跳转到内容

英文维基 | 中文维基 | 日文维基 | 草榴社区

情境最佳化

维基百科,自由的百科全书

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

簡介

[编辑]

最优化的應用中,強健性的特點會轉變成一些拘束條件,其中的參數是問題中的未知量。在情境最佳化方法[1][2][3]中,會用亂數取樣的方式,找到一些亂數取樣的拘束樣本(启发法),這些拘束樣本稱為「情境」(scenarios),會先只根據這些拘束條件找到一個解,之後再配合其他方法求得這個解和其他拘束之間的強健性。此理論證實了在強健最佳化及機會約束最佳化中,使用亂數是合理的。

資料驅動的最佳化

[编辑]

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

理論結果

[编辑]

針對凸拘束(也就是和线性矩阵不等式有關的半定問題英语semidefinite programming),已有深入的理論分析說明新的拘束無法滿足的機率是依照以β分布為主的分布。針對所有凸優化問題的結果也是如此[3]。再繼續擴展,有許多實驗等級的結果是依照狄利克雷分布,其邊緣分布為β分布[4]。也有探討過配合正則化的情境最佳化[5],也有便利的算法,可以簡化運算的複雜度[6]。有關更複雜、非凸拘束的研究是目前熱門的研究主題。

配合情境最佳化,可以在風險和回報中取得權衡[7][8],而且有完整的方法可以將此結果應用在控制上[9]。一開始先選擇個拘束開始進行最佳化,之後持續的移除其中的一些拘束,移除過程可以用不同的方式行,甚至是利用貪心法。每當多消除一個拘束後,會更新最佳化的解,也會得到對應最佳化的數值。在此程序持續進行時,可以得到經驗式的「最佳值曲線」,也就是在移除多少數量的拘束後,最佳值的變化。情境最佳化可以針對各個解的強健性作準確的評估。

此技術一個很大的進步是透過wait-and-judge方法得到的[10]:先評估解的複雜度(如前面所述),並根據其值的公式來評估解的強健性。這些結果可以看來複雜度和風險二個概念之間的深層關係。有一個相關的研究方式,稱為「重複情形設計」(Repetitive Scenario Design),是用透過重複的交替情境設計的階段(用較少的樣本)再隨機的確認其解的可行性,目的是要降低解的複雜度[11]

例子

[编辑]

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

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

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

對應一個投資組合向量x,可以在最壞的情境下有最好的報酬[12][13]

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

在量化金融上,最壞條件的分析可能過於保守。另一種作法是不考慮一些奇怪的情形,以減少悲观情绪[7],而情境最佳化也可以用在其他風險度量中,例如CVaR(风险条件值,Conditional Value at Risk),因此增加使用靈活度[14]

應用領域

[编辑]

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

參考資料

[编辑]
  1. ^ G. Calafiore and M.C. Campi. Uncertain Convex Programs: Randomized Solutions and Confidence Levels. Mathematical Programming, 102: 25–46, 2005. [1] Archive.is存檔,存档日期2013-02-03
  2. ^ G. Calafiore and M.C. Campi. "The scenario approach to robust control design," IEEE Transactions on Automatic Control, 51(5). 742-753, 2006. [2]
  3. ^ 3.0 3.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–1230, 2008.[3]
  4. ^ 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. [4]页面存档备份,存于互联网档案馆
  5. ^ 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. [5]页面存档备份,存于互联网档案馆
  6. ^ A. Caré, S. Garatti and M.C. Campi. FAST - Fast Algorithm for the Scenario Technique. Operations Research, 62, no.3: 662-671, 2014. [6]页面存档备份,存于互联网档案馆
  7. ^ 7.0 7.1 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). [7][永久失效連結]
  8. ^ G.C. Calafiore. Random Convex Programs. SIAM J. on Optimization, 20(6) 3427-3464, 2010. [8]页面存档备份,存于互联网档案馆
  9. ^ S. Garatti and M.C. Campi. Modulating Robustness in Control Design: Principles and Algorithms.. IEEE Control Systems Magazine, 33, 36–51, 2013. [9]
  10. ^ M.C. Campi and S. Garatti. Wait-and-judge scenario optimization.. Mathematical Programming, published online, 2016. [10]页面存档备份,存于互联网档案馆
  11. ^ G.C. Calafiore. Repetitive Scenario Design. IEEE Transactions on Automatic Control, Vol. 62, Issue 3, March 2017, pp. 1125-1137. [11]页面存档备份,存于互联网档案馆
  12. ^ 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. [12]页面存档备份,存于互联网档案馆
  13. ^ G.C. Calafiore. Direct data-driven portfolio optimization with guaranteed shortfall probability. Automatica, 49(2) 370-380, 2013. [13]
  14. ^ M.C. Campi and Federico Alessandro Ramponi. Expected shortfall: Heuristics and certificates. European Journal of Operational Research. [14]