魯棒優(yōu)化的方法及應用

1、.頁眉魯棒優(yōu)化的方法及應用 楊威在實際的優(yōu)化中決策過程中，我們經(jīng)常遇到這樣的情形，數(shù)據(jù)是不確定的或者是非精確的；最優(yōu)解不易計算，即使計算的非常精確，但是很難準確的實施；對于數(shù)據(jù)的一個小的擾動可能導致解是不可行。魯棒優(yōu)化是一個建模技術(shù)，可以處理數(shù)據(jù)不確定但屬于一個不確定集合的優(yōu)化問題。早在19世紀70年代，Soyster就是最早開始研究魯棒優(yōu)化問題的學者之一，他的文章給出了當約束矩陣的列向量屬于一個橢球形不確定的集合時的魯棒線性優(yōu)化問題。幾年以后Falk沿著這條思路做了非精確的線性規(guī)劃。在以后的很長的一段時間里，魯棒優(yōu)化方面都沒有新的成果出現(xiàn)。直到19世紀末，Ben-Tal,Nemirovski

2、的工作以及這時計算技術(shù)的發(fā)展，尤其是對于半定優(yōu)化和凸優(yōu)化內(nèi)點算法的發(fā)展，使得魯棒優(yōu)化又成為一個研究的熱點。 一個一般的數(shù)學規(guī)劃的形式為其中為設計向量，為目標函數(shù)，是問題的結(jié)構(gòu)元素。表示屬于特定問題的數(shù)據(jù)。是數(shù)據(jù)空間中的某個不確定的集合。對于一個不確定問題的相應的魯棒問題為 這個問題的可行解和最優(yōu)解分別稱為不確定問題的魯棒可行和魯棒最優(yōu)解。這篇文章主要回顧了魯棒優(yōu)化的基本算法，目前的最新的研究結(jié)果及在經(jīng)濟上的應用。1 魯棒優(yōu)化的基本方法1.1魯棒線性規(guī)劃一個不確定線性規(guī)劃所對應的魯棒優(yōu)化問題為，如果不確定的集合是一個計算上易處理的問題，則這個線性規(guī)劃也是一個計算上易處理的問題。并且有下列的結(jié)論：

3、假設不確定的集合由一個有界的集合的仿射像給出，如果是1線性不等式約束系統(tǒng)構(gòu)成，則不確定線性規(guī)劃的魯棒規(guī)劃等價于一個線性規(guī)劃問題。2由錐二次不等式系統(tǒng)給出，則不確定線性規(guī)劃的魯棒規(guī)劃等價于一個錐二次的問題。3 由線性矩陣不等式系統(tǒng)給出，則所導致的問題為一個半定規(guī)劃問題。1.2魯棒二次規(guī)劃考慮一個不確定的凸二次約束問題對于這樣的一個問題，即使不確定集合的結(jié)夠很簡單，也會導致NP難的問題，所以對于這種問題的處理通常是采用它的近似的魯棒規(guī)劃問題?？紤]一個不確定的優(yōu)化問題，假設不確定集合為，而表示名義的數(shù)據(jù)，而表示一個擾動的集合，假設是一個包含原點的凸緊集。不確定問題可以看成是一個不確定問題的參數(shù)族，表

4、示不確定的水平。具有橢圓不確定性的不確定的凸二次規(guī)劃問題的近似魯棒問題其中則問題可一轉(zhuǎn)化為一個半定規(guī)劃問題 具有橢圓不確定集合的不確定錐二次問題的近似魯棒規(guī)劃考慮不確定錐二次規(guī)劃它的約束為逐側(cè)的不確定它的左側(cè)的不確定的集合是一個橢圓其中右側(cè)的不確定集合是有界的，它的半定表示為，為線性映射。則半定規(guī)劃為其中1.3魯棒半定規(guī)劃一個不確定的半定規(guī)劃的魯棒規(guī)劃為由一個箱式不確定集合影響的不確定半定規(guī)劃的近似魯棒問題。則半定規(guī)劃的近似的魯棒優(yōu)化為由一個球不確定集合影響的不確定半定規(guī)劃的近似魯棒問題。則半定規(guī)劃問題為具有易處理的魯棒counterparts的不確定線性規(guī)劃。 如果多胞形是由有限集合的凸包給

