ch6常用約束最優(yōu)化方法

1、第6章 常用約束最優(yōu)化方法 1本節(jié)主要考察帶有約束條件的非線性規(guī)劃問題。 稱問題(MP)為數(shù)學規(guī)劃(Mathematical Programming)。 (MP)稱 為不等式約束, 為等式約束。 稱集合 為問題(MP)的可行域。 若問題(MP)中的f, gi是凸函數(shù), hj是線性函數(shù), 則稱問題(MP)為凸規(guī)劃。 26.1.1 不等式約束問題的最優(yōu)性條件 考察最優(yōu)化問題 記 , 稱為問題(6.1.1)的可行域 (6.1.1)定義6.1.1 設 , 若對某個i有g(shù)i(x*)=0, 稱gi(x)0為點x*處的起作用約束, 也稱為有效約束, 積極約束(Active Constraint)。 記 為起

2、作用約束下標集。 36.1 最優(yōu)性條件 若 , 則稱 為點x*處的不起作用約束。其幾何意義如圖所示。在 處 是起作用約束, 是不起作用約束。在 處 均是不起作用約束。 4定義6.1.2 設 , 對于向量p0若存在實數(shù) 使 則稱向量p為x*處關(guān)于區(qū)域D的可行方向, 若p既是可行方向又是下降方向, 則稱p為可行下降方向。 5 在研究某點處的可行方向時, 只需考察這一點處的起作用約束即可, 對不起作用約束可以暫時不考慮。 對起作用的約束來說, 當變量x沿某些方向作微小的移動時仍然滿足約束條件, 而沿另外一些方向作微小的移動時, 無論移動是多么的微小都將違背約束條件。對不起作用的約束來說, 變量x沿任

3、何方向作微小移動都能滿足約束條件。例6.1.1 用圖解法求下列問題的最優(yōu)解，指出最優(yōu)解處的起作用約束及目標函數(shù)的最優(yōu)值。 (1)(2)解： (1)原問題可以化為： 6最優(yōu)解 , 最優(yōu)值 。 在x*處是起作用約束。 如圖所示。 7(2)原問題可化為 最優(yōu)解 , 最優(yōu)值 。 在x*處是起作用約束。 8定理6.1.1(Fritz-John必要條件)設 在x*處可微, 在x*處連續(xù), 若x*是不等式約束問題(6.1.1)的局部最優(yōu)解, 則存在不全為零的數(shù) 使 【日】Masao Fukushima著，林貴華譯，非線性最優(yōu)化基礎，科學出版社，2011年5月 9例6.1.2 驗證最優(yōu)化問題 在最優(yōu)解 處的F

4、ritz-John條件成立 解:在 處 是起作用約束, 即 且 取 , 便有Fritz-John條件成立。 10 在Fritz-John必要條件中, 若 則Fritz-John條件中就沒有目標函數(shù)的信息了, 這樣的Fritz-John條件就沒有多大的價值, 為了保證 , 需對約束條件加以適當?shù)南拗茥l件, 稱之為約束規(guī)格(Constraint qualification)。在非線性規(guī)劃的研究中, 有著各種不同的約束規(guī)格, 如果增加起作用約束的梯度向量線性無關(guān)的約束規(guī)格, 就得出著名Kuhn-Tucker條件。它是Kuhn和Tucker在1951年提出的, 簡稱為K-T條件。 11定理6.1.2(

5、Kuhn-Tucker必要條件) 設 在x*處可微, 在x* 處連續(xù), 線性無關(guān), 若x*是不等式約束問題 (6.1.1) 的局部最優(yōu)解, 則存在 使 12 在定理6.1.2中, 若 在x*處也可微, 則有等價形式的Kuhn-Tucker條件稱滿足K-T條件的可行點為K-T點。 例6.1.3 對不等式約束問題 考察點 , 是否是K-T點？ 解: 經(jīng)驗證x(1), x(2)是可行點 由于在x(1)處只有g(shù)2(x)0是起作用約束, 此時有 13方程組 無解, 故x(1)不是K-T點。 在x(2)處, 均是起作用約束, 且 線性無關(guān), 由 有方程組 解之有 故x(2)是K-T點。 14定理6.1.3

