情境最佳化

情境最佳化（scenario optimization）也稱為情境方法（scenario approach），是一種求解問題和機會約束規劃（chance-constrained optimization）問題的方式，其方法會以一些約束的樣本為基礎。情境最佳化也和建模及決策中的归纳推理有關。此方法已以启发法的形式存在了數十年，近來開始探討此方法系統化理論的基礎。

 簡介 
在最优化的應用中，強健性的特點會轉變成一些拘束條件，其中的參數是問題中的未知量。在情境最佳化方法G. Calafiore and M.C. Campi. Uncertain Convex Programs: Randomized Solutions and Confidence Levels. Mathematical Programming, 102: 25–46, 2005.  G. Calafiore and M.C. Campi. "The scenario approach to robust control design," IEEE Transactions on Automatic Control, 51(5). 742-753, 2006. M.C. Campi and S. Garatti. The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs. SIAM J. on Optimization, 19, no.3: 1211–1230, 2008.中，會用亂數取樣的方式，找到一些亂數取樣的拘束樣本（启发法），這些拘束樣本稱為「情境」（scenarios），會先只根據這些拘束條件找到一個解，之後再配合其他方法求得這個解和其他拘束之間的強健性。此理論證實了在強健最佳化及機會約束最佳化中，使用是合理的。

 資料驅動的最佳化 
有時情境的資訊是由模型中以亂數的方式拮取出來。不過更常見的是情境是從觀測資料中找到的不確定事件（数据科学）。在後者的情形下，不需要不確定性的模型即可以產生情境。最值得注意的是，此情形下的情境最佳化伴隨著的是
成熟的理論，因為所有情境最佳化的結果都和分佈無關，因此可以應用在沒有不確定性模型或是缺乏類似資訊的情形下。

 理論結果 
針對凸拘束（也就是和线性矩阵不等式有關的），已有深入的理論分析說明新的拘束無法滿足的機率是依照以β分布為主的分布。針對所有凸優化問題的結果也是如此。再繼續擴展，有許多實驗等級的結果是依照狄利克雷分布，其邊緣分布為β分布A. Caré, S. Garatti and M.C. Campi.Scenario min-max optimization and the risk of empirical costs . SIAM Journal on Optimization, 25, no.4: 2061-2080, 2015, Mathematical Programming, published online, 2016.  。也有探討過配合正則化的情境最佳化M.C. Campi and A. Carè. Random convex programs with L1-regularization: sparsity and generalization. SIAM Journal on Control and Optimization, 51, no.5: 3532-3557, 2013.  ，也有便利的算法，可以簡化運算的複雜度A. Caré, S. Garatti and M.C. Campi. FAST - Fast Algorithm for the Scenario Technique. Operations Research, 62, no.3: 662-671, 2014.  。有關更複雜、非凸拘束的研究是目前熱門的研究主題。

配合情境最佳化，可以在風險和回報中取得權衡M.C. Campi and S. Garatti. A Sampling-and-Discarding Approach to Chance-Constrained Optimization: Feasibility and Optimality. Journal of Optimization Theory and Applications, 148, Number 2, 257–280, 2011 (preliminary version published in Optimization Online, 2008). G.C. Calafiore. Random Convex Programs. SIAM J. on Optimization, 20(6) 3427-3464, 2010.  ，而且有完整的方法可以將此結果應用在控制上S. Garatti and M.C. Campi. Modulating Robustness in Control Design: Principles and Algorithms.. IEEE Control Systems Magazine, 33, 36–51, 2013. 。一開始先選擇個拘束開始進行最佳化，之後持續的移除其中的一些拘束，移除過程可以用不同的方式行，甚至是利用貪心法。每當多消除一個拘束後，會更新最佳化的解，也會得到對應最佳化的數值。在此程序持續進行時，可以得到經驗式的「最佳值曲線」，也就是在移除多少數量的拘束後，最佳值的變化。情境最佳化可以針對各個解的強健性作準確的評估。

此技術一個很大的進步是透過wait-and-judge方法得到的M.C. Campi and S. Garatti. Wait-and-judge scenario optimization.. Mathematical Programming, published online, 2016.  ：先評估解的複雜度（如前面所述），並根據其值的公式來評估解的強健性。這些結果可以看來複雜度和風險二個概念之間的深層關係。有一個相關的研究方式，稱為「重複情形設計」（Repetitive Scenario Design），是用透過重複的交替情境設計的階段（用較少的樣本）再隨機的確認其解的可行性，目的是要降低解的複雜度G.C. Calafiore. Repetitive Scenario Design.  IEEE Transactions on Automatic Control, Vol. 62, Issue 3, March 2017, pp. 1125-1137.  。

 例子 
考慮一函數為投资的獲利，此函數和投資選擇向量及市場狀態有關，這些資訊在投資週期的最後會知道。

假設一個市場狀態的隨機模型，考慮有個可能狀態 （亂數或是不確定性）。接著，可以從觀察記錄中找到情境。

要求解以下的情境最佳化問題



對應一個投資組合向量x，可以在最壞的情境下有最好的報酬B.K. Pagnoncelli, D. Reich and M.C. Campi. Risk-Return Trade-off with the Scenario Approach in Practice: A Case Study in Portfolio Selection. Journal of Optimization Theory and Applications, 155: 707-722, 2012.  G.C. Calafiore. Direct data-driven portfolio optimization with guaranteed shortfall probability. Automatica, 49(2) 370-380, 2013. 。

在求解(1)後，可以得到最佳投資策略，對應此情形的最佳報酬。當. While 只根據個可能的市場狀態求得時，透過情境最佳化理論可以得到其強健性最大到，意思是指，在其他的市場狀態下，可達到報酬達到的機率只有。

在量化金融上，最壞條件的分析可能過於保守。另一種作法是不考慮一些奇怪的情形，以減少悲观情绪，而情境最佳化也可以用在其他風險度量中，例如CVaR（风险条件值，Conditional Value at Risk），因此增加使用靈活度M.C. Campi and Federico Alessandro Ramponi. Expected shortfall: Heuristics and certificates. European Journal of Operational Research. 。

應用領域 
應用領域包括：預測、系统科学、迴歸分析、精算學、最优控制、數理金融學、机器学习、决策、供应链及管理学等。

 參考資料 

Category:控制理论
Category:金融数学