5、出的，則魯棒規(guī)劃為2 魯棒優(yōu)化的幾種新的方法 魯棒規(guī)劃的最近的研究包括了對于可調(diào)節(jié)的魯棒優(yōu)化的研究以及對于魯棒凸優(yōu)化的研究。2.1不確定的線性規(guī)劃的可調(diào)節(jié)的魯棒解不確定線性規(guī)劃為，其中不確定集合是一個非空的緊的凸集，稱為recourse矩陣。當是確定的情況下，則稱相應的不確定線性規(guī)劃為固定recourse的。定義：線性規(guī)劃的魯棒counterpart為 ，則它的可調(diào)節(jié)的魯棒counterpart為。可調(diào)節(jié)的魯棒規(guī)劃比一般的魯棒規(guī)劃靈活，但是同時它也比一般的魯棒規(guī)劃難解。對于一個不確定線性規(guī)劃的魯棒規(guī)劃是一個計算上易處理的問題，然而它相應的可調(diào)節(jié)的魯棒規(guī)劃卻是不易處理的問題。但是如果不確定集合是

6、有限集合的凸包，則固定recourse的ARC是通常的線性規(guī)劃。從實際的應用來看，只有當原不確定問題的魯棒counterpart在計算上容易處理的時候，魯棒優(yōu)化方法才有意義。當可調(diào)節(jié)的變量是數(shù)據(jù)的仿射函數(shù)時，可以得到一個計算上易處理的魯棒counterpart.對于的仿射可調(diào)節(jié)的魯棒counterpart (AARC)可以表示為。如果是一個計算上易處理的集合，則在固定recourse的情況下，的仿射可調(diào)節(jié)的魯棒counterpart (AARC)是一個計算上易處理的問題。如果是這樣的一個集合，是一個非空的凸緊集。在固定的recourse的情況下，AARC具有這樣的形式如果不確定的集合是一個錐表

7、示的，則的仿射可調(diào)節(jié)的魯棒counterpart (AARC)是一個錐二次或半定規(guī)劃。如果recourse也是可變的，則AARC是不易處理的問題，這時采用它的近似形式。在簡單橢圓不確定集合的情況下，AARC等價于一個半定規(guī)劃。當擾動的集合是一個中心在原點的箱式集合或者是一個關于原點對稱的多胞形集合，則AARC可以有一個半定規(guī)劃來近似。對于多期的決策問題也是一個可調(diào)節(jié)的魯棒優(yōu)化問題?？紤]一個兩期的決策問題其中是不確定的，但屬于一個閉的有界的不確定集合。可行集依賴于和參數(shù)。則可以表示為，或。可調(diào)節(jié)的魯棒counterpart問題可以表示為， 可以等價的表示為 。 如果包含有限數(shù)量的元素，則對于每個

8、，都存在著相應的滿足上面的問題。則問題可以轉(zhuǎn)化為一個等價的單層優(yōu)化問題這樣的一個單層的優(yōu)化問題對于許多類的函數(shù)和集合，這是一個易處理的問題。比如，其中，在這種情況下，問題等價于一個二次約束的優(yōu)化問題如果不確定集合是有限集合的凸包，則考慮下面的問題如果是擬凸的，則。則問題轉(zhuǎn)化為一個單層的優(yōu)化問題。 2.2一個錐二次問題的魯棒解一個錐二次約束的形式為，或者是等價的形式，是Lorentz錐。假設不確定參數(shù)屬于一個有界的集合。兩種類型的不確定集合常常用到，一個是范數(shù)有界的不確定集合，一個是擾動的向量屬于一個有界的擾動集合時的結(jié)構(gòu)不確定集合。對于參數(shù)的結(jié)構(gòu)不確定為，其中是描述擾動的向量，是表示擾動幅度的