6、(充分條件) 設不等式約束問題(6.1.1)中, 是凸函數(shù), 和f在點x*處可微, 在x*處連續(xù), 且x*是K-T點, 則x*是(6.1.1)的全局最優(yōu)解。 156.1.2 等式約束問題的最優(yōu)性條件考查最優(yōu)化問題 (6.1.2)對等式約束問題(6.1.2)可以轉(zhuǎn)化為不等式約束問題來考慮 16(6.1.1)的結(jié)論可平移到(6.1.3)中來, 并得到(6.1.2)的相應結(jié)論。(6.1.2)也采用Lagrange乘數(shù)法來求解。 (6.1.3)定義3.2.3 稱為等式約束問題(6.1.2)的Lagrange函數(shù)。其中 =(1, 2, , l)T 稱為Lagrange乘子, 17記稱 為h(x)的Jac

7、obi矩陣。定義6.1.4 若 滿足: , 則 稱為等式約束問題(6.1.3)的Lagrange點。設等式約束問題 (6.1.2) 中f, hj(j=1,2,l)在x*處的某個鄰域內(nèi)可微, h(x)的Jacobi矩陣在x*處的秩為l, 若x*是 (6.1.2) 的局部最優(yōu)解, 則存在 使 18定理6.1.4(必要條件)設等式約束問題(6.1.2)中f, hj(j=1,2,l)二階連續(xù)可微, 若存在 使得其中 ; 則x*是等式約束問題(6.1.2)的嚴格局部最優(yōu)解。 19定理6.1.5(充分條件)例6.1.4 求解 20解：原問題可化為： 有 令 有 設向量 滿足 , 則有 21此時 由定理6.

8、1.5知(1,2)T是問題的嚴格局部最優(yōu)解。 6.1.3 混合約束問題的最優(yōu)性條件現(xiàn)在考查既含不等式約束又含等式約束的最優(yōu)化問題 22記定理6.1.6(Fritz John必要條件) 設混合約束問題(6.1.4)中的 在點x*處可微, 在x*點處連續(xù), 在點x*處連續(xù)可微, 若x*是(6.1.4)的局部最優(yōu)解, 則存在數(shù):使 23 在定理6.1.6中, 若還有條件, 在點x*處可微, 則Fritz-John條件可改寫為設混合約束問題中 在點x*處可微, 在點x*處連續(xù), 在點x*處連續(xù)可微, 且 線性無關(guān), 若x*是(MP) 的局部最優(yōu)解, 則存在 使 24定理6.1.7 (Kuhn-Tuck

9、er必要條件) 在定理6.1.7中若還有條件 在點x*處可微, 則Kuhn-Tucker條件可改寫為： 25設混合約束問題(6.1.4)中的 在點x*處可微, 若x*滿足(6.1.4) 的 Kuhn-Tucker 條件, 并且 是凸函數(shù), 是線性函數(shù), 則x*是(6.1.4)的全局最優(yōu)解。 定理6.1.8(充分條件)例6.1.5 求解解： 26由Kuhn-Tucker條件有： 27解此方程組得解 由于f(x), g(x)是凸函數(shù), h(x)是線性函數(shù), 而且x*是Kuhn-Tucker點, 故由定理6.1.8知(1, 1)T 是問題的全局最優(yōu)解。6.2 罰函數(shù)法 罰函數(shù)法又稱為序列無約束極小化

10、方法(Sequential Unconstrained Minimization Technique), 簡稱SUMT。其基本思想是:利用問題中的約束函數(shù)作出適當?shù)膽土P函數(shù)(Penalty function), 由此構(gòu)造出帶參數(shù)的輔助函數(shù), 將約束問題轉(zhuǎn)化為求解一系列無約束最優(yōu)化問題。 286.2.1 外罰函數(shù)法(外點法) 該方法的基本思想是迭代點在可行域的外部移動, 隨著迭代次數(shù)的增加, “懲罰”也愈增大, 以迫使迭代點向可行域接近。 如對不等式約束問題 (6.2.1)構(gòu)造輔助函數(shù) (6.2.2)對等式約束問題 (6.2.3) 29構(gòu)造輔助函數(shù) (6.2.4)對混合約束問題 (6.2.5)構(gòu)

11、造輔助函數(shù) (6.2.6)其中 為充分大的正數(shù), 這樣就將約束問題轉(zhuǎn)化為求解無約束問題:(6.2.7) 30 稱為罰參數(shù), 當x為可行點時, F(x,)=f(x)。當x不是可行點時, 在x處輔助函數(shù)中的懲罰項是很大的數(shù), 它的存在是對脫離可行域的點的一種懲罰, 其作用是在最優(yōu)化過程中迫使迭代點靠近可行域, 這樣求解無約束最優(yōu)化問題便能得到約束問題的近似解, 而且罰參數(shù)的值越大, 近似程度就越好。 31 在實際計算中, 罰參數(shù)的選擇十分重要。若太大, 就會給無約束問題的求解帶來困難, 若太小則懲罰的力度不夠, 將使無約束問題的解與約束問題解之間誤差達不到要求, 因此實用中的罰參數(shù)常取為遞增且趨于

