查看“︁情境最佳化”︁的源代码

{{orphan|time=2019-01-23T05:07:08+00:00}}
'''情境最佳化'''（scenario optimization）也稱為'''情境方法'''（scenario approach），是一種求解{{link-en|強健最佳化|robust optimization}}問題和[[機會約束規劃]]（chance-constrained optimization）問題的方式，其方法會以一些[[約束 (數學)|約束]]的樣本為基礎。情境最佳化也和建模及決策中的[[归纳推理]]有關。此方法已以[[启发法]]的形式存在了數十年，近來開始探討此方法系統化理論的基礎。

== 簡介 ==
在[[最优化]]的應用中，強健性的特點會轉變成一些拘束條件，其中的參數是問題中的未知量。在情境最佳化方法<ref>G. Calafiore and M.C. Campi. ''Uncertain Convex Programs: Randomized Solutions and Confidence Levels.'' Mathematical Programming, 102: 25&ndash;46, 2005. [http://www.springerlink.com/content/qlcbr9eg3dne6ldb/?p=ad759ab4ef9f49049f9b5ef14e7b00ee&pi=1] {{Webarchive|url=https://archive.today/20130203025646/http://www.springerlink.com/content/qlcbr9eg3dne6ldb/?p=ad759ab4ef9f49049f9b5ef14e7b00ee&pi=1 |date=2013-02-03 }}</ref><ref>G. Calafiore and M.C. Campi. "The scenario approach to robust control design," IEEE Transactions on Automatic Control, 51(5). 742-753, 2006. [http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=1632303&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D1632303]</ref><ref name="#1">M.C. Campi and S. Garatti. ''The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs.'' SIAM J. on Optimization, 19, no.3: 1211&ndash;1230, 2008.[http://epubs.siam.org/siopt/resource/1/sjope8/v19/i3/p1211_s1]</ref>中，會用亂數取樣的方式，找到一些亂數取樣的拘束樣本（[[启发法]]），這些拘束樣本稱為「情境」（scenarios），會先只根據這些拘束條件找到一個解，之後再配合其他方法求得這個解和其他拘束之間的強健性。此理論證實了在強健最佳化及機會約束最佳化中，使用{{link-en|亂數|randomization}}是合理的。

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

== 理論結果 ==
針對[[凸優化|凸拘束]]（也就是和[[线性矩阵不等式]]有關的{{link-en|半定規劃|semidefinite programming|半定問題}}），已有深入的理論分析說明新的拘束無法滿足的機率是依照以[[Β分布|β分布]]為主的分布。針對所有凸優化問題的結果也是如此<!--This result is tight since it is exact for a whole class of convex problems.--><ref name="#1"/>。再繼續擴展，有許多實驗等級的結果是依照[[狄利克雷分布]]，其邊緣分布為β分布<ref>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. [http://epubs.siam.org/doi/abs/10.1137/130928546] {{Wayback|url=http://epubs.siam.org/doi/abs/10.1137/130928546 |date=20220122075525 }}</ref>。也有探討過配合<math>L_1</math>正則化的情境最佳化<ref>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. [http://epubs.siam.org/doi/abs/10.1137/110856204?journalCode=sjcodc] {{Wayback|url=http://epubs.siam.org/doi/abs/10.1137/110856204?journalCode=sjcodc |date=20190124041725 }}</ref>，也有便利的算法，可以簡化運算的複雜度<ref>A. Caré, S. Garatti and M.C. Campi. ''FAST - Fast Algorithm for the Scenario Technique''. Operations Research, 62, no.3: 662-671, 2014. [https://pubsonline.informs.org/doi/abs/10.1287/opre.2014.1257] {{Wayback|url=https://pubsonline.informs.org/doi/abs/10.1287/opre.2014.1257 |date=20220122021532 }}</ref>。有關更複雜、非凸拘束的研究是目前熱門的研究主題。

配合情境最佳化，可以在風險和回報中取得權衡<ref name="#2">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&ndash;280, 2011 (preliminary version published in Optimization Online, 2008). [http://www.springerlink.com/content/a0146681n6878894/]{{Dead link|date=2020年2月 |bot=InternetArchiveBot |fix-attempted=yes }}</ref><ref>G.C. Calafiore. ''Random Convex Programs''. SIAM J. on Optimization, 20(6) 3427-3464, 2010. [http://epubs.siam.org/doi/abs/10.1137/090773490] {{Wayback|url=http://epubs.siam.org/doi/abs/10.1137/090773490 |date=20190124041428 }}</ref>，而且有完整的方法可以將此結果應用在控制上<ref>S. Garatti and M.C. Campi. ''Modulating Robustness in Control Design: Principles and Algorithms.''. IEEE Control Systems Magazine, 33, 36&#x2013;51, 2013. [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6479421&filter%3DAND%28p_IS_Number%3A6479381%29]</ref>。一開始先選擇<math>N</math>個拘束開始進行最佳化，之後持續的移除其中的一些拘束，移除過程可以用不同的方式行，甚至是利用貪心法。每當多消除一個拘束後，會更新最佳化的解，也會得到對應最佳化的數值。在此程序持續進行時，可以得到經驗式的「最佳值曲線」，也就是在移除多少數量的拘束後，最佳值的變化。情境最佳化可以針對各個解的強健性作準確的評估。

此技術一個很大的進步是透過wait-and-judge方法得到的<ref>M.C. Campi and S. Garatti. ''Wait-and-judge scenario optimization.''. Mathematical Programming, published online, 2016. [https://link.springer.com/article/10.1007/s10107-016-1056-9?view=classic] {{Wayback|url=https://link.springer.com/article/10.1007/s10107-016-1056-9?view=classic |date=20190124041247 }}</ref>：先評估解的複雜度（如前面所述），並根據其值的公式來評估解的強健性。這些結果可以看來複雜度和風險二個概念之間的深層關係。有一個相關的研究方式，稱為「重複情形設計」（Repetitive Scenario Design），是用透過重複的交替情境設計的階段（用較少的樣本）再隨機的確認其解的可行性，目的是要降低解的複雜度<ref>G.C. Calafiore. ''Repetitive Scenario Design.''  IEEE Transactions on Automatic Control, Vol. 62, Issue 3, March 2017, pp. 1125-1137. [http://ieeexplore.ieee.org/document/7484339/] {{Wayback|url=http://ieeexplore.ieee.org/document/7484339/ |date=20190214195921 }}</ref>。

== 例子 ==
考慮一函數<math>R_\delta(x)</math>為[[投资]]的獲利，此函數和投資選擇向量<math>x</math>及市場狀態<math>\delta</math>有關，這些資訊在投資週期的最後會知道。

假設一個市場狀態的隨機模型，考慮有<math>N</math>個可能狀態<math>\delta_1, \dots, \delta_N</math> （亂數或是不確定性）。接著，可以從觀察記錄中找到情境<math>\delta_i</math>。

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

: <math>\max_x \min_{i=1,\dots,N} R_{\delta_i}(x). \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)</math>

對應一個投資組合向量''x''，可以在最壞的情境下有最好的報酬<ref>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. [https://link.springer.com/article/10.1007/s10957-012-0074-x] {{Wayback|url=https://link.springer.com/article/10.1007/s10957-012-0074-x |date=20190419233347 }}</ref><ref>G.C. Calafiore. ''Direct data-driven portfolio optimization with guaranteed shortfall probability''. Automatica, 49(2) 370-380, 2013. [http://www.sciencedirect.com/science/article/pii/S0005109812005481]</ref>。

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

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

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

== 參考資料 ==
{{reflist}}

<!-- [[Category:Stochastic optimization]]
[[Category:Optimal decisions]] -->
[[Category:控制理论]]
[[Category:金融数学]]