9、向量，是擾動集合，是名義數(shù)值，為擾動方向。是橢圓的交集 ，為對稱的正半定矩陣，且是正定的。對于一個單側(cè)不確定的錐二次約束，El Ghaoui和Lebret證明了在不確定集合是范數(shù)有界的情況下，問題等價于一個錐二次約束。Ben-Tal,Nemirovski給出了在擾動集合是橢圓集合的交集的結(jié)構(gòu)不確定的情況下，如果是簡單的橢圓不確定集合，則相應的魯棒counterpart為一個線性矩陣不等式，在一般的情況下，問題是NP難的，但是可以用線性矩陣不等式來近似。Ben-Tal等研究了逐側(cè)不確定的錐二次約束，即對于影響左側(cè)的不確定獨立于影響右側(cè)的不確定。，是相互獨立的集合。則是問題的可行解，但且僅當存在，

10、使得，和成立。在具有橢球交集的結(jié)構(gòu)不確定的集合的情況下，這兩個問題是易處理的。在很多的情況下，影響兩側(cè)的不確定集合是相互依存的。比如考慮一個不確定的錐二次約束 ， (*)其中關于是仿射的。是中心在原點的橢圓的交集。，為對稱的正半定矩陣，且是正定的。如果存在著，且滿足下式，則滿足(*)式。其中 如果向量被分成兩部分，其中表示不可調(diào)節(jié)的變量，表示可調(diào)節(jié)的變量。假設目標函數(shù)是確定的，獨立于可調(diào)節(jié)的變量，則相應的錐優(yōu)化問題為，是一個錐。則相應于不確定集合的魯棒counterpart為則可調(diào)節(jié)的魯棒規(guī)劃為?？烧{(diào)節(jié)的魯棒規(guī)劃比一般的魯棒靈活一些。但是這樣會導致所得到的問題是不易處理的?？朔嬎闵先秉c的一個

11、方法是限制可調(diào)節(jié)的變量為一個仿射函數(shù)。，這樣得到了仿射可調(diào)節(jié)的魯棒規(guī)劃為對于結(jié)構(gòu)不確定的錐二次約束可表示為，如果分別用表示的子向量，并且分別對應于不可調(diào)節(jié)的部分和可調(diào)節(jié)的部分，則上面的約束可以表示為(*)，若，則上面的約束即為仿射可調(diào)節(jié)的約束。下面分成兩種情況來討論，一種是固定的recourse,即是確定的，一種是可變的recourse，即是不確定的。在第一種情況下，如果約束由(*)表達，擾動集合為中心在原點的橢圓的交集，如果存在和使得下式成立，則會存在一個解滿足(*)，對于所有的擾動成立， 其中， 在第二種情況下，如果擾動很小，使得二次項可以被忽略，則可以用上面的半定規(guī)劃來近似。如果二次項不

12、能夠被忽略，則需要增加一些變量后能夠用一個半定規(guī)劃來近似。 2.3 魯棒凸優(yōu)化2.3.1魯棒凸二次約束的規(guī)劃問題 一個凸二次約束的規(guī)劃問題為，其中為決策向量，為參數(shù)。上面的這個問題可以轉(zhuǎn)化為一個二階的錐規(guī)劃問題由于上述的模型對于參數(shù)很敏感，所以有必要研究其對應的魯棒問題一個一般的魯棒凸二次規(guī)劃問題為當不確定的集合是橢球時，上面的問題可以轉(zhuǎn)化為一個半定規(guī)劃問題，這里我們來確定的結(jié)構(gòu)，使它能夠轉(zhuǎn)化為一個二階錐規(guī)劃。分成以下的三種情況:1離散集合和多邊形不確定集合對于離散形式的集合定義為，魯棒約束等價于K個凸二次約束?；蛘叩葍r的個二階錐約束。對于離散集合的凸包為，則魯棒約束等價于將上面的兩種情況下的

13、集合推廣到多邊形的不確定集合。如果決策向量滿足魯棒約束，對于所有的，當且僅當存在著，使得其中是的第列，。2范數(shù)約束的不確定的集合一個決策向量滿足魯棒約束，對于所有的，當且僅當存在和，滿足，其中，二次項和錐項的不確定性是獨立的，即一個決策向量滿足魯棒約束，對于所有的，當且僅當存在和，滿足，其中，3因子化的不確定的集合如果不確定的集合定義為一個決策向量滿足魯棒約束，對于所有的，當且僅當存在，使得下式成立其中是的譜分解，。2.3.2二次約束的二次規(guī)劃的魯棒解 對于一個非凸的二次約束的二次優(yōu)化問題 其中是一個多面體，并且包含在中，每個的形式為。任何一個二次多項式可以寫成兩個正系數(shù)的二次多項式的差，一個

14、一般的(QQP)可以寫成由于，則問題可以轉(zhuǎn)化為通過變換記號，可以得到這樣的形式 其中，所有的系數(shù)為正的。，并且為單調(diào)遞增的二次函數(shù)使得由于孤立的最優(yōu)解即使是可計算的，但是它是難于實施，因為它對一個小的擾動非常的不穩(wěn)定，因而，從實際的觀點來看，只有非孤立的可行解有意義。 Essential 最優(yōu)解，表示所以非孤立的可行解的集合。 Essential可行解：滿足。一個非孤立的可行解稱為是Essential最優(yōu)解，如果它滿足尋找Essential最優(yōu)解的方法是：從一個初始的Essential可行解，尋找一個更好的Essential可行解，直到不能獲得比當前的可行解更好的可行解為止。假設為一個Esse

15、ntial可行解的目標函數(shù)值，給定：如果，由于單調(diào)遞增，則如果，則即為一個Essential可行解如果，則需要考慮一個輔助的問題求解采用分支定界的方法。這篇文章中給出了一個successive incumbent transcending(SIT)算法。3 魯棒優(yōu)化的應用 魯棒優(yōu)化現(xiàn)在已經(jīng)應用到了各個研究領域，這里我們主要給出了在金融上的應用。1Ruijun Shen和Shuzhong Zhang將魯棒的觀點應用于基于scenario樹的投資組合的選擇問題中，給出了一階段和兩階段的組合選擇模型相應的魯棒規(guī)劃問題。這里允許概率分布存在ambiguity.這樣的一個問題能夠轉(zhuǎn)化為一個有限的錐形式凸

16、規(guī)劃問題。并且在不允許賣空的情況下，效用函數(shù)采用下半方差的負值，參數(shù)的不確定集合是橢球形的，則相應的問題可以轉(zhuǎn)化成一個二階錐規(guī)劃問題。 假設想從種資產(chǎn)中選擇一個投資組合并且持有一段時間，假設初始的財富為1，持有期末有種可能的結(jié)果。即所有的可能的scenario可以通過一個具有個葉子的一階段樹來表示。假設收益向量的第個元素表示表示第種資產(chǎn)的收益。則基于scenario的單階段的組合選擇模型為 是股票的數(shù)量，是每個節(jié)點scenario的數(shù)量是持有的股票，是模型中的決策向量是如果scenario 出現(xiàn)的話個股票的收益是scenario 出現(xiàn)的概率是分量全為1的向量是允許的投資組合集合則兩階段的效用極

17、大化投資模型為 表示如果scenario 出現(xiàn)在第一階段，scenario 出現(xiàn)在第二階段表示條件概率scenario 出現(xiàn)在第二階段在scenario 出現(xiàn)在第一階段的條件下的概率。第二階段允許的投資組合是第二階段的recourse問題的最優(yōu)解則上面的問題可以寫成(P2) 假設可行集為凸集令，且由定義可知為非負的向量問題(P2)是可分的，則可得由于是凹的，則上面的問題為凸規(guī)劃。單階段模型的魯棒規(guī)劃模型確定的情景樹有兩個缺點：一個是每個情境中收益的模糊性，一個是每個情景發(fā)生的條件概率的模糊性。實際上在我們的模型中用到的收益向量為估計值。并且我們并不知道確切的收益為多少，但是根據(jù)統(tǒng)計分析，我們知

18、道實際的值離我們估計的值不遠，我們可以得到某些置信區(qū)間。（收益的模糊性）（概率分布的模糊性）假設所有的集合為凸的，緊的，非空的。令，則魯棒模型為兩階段的魯棒規(guī)劃模型兩階段的模型中的估計量為,令，,令，.單階段魯棒模型的有限表示假設條件：1 沒有賣空 2 一個半方差的非效用函數(shù)相當于一個給定的基準組合的下方風險，相應的效用函數(shù)為。模糊集合是橢球形的：，為了簡便，假設是單位矩陣，則原模型可變形為則相應的魯棒規(guī)劃模型為進一步變形為利用結(jié)論將上面的規(guī)劃變?yōu)閷τ谝粋€一般的模型通過增加變量變?yōu)槿绻且粋€凸集，則它的齊次錐是則可以得到如下的凸表示對于多階段的魯棒模型因此把球映射到區(qū)間，則上述模型等價于2R.