12、無窮大的正數(shù)列k, 如取初始罰參數(shù)00 和增大系數(shù)2 , 則 32其中 迭代的終止條件可取:或終止條件為: 算法(外罰函數(shù)法) 1. 選擇初始點x(0), 罰參數(shù)列k, 誤差0, k1 2. 構(gòu)造輔助函數(shù)3. 用某種無約束最優(yōu)化算法, 以x(k-1)為初值求解 得最優(yōu)解x(k)。4. 若x(k)滿足終止條件, 停止計算并輸出x*=x(k)。否則 令kk+1, 轉(zhuǎn)2。 33定理6.2.1 設f(x), gi(x), hj(x)(i=1, 2, , m; j=1, 2, , l)連續(xù), 約束問題(6.2.5)存在最優(yōu)解, 若x(k)是由外罰函數(shù)法產(chǎn)生的無窮點列, 并且x*為其極限點, 則x*是約束

13、問題(6.2.5)的最優(yōu)解。 34解: 構(gòu)造輔助函數(shù) 由 有: 令 有: 該問題的準確解為(0.25,0.75)T; 現(xiàn)取k=0.14k-1例6.2.1 求解 迭代次數(shù)kx(k)10.1(0.071429,0.214286)T20.4(0.153846,0.461538)T31.6(0.216216,0.648649)T46.4(0.240602,0.721804)T525.6(0.247582,0.742747)T6102.4(0.249391,0.748173)T7409.6(0.249898,0.749542)T81638.4(0.249962,0.749886)T96553.6(0.2

14、49990,0.749971)T1026214.4(0.249998,0.749993)T 356.2.2 內(nèi)罰函數(shù)法(內(nèi)點法) 內(nèi)罰函數(shù)法又稱為內(nèi)點法, 障礙函數(shù)法, 該方法是從滿足約束條件的可行域的內(nèi)點開始迭代, 并且對企圖穿越可行域的邊界的點予以“懲罰”。而且迭代點愈接近邊界, “懲罰”就越大, 從而保證迭代點的可行性。此時輔助函數(shù)中懲罰項的作用相當于在可行域的邊界設置障礙, 不讓可行點穿越到可行域之外, 因此又叫障礙函數(shù)法。 36內(nèi)點法只適合于解不等式約束問題 (6.2.8)記 或 稱B(x)為內(nèi)罰函數(shù), 也稱為障礙函數(shù)(Barrier function) 。 37記 稱D0為可行域

15、的內(nèi)部, 記為intD1。構(gòu)造輔助函數(shù) 參數(shù)d0稱為罰參數(shù), 實用中罰參數(shù)取為單調(diào)減小的正數(shù)列dk, 常取d00,2, 令 初始點x(0)必須選在可行域的內(nèi)部, 終止條件可取為: 或 38算法(內(nèi)罰函數(shù)法)1. 選初始點x(0)D0, 罰參數(shù)列dk, 誤差0, 令k1。 2. 構(gòu)造輔助函數(shù)或 3. 選用某種無約束非線性規(guī)劃方法, 以x(k-1)為初值求 解 得最優(yōu)解x(k)。4. 若x(k)滿足終止條件, 停止計算并輸出最優(yōu)解x*=x(k)。 否則令kk+1轉(zhuǎn)2。 39定理6.2.2 設f(x), gi(x)(i=1, 2, , m)連續(xù), 約束問題(6.2.8)存在最優(yōu)解, 若x(k)是由內(nèi)

16、罰函數(shù)法產(chǎn)生的無窮點列, 并且x*為其極限點, 則x*是約束問題(6.2.5)的最優(yōu)解。例6.2.2 求解 解: 構(gòu)造輔助函數(shù) 由 有 (當dk0+時) 迭代次數(shù)dkx(k)11(1.4142360,1.0000000)T20.1(1.1472697,0.3162277)T30.01(1.0488088,0.1000000)T40.001(1.0156883,0.0316227)T50.0001(1.0049876,0.0100000)T60.00001(1.0001581,0.0003162)T70.000001(1.0004999.0.0010000)T80.0000001(1.00015

17、81,0.0003162)T90.00000001(1.0000499,0.0001000)T100.000000001(1.0000158,0.0000316)T用解析法求最優(yōu)解非常困難, 現(xiàn)取dk=10-(k-1), 得前10次計算結(jié)果為: 6.3 乘子法 乘子法是將罰函數(shù)法和Lagrange函數(shù)結(jié)合起來, 構(gòu)造出更適當?shù)妮o助函數(shù), 并借助Lagrange 乘子的迭代進行求解。 1. 等式約束問題的乘子法(P-H乘子法) 考察等式約束問題:其中f, hj(j=1, 2, , l)是二階連續(xù)函數(shù)。 (6.3.1)構(gòu)造輔助函數(shù) (6.3.2) 41 42其中: 輔助函數(shù)F(x,)與Lagran

18、ge函數(shù)相比增加了懲罰項 , 而與罰函數(shù)相比又增加了乘子項Th(x), 這使得輔助函數(shù)與Lagrange函數(shù)和罰函數(shù)相比具有不同的性態(tài), 而且對輔助函數(shù)來說, 只須取足夠大的罰參數(shù), 不必讓+就可通過求解無約束問題(6.3.2)來得到等式約束問題(6.3.1)的局部最優(yōu)解。 定理6.3.1 設x*是等式約束問題的局部最優(yōu)解, *是相應的最優(yōu)Lagrange乘子, 即:則存在00, 使得對所有的0, x*是F(x,*,)的嚴格局部極小點。 反之, 若存在 , 滿足 , 且對某個 , 為 的無約束極小值點, 而且又滿足二階充分條件, 則 是等式約束問題的嚴格局部最優(yōu)解。 43且對每個滿足 的非零向

19、量p, 均有二階充分條件成立, 即 44 由定理6.3.1的結(jié)論可知, 若知道了最優(yōu)乘子*, 則只需取充分大的罰參數(shù), 就可通過求F(x, *, )的極小值點來得到等式約束問題的最優(yōu)解, 但在應用中最優(yōu)乘子*一般難于得到,所以在實用中, 先給定充分大的和初始估計 , 然后在迭代過程中逐步修正, 使趨于* 。 假設在第k次迭代中Lagrange乘子向量的估計值為 , 罰參數(shù)取 , 得到 的極小值點為 , 此時有: 45若 線性無關(guān), 則x(k)為等式約束問題(6.3.1)的最優(yōu)解就應該有K-T條件成立, 即比較上面二式的結(jié)果就有:所以有迭代公式: 這樣就可能有: 若(k)不收斂, 或者收斂速度慢

20、, 就增大罰參數(shù), 再進行新的迭代, 收斂的快慢常用 來判斷。 46算法(P-H方法)1. 給出初值x(0), 初始估計(1), 罰參數(shù), 誤差 0, 常數(shù) 。 2. 以x(k-1)為初值, 求解無約束問題 得最優(yōu)解x(k)。 3. 若 或 , 停止計算, 輸出近似 解x*=x(k); 否則轉(zhuǎn)4。 4. 若 , 令 , 轉(zhuǎn)5。 5. 計算 轉(zhuǎn)2。 47例6.3.1 用乘子法求解 解: 構(gòu)造輔助函數(shù) 由 得最優(yōu)解 現(xiàn)取 48迭代次數(shù)(k)x(k)10(0.0714285,0.2142857)T2-0.0714285(0.1813186,0.5439559)T3-0.1813186(0.24071

21、87,0.7221562)T4-0.2407187(0.2496510,0.7489532)T5-0.2496510(0.2499966,0.7499898)T6-0.2499966(0.2499999,0.7499999)T6.3.2. 不等式約束問題的乘子法(Rockafellar乘子法) 引入松弛變量y=(y1, y2, , ym)T。將不等式約束問題化為等式約束問題 構(gòu)造輔助函數(shù)為: 49 該方法是Rockafellar在1973年提出的, 考察不等式約束問題:將不等式約束問題轉(zhuǎn)化為無約束問題: 將輔助函數(shù)配方得: 50為使輔助函數(shù)F(x,y,)達到極小, 取代入輔助函數(shù)中有: 將不等