19、h.tutuncu, M.Koenig給出一個基于worse-case的方法。在一個簡單的情況下，相應魯棒優(yōu)化問題是一個標準的二次規(guī)劃問題，在大多數(shù)情況下，這個問題可以轉(zhuǎn)化為一個鞍點問題。利用2003年Handorsson和Tutuncu給出的方法求解。作者給出了在不確定集合為區(qū)間時的魯棒MVO模型，和魯棒最大夏普比率問題。一個資產(chǎn)分配問題可以表示為在期望收益的下限上極小化方差或最大化一個風險調(diào)節(jié)的期望收益 （1） （2）其中對于期望收益的向量和協(xié)方差矩陣分別取成區(qū)間的形式采用區(qū)間型數(shù)據(jù)的原因：（1）區(qū)間的端點對應于歷史數(shù)據(jù)中相應的統(tǒng)計的極值，在分析估計和Scenarios中。（2）建模者可以

20、選擇置信水平，以預測區(qū)間的形式產(chǎn)生收益和協(xié)方差的估計。給定不確定集合，優(yōu)化問題（1）（2）對應的魯棒優(yōu)化為 （7） （8）若是（8）一個給定正值的最優(yōu)解，則也是（7）的最優(yōu)解對于。US財政證券可以認為是無風險投資。如果這樣的資產(chǎn)包含于資產(chǎn)類中，則有效的投資組合是這個無風險資產(chǎn)和一個風險組合的線性組合。這個最優(yōu)的組合是具有最高夏普比率的組合。，為無風險的已知收益。假設是正定的。因為是正半定的，若它是正定的，則意味著沒有冗余的資產(chǎn)。具有最高夏普比率的組合可以通過解決下面的優(yōu)化問題給出： （11）這個目標函數(shù)是一個非線性，非凹的目標函數(shù)，難以解決。利用lifting技術(shù)對進行齊次化：，增加是為了或得