22、式約束問題轉(zhuǎn)化為求解無約束問題:由等式約束計算乘子的公式： 51代入（1），可得而 521. 給出初值x(0), 初始估計(1), 罰參數(shù), 誤差0, 常數(shù) 。 算法(Rockafellar乘子法) 終止條件：4. 若 ，轉(zhuǎn)向5，否則令, ，轉(zhuǎn)5。5. 計算 轉(zhuǎn)2 532. 以x(k-1)為初值, 求解無約束問題 得最優(yōu)解x(k)。3. 按式（2）計算 ，若 ，則 為近似最優(yōu)解，停止計算，否則轉(zhuǎn)向4例6.3.2 用Rockafellar乘子法求解 解: 構(gòu)造輔助函數(shù)為: 54由 有: 取 , 數(shù)值計算結(jié)果如下表: 55迭代次數(shù)(k)x(k)11(0.65,0.325)T21.3(0.665,0

23、.3325)T31.33(0.6665,0.33325)T41.333(0.66665,0.333325)T51.3333(0.666665,0.3333325)T61.33333(0.6666665,0.33333325)T71.333333(0.66666667,0.333333333)T6.3.3. 混合約束問題的乘子法(PHR法)構(gòu)造輔助函數(shù)為: 56 該方法是Rockafellar在PH算法的基礎上提出的。考察混合約束最優(yōu)化問題:迭代過程中, 取充分大的 , 并不斷地修正乘子 和 , 修正公式為: 實用中罰參數(shù) 也可取為不斷增加的數(shù)列 。 57 數(shù)值試驗的結(jié)果表明, 乘子法克服了罰函

24、數(shù)法的病態(tài)性質(zhì), 它比罰函數(shù)法優(yōu)越, 收斂速度快, 目前是求解約束最優(yōu)化問題的最好算法之一。6.4 可行方向法 可行方向法的特點是: 在可行的迭代點處不斷地構(gòu)造適當?shù)目尚邢陆捣较颉?6.4.1 Frank-Wolfe方法 其中f是連續(xù)可微的非線性函數(shù): 該方法是Frank和Wolfe于1956年提出的求解線性約束的一種算法, 考察線性約束的非線性規(guī)劃問題 (6.4.1) 58記 Frank-wolfe法的基本思想是: 將目標函數(shù)f(x)線性化, 通過求解線性規(guī)劃來得到可行下降方向, 并沿此方向在可行域內(nèi)作一維搜索。 假設 是第k次近似解, 將f(x)在x(k)處進行一階Taylor展開有: 由

25、此構(gòu)造線性規(guī)劃: 假設該線性規(guī)劃有最優(yōu)解y(k), 則有(6.4.2) 59定理6.4.1 設f(x)連續(xù)可微, , y(k)是相應線性規(guī)劃問題(6.4.2)的解, 則有: 當 時, x(k)是最優(yōu)化問題 (6.4.1)的K-T點。 (2) 當 時, 向量 是f(x)在點x(k)處關(guān)于可行域D的可行下降方向。 60算法(Frank-Wolfe法) 1. 給定初始可行點x(0), 誤差0, k0。 2. 構(gòu)造線性規(guī)劃 并求得最優(yōu)解y(k)。3. 若 , 停止計算, 輸出解x*=x(k)。 否則轉(zhuǎn)4。 4. 從x(k)出發(fā)沿方向pk=y(k)-x(k)進行一維搜索 5. 令 ; 轉(zhuǎn)2。 61定理6

26、.4.2 設f(x)連續(xù)可微, D有界, , x(k)是由Frank-Wolfe法得到的點列, 則當x(k)是有限點列時, 其最后一個點x*是問題 (6.4.1)的K-T點。(2) 當x(k)是無限點列時, 它必有極限點, 并且其極限 點 是問題(6.4.1)的K-T點。 62 例6.4.1 利用Frank-Wolfe方法求解 解：取初值x(0)=(0, 0)T, 誤差=10-6第一輪迭代: 構(gòu)造近似線性規(guī)劃 63求解此線性規(guī)劃得解 由于 , 構(gòu)造可行下降方向 一維搜索求解: 得步長 64第二輪迭代: 構(gòu)造近似線性規(guī)劃 求解此線性規(guī)劃得y(1)=(0, 1)T。由于 , 構(gòu)造可行下降方向 一維搜索求解 得步長 65第三輪迭代: 構(gòu)造近似線性規(guī)劃 得最優(yōu)解 由于 , 停止計算輸出最優(yōu)解 x(2)是問題的K-T點。而且由于問題是凸規(guī)劃, 故x(2)又是問題的整體最優(yōu)解。 66 Frank-Wolfe法將問題歸結(jié)為求解一系列輔助線性規(guī)劃問題, 方法簡單方便。但是由于該方法是一種可行方向法, 在每次迭代中, 搜索方向總是指向某個極點, 并且當?shù)c接近收斂時, 搜索方向與目標函數(shù)的梯度向量正交。由前面無約束問題的結(jié)論可知, 這種搜索方向不是最好的下降方向, 因此算法收斂較慢。但該種方法對某些問題, 如研究交通問題時, 能得到較好的計算結(jié)果。因此Frank