21、一個凸集。是一個錐，當是一個環(huán)的時候，是一個ice-cream錐，若是一個多面體，則。，由于是齊次的，則問題等價于，由于是齊次的，則增加規(guī)范化的約束不會影響最優(yōu)解，則問題等價于 結(jié)論：給定一個可行的具有性質(zhì)的組合集，這個集合中具有最大夏普比率的解可以通過下面的規(guī)劃來解： （15）若是（15）的解，則。松弛問題如下：魯棒有效前沿的算法：1利用SP算法解決沒有期望收益約束的問題，令表示他的最優(yōu)解，令2，解決問題，令表示他的最優(yōu)解，3 選擇，有效前沿上點的數(shù)量，解決問題3Mustafa C.Pinar 給出了多階段的組合選擇模型。目標是最大化最終期望收益和最小化與一個給定的財富水平的偏差。他們之間是

22、通過一個非負參數(shù)來平衡的。利用一個分段的線性罰函數(shù)，能夠得到線性規(guī)劃模型，并且能夠確保如下階段的最優(yōu)性。假設有種資產(chǎn)，前種為風險的股票，第種為無風險資產(chǎn)，比如現(xiàn)金。表示1階段初的決策向量，表示相應的組合種第種資產(chǎn)的市值。表示2階段初的決策向量，表示一階段和二階段結(jié)束后的凈資產(chǎn)收益。是有限概率空間上的離散的隨機變量。假設市場的發(fā)展是離散的scenario樹。表示隨機變量相應于第一層scenario樹的第n個節(jié)點的實現(xiàn)?；谧畲蟮钠谕鹐nd-of-horizon組合值的沒有交易費用的兩階段組合選擇模型的隨機規(guī)劃為：其中由于recourse 問題的可分性，上面的優(yōu)化問題等價于以上的模型假設決策者是風

23、險中立的，Mulvey,Vanderbei and Zenios建議通過由一個參數(shù)控制給目標函數(shù)增加一個風險項得到兩階段的魯棒隨機規(guī)劃。他們的模型為 （4）則可分離的魯棒優(yōu)化模型為（5）Takriti and Ahmed證明了對于任意的方差測度，上式對能夠給出當兩階段的組合決策問題對于recourse問題不是最優(yōu)時的最優(yōu)解。 如果是一個非減的函數(shù)，則上面的兩個問題時等價的。Takriti and Ahmed利用了一個分段二次的方差度量 ，其中是目標函數(shù)值。是一組離散的隨機變量，具有實現(xiàn)，而是相應的概率。為了是計算方便是所得的問題是一個線性規(guī)劃，采用一個分段線性的方差測度 它仍然滿足非減的條件。

24、則我們的問題變?yōu)榭梢詫⑸厦娴哪Ｐ屯茝V到三階段的情況。在這篇文章中作者還給出了包含線性交易費用的模型。表示一階段買入資產(chǎn)的數(shù)量，表示一階段買入一美元的資產(chǎn)的交易費表示一階段賣出資產(chǎn)的數(shù)量，表示一階段賣出一美元的資產(chǎn)的交易費表示的第個分量則對于風險資產(chǎn)， 對于無風險資產(chǎn)初始的資金要求為則可行集為帶有交易成本的魯棒兩階段的投資組合選擇的模型為 4. Aharon Ben-Tal, Tamar Margalit Arkadi Nemirovski給出了一個多階段的組合選擇問題的魯棒建模方法。假設有種類型的資產(chǎn)和現(xiàn)金。個投資階段。目標是控制這些資產(chǎn)的一個投資組合。表示投資組合中資產(chǎn)在階段開始時的數(shù)量?？?/p>

25、以有下列的方程給出：時，是來自前一個階段的數(shù)量，表示資產(chǎn)收益。表示在階段初買入的資產(chǎn)數(shù)量。表示在階段初賣出的資產(chǎn)數(shù)量。時，是從前一個階段得到的現(xiàn)金流；是在階段賣出資產(chǎn)得到的資產(chǎn)數(shù)量，表示交易成本表示在階段買入資產(chǎn)得到的資產(chǎn)數(shù)量，表示交易成本應該滿足約束假設約束為簡單的約束，即下界為0，上界為無窮大目標是極大化期末財富的總價值?？傻玫骄€性規(guī)劃模型為 令，其中，則新的規(guī)劃為 其中 數(shù)據(jù)的不確定性 決策向量不是實的，是的可測函數(shù)，當決策向量實施的時候，數(shù)據(jù)就是立即可知。 不確定線性規(guī)劃的魯棒規(guī)劃 為維的決策向量，為精確可知的目標，為不確定的約束矩陣。錐二次規(guī)劃， 是的期望，是隨機變量的協(xié)方差矩陣。是

26、隨機變量的協(xié)方差。. 錐規(guī)劃模型可以用已有的算法求解。4結(jié)論：這里給出了魯棒優(yōu)化的基本算法，最新的發(fā)展和在金融上的應用。今后的研究方向是對魯棒優(yōu)化算法本身的研究，另一個是將其用到金融上。參考文獻1A.L.Soyster. Convex programming and set-inclusive constraints and application to inexact linear programming. Operation Research,21:1154-1157,19732J.E.Falk. Exact solution of inexact linear programs. Ope

27、ration Research,24,17963A.Ben-Tal and A.Nemirovski. Robust convex optimization. Math.Oper.Res.23:769-805,19984A.Ben-Tal and A.Nemirovski. Robust solution of uncertain linear programs. Operation Research Letters,25,19995A.Ben-Tal and A.Nemirovski. Robust optimization-methodology and applications. Mat

28、h.Program,.Ser.B92:453-480,20026Shen Ruijun Zhang shuzhong Robust portfolio selection based on a muli-stage tree,European Journal of operation research,191:864-887,20087Mustafa C.Pinar Robust scenario optimization based on downside-risk measure for multi-period portfolio selection. OR spectrum,20058 Aharon Ben-Tal, Tamar Margalit Arkadi Nemirovski, robust modeling of multi-stage portfolio problems, draft paper9A.Ben-Tal A.Goryashko E.Guslitzer A.Nemirovski Adustable robust soltutions of uncertain linear programs Math