數(shù)據(jù)科學優(yōu)化方法 課件 第7、8章 共軛梯度方法、約束最優(yōu)化問題的最優(yōu)性理論

數(shù)據(jù)科學優(yōu)化方法Optimization

Method

in

Data

Science第7章共軛梯度方法7.1共軛方向方法7.2針對正定二次函數(shù)的共軛梯度方法7.3

非線性共軛梯度方法7.4數(shù)值實驗引入一個很自然的想法是構(gòu)造一種介于負梯度方法和牛頓方法之間的方法，使其既可以比負梯度方法的收斂速度快，又可以避免牛頓方法高昂的計算成本.本章介紹的共軛梯度方法正是這樣一種方法.關(guān)于無約束最優(yōu)化問題，我們已經(jīng)學習了一階方法(負梯度方法)和二階方法(牛頓方法).12在實際使用中，負梯度方法的收斂速度往往很慢牛頓方法的收斂速度雖然很快，但卻需要計算Hesse矩陣的逆.第7章共軛梯度方法7.1共軛方向方法7.2針對正定二次函數(shù)的共軛梯度方法7.3

非線性共軛梯度方法7.4數(shù)值實驗共軛方向方法7.1.1方法的引入

7.1.2共軛的定義及性質(zhì)7.1.3共軛方向方法的計算步驟及性質(zhì)方法的引入考慮極小化正定二次函數(shù)問題其中是對稱正定矩陣.當

是對角陣時，可以很容易地將原問題轉(zhuǎn)化為

個一元二次函數(shù)的最小化問題對

維問題，從出發(fā)，依次沿

個坐標軸方向作精確線搜索，便得到該問題最小值方法的引入圖7.1

沿負梯度方向的迭代路徑(實線)和沿坐標軸方向的迭代路徑(虛線)方法的引入圖7.1

沿負梯度方向的迭代路徑(實線)和沿坐標軸方向的迭代路徑(虛線)方法的引入當正定二次函數(shù)問題中的

不再是對角陣時，依次沿何種方向作精確線搜索能得到相同結(jié)果呢？設(shè)是實對稱矩陣，則具有如下性質(zhì)1.有個實特征根2.屬于不同特征值的特征向量正交3.可正交對角化根據(jù)該定理，從任意初始點出發(fā)，依次沿的

個正交特征向量方向做精確線搜索，便可得到正定二次函數(shù)問題的極小值.定理7.1.譜定理方法的引入圖7.2

沿負梯度方向的迭代路徑(實線)和沿正交特征向量方向的迭代路徑(虛線)方法的引入盡管根據(jù)譜定理可以解決正定二次函數(shù)的優(yōu)化問題，但求矩陣的特征值和特征向量需要付出較高的計算成本.為了能處理一般的最優(yōu)化問題，尤其是大規(guī)模最優(yōu)化問題，我們必須另外尋找合適的迭代方向.研究發(fā)現(xiàn)，共軛方向具備所要求的性質(zhì)共軛方向方法7.1.1方法的引入

7.1.2共軛的定義及性質(zhì)7.1.3共軛方向方法的計算步驟及性質(zhì)共軛的定義及性質(zhì)設(shè)為的對稱正定矩陣，是中的兩個非零向量，若則稱向量是的共軛方向，簡稱共軛的.設(shè)是中的一組非零向量，若則稱向量組是的兩兩共軛方向，簡稱

共軛的.定義7.1.共軛方向共軛的定義及性質(zhì)如果，則任意兩個

維非零向量是

共軛的.如果

，則共軛就是通常所說的正交.設(shè)為的對稱正定矩陣，如果是共軛的，則它們是線性無關(guān)的.設(shè)為的對稱正定矩陣，如果是共軛的，則共軛方向方法7.1.1方法的引入

7.1.2共軛的定義及性質(zhì)

7.1.3共軛方向方法的計算步驟及性質(zhì)共軛方向方法的計算步驟及性質(zhì)共軛方向方法：所有迭代方向都兩兩共軛的方法.算法7.1:共軛方向方法的計算步驟給定若滿足終止準則，則停止迭代;由線搜索確定步長因子令采用某種共軛方向法計算，轉(zhuǎn)步2共軛方向方法的計算步驟及性質(zhì)對于極小化正定二次函數(shù)問題，由精確線搜索確定的步長因子的顯式表達式為(7.2)其中定理7.2共軛方向方法的計算步驟及性質(zhì)在精確線搜索條件下，共軛方向方法具有二次終止性，即對于正定二次函數(shù)，方法能夠在有限步內(nèi)終止.對于極小化正定二次函數(shù)問題，由任意初始點

出發(fā)，采用精確線搜索的共軛方向方法至多經(jīng)

步就可收斂到目標函數(shù)的極小點.共軛方向方法的計算步驟及性質(zhì)證明：因為共軛方向線性無關(guān)，故它們可以張成一個n

維空間.于是,可將寫成共軛方向的線性組合上式兩邊左乘,由的共軛性得(7.3)共軛方向方法的計算步驟及性質(zhì)下面證明系數(shù)與(7.2)定義的步長

相等.注意到上式兩邊左乘,由的共軛性得因此，對比(7.2)和(7.3)，有，由此定理得證.共軛方向方法的計算步驟及性質(zhì)當為對角陣，每次沿坐標軸方向迭代可以依次確定極小

點

的一個分量.在個一維極小化后，迭代點達到正定二次函數(shù)在由坐標軸張成的子空間中的極小點.下面的定理表明這一結(jié)果適用于一般的正定二次函數(shù).共軛方向方法的計算步驟及性質(zhì)對于極小化正定二次函數(shù)問題，由任意初始點

出發(fā)，采用精確線搜索的共軛方向滿足(7.4)且上的極小點.定理7.3.子空間擴展定理共軛方向方法的計算步驟及性質(zhì)證明：我們只給出證明思路，具體證明留作習題1.將

改寫為

的線性組合，由共軛方向的定義即可證明出(7.4).2.只需證明當

時，.因為是二次函數(shù)，所以

就等于

的2階Taylor展式，再利用第一個結(jié)論就可以證明出第二個結(jié)論.第7章共軛梯度方法7.1共軛方向方法7.2針對正定二次函數(shù)的共軛梯度方法7.3

非線性共軛梯度方法7.4數(shù)值實驗針對正定二次函數(shù)的共軛梯度方法共軛梯度方法是一種共軛方向方法，由Hestenes和Stiefel獨立提出.方法的最大特點在于無需預(yù)先給定共軛方向，而是隨著迭代的進行不斷產(chǎn)生共軛方向.在每次迭代中，利用上一步迭代方向和目標函數(shù)在當前迭代點的梯度方向二者的線性組合構(gòu)造一個新方向，使其與前面所有迭代方向是Q共軛的.

該方法所需的存儲量小，計算簡便.針對正定二次函數(shù)的共軛梯度方法本節(jié)討論針對正定二次函數(shù)的共軛梯度方法（又稱線性共軛梯度方法）及性質(zhì)，下節(jié)討論針對一般非線性函數(shù)的共軛梯度方法.針對正定二次函數(shù)的共軛梯度方法7.2.1方法的推導

7.2.2方法的性質(zhì)

7.2.3預(yù)處理技術(shù)方法的推導在共軛梯度方法中，迭代方向為負梯度方向和前一個迭代方向的線性組合，即為了保證由于上式可以改寫為由（7.4）和（7.5），上式可進一步簡化為（7.5）方法的推導由于極小化正定二次函數(shù)問題等價于求解線性方程組，因此基于上式的共軛梯度方法也被稱為線性共軛梯度方法.方法的推導算法7.2:共軛梯度方法的計算步驟給定若滿足終止準則，則停止迭代計算

，轉(zhuǎn)步2針對正定二次函數(shù)的共軛梯度方法7.2.1方法的推導

7.2.2方法的性質(zhì)7.2.3預(yù)處理技術(shù)方法的性質(zhì)迭代方向是共軛的，故由定理7.2可知，方法最多在

步內(nèi)收斂.向量

是相互正交的.和均在度為

的Krylov空間中，其定義如下：定理7.4方法的性質(zhì)設(shè)是實對稱矩陣，,取則采用精確線搜索的共軛梯度方法在步內(nèi)終止,且對有共軛方向： (7.7)正交向量： (7.8)下降方向： (7.9)(7.10)(7.11)定理7.4方法的性質(zhì)設(shè)是實對稱矩陣，,取則采用精確線搜索的共軛梯度方法在步內(nèi)終止,且對有共軛方向： (7.7)正交向量： (7.8)下降方向： (7.9)(7.10)(7.11)①②③④⑤注：定理7.4的結(jié)論要求初始迭代方向取為負梯度方向，否則生成的迭代方向可能不共軛.方法的性質(zhì)例

考慮最優(yōu)化問題其中，選取初始點為初始迭代方向為故有采用精確線搜索方法得步長從而于是有方法的性質(zhì)證明：采用數(shù)學歸納法.當

，(7.7)成立.當

時，(7.10)和(7.11)自然成立.假設(shè)這三個等式對某個成立，證明對于

，這些等式亦成立.

對于(7.10)，先證明等式左邊集合包含于等式右邊集合.由歸納法假設(shè)知第二式兩邊左乘，得由于(7.12)故方法的性質(zhì)再利用歸納法假設(shè)(7.10)，可得(7.13)反之，由歸納法假設(shè)(7.11)，有由(7.12)有故再利用歸納法假設(shè)(7.10)，可得(7.14)(7.13)和(7.14)表明(7.10)對k+1成立.類似地，可以證明(7.11)也對k+1成立.方法的性質(zhì)接下來，證明(7.7)也對k+1成立.利用(7.5)，可得(7.15)由的定義知，當i=k時，上式右邊項等于零.當i<k，首先利用歸納法假設(shè)可知

是共軛的，故由定理7.3，可得(7.16)其次，重復(fù)利用(7.10)，對i=0,1,...,k?1，有(7.17)由(7.16)和(7.17)可得方法的性質(zhì)故(7.15)右邊第一項為零，又由歸納法假設(shè)知(7.15)右邊第二項也為零，從而

由此表明共軛梯度方法產(chǎn)生的迭代方向的確是共軛的，從而由定理7.2可知方法一定能在n

步內(nèi)終止.

然后，證明(7.7).因為迭代方向是共軛的，故由(7.4)可得

由(7.5)可知于是.由此可得.當

時，由于，又利用(7.4)，可得.

最后，由(7.4)和(7.5)可證出(7.9).

方法的性質(zhì)共軛梯度方法的收斂速度如下.定義其中和分別為矩陣最大和最小的特征根.可以證明和最速下降方法的收斂速度(定理4.6)相比，共軛梯度方法的收斂速度取決于而非7.2針對正定二次函數(shù)的共軛梯度方法7.2.1方法的推導

7.2.2方法的性質(zhì)7.2.3預(yù)處理技術(shù)預(yù)處理技術(shù)我們可以通過改善矩陣

條件數(shù)的方式提高共軛梯度方法的收斂速度，這種方式被稱為預(yù)處理.設(shè)

是一個非奇異矩陣，令等價于求解于是，共軛梯度方法的收斂速度將取決于

而非矩陣

的條件數(shù).因此能選擇合適的非奇異矩陣可以改善該方法的收斂速度.預(yù)處理技術(shù)定義即可得到下面的預(yù)處理共軛梯度方法7.3，并且算法7.2的性質(zhì)可以推廣到算法7.3.計算上需要多計算一個線性方程組預(yù)處理技術(shù)算法7.3:預(yù)處理共軛梯度方法的計算步驟給定令若滿足終止準則，則停止迭代;計算解，得

，轉(zhuǎn)步3第7章共軛梯度方法7.1共軛方向方法7.2針對正定二次函數(shù)的共軛梯度方法7.3

非線性共軛梯度方法7.4數(shù)值實驗非線性共軛梯度方法非線性共軛梯度方法的迭代方向仍是當前的負梯度方向與上一次迭代方向的線性組合：選取不同的，便得到不同的共軛梯度方法.其中，最為著名的兩個方法：FR方法PRP方法非線性共軛梯度方法7.3.1FR方法7.3.2

PRP方法7.3.3重啟共軛梯度方法7.3.4其他非線性共軛梯度方法FR方法算法7.4:FR方法給定若滿足終止準則，則停止迭代;用非精確線搜索求，令計算(7.21)(7.22)5.，轉(zhuǎn)步2FR方法FR方法是首個非線性共軛梯度方法.該方法在線性共軛梯度方法基礎(chǔ)上做了一處調(diào)整，即不再采用精確線搜索確定步長，而是改用非精確線搜索由于算法7.4每次迭代僅需要目標函數(shù)值和梯度值，未涉及矩陣存儲和計算，故非常適合求解大規(guī)模非線性最優(yōu)化問題.FR方法接下來討論FR方法的下降性.對于FR方法，如果步長滿足強Wolfe非精確線搜索準則，且，則迭代方向滿足因此，是下降方向.

定理7.5注：定理說明當使用強Wolfe非精確線搜索并保證

，得到的迭代方向是下降方向.（7.23）FR方法證明：用數(shù)學歸納法證明(7.23).當,,有故(7.23)成立.假設(shè)對任意k?1，(7.23)成立.由(7.21)和(7.22)有(7.24)由強Wolfe非精確線搜索準則知FR方法由(7.25)的第一個不等式與歸納假設(shè)知由(7.25)的第二個不等式與歸納假設(shè)知即(7.23)對k也成立，從而(7.23)成立.

由于

在上單調(diào)遞增，且任意有

因此，由(7.23)可知是下降方向。將上式與(7.24)相結(jié)合有(7.25)定理7.6FR方法接下來討論FR方法的收斂性.設(shè)在水平集上，有下界，梯度函數(shù)

滿足Lipschitz條件，則采用精確線搜索的FR方法產(chǎn)生的迭代序列，或者對某個有限有，或者FR方法證明：假定對所有k,由于故從而

是下降方向.由于是單調(diào)下降且有下界的序列，故

存在.由及L

有界,可知是有界點列，故存在收斂子列,這里是子序列的下標集.由于,故,從而由的連續(xù)性可知，對于,有類似地，也是有界點列，故存在，這里是

的子序列的下標集.于是，對于

，有（7.26）FR方法下面用反證法證明假定則存在一個方向使得對于充分小的

，有(7.27)由于

是由精確線搜索確定，于是有因此對于,令，并利用(7.27)得這與(7.26)矛盾.由此證明了FR方法關(guān)于FR方法的收斂速度，我們有以下結(jié)果：在定理7.6的條件下，采用精確線搜索的FR方法產(chǎn)生的迭代序列線性收斂到目標函數(shù)的極小點.非線性共軛梯度方法7.3.1FR方法7.3.2

PRP方法7.3.3重啟共軛梯度方法7.3.4其他非線性共軛梯度方法PRP方法將算法中7.4中的計算公式進行如下替換即得到PRP方法的計算步驟.對于正定二次函數(shù)，PRP方法等價于FR方法.對于一般非線性函數(shù)，數(shù)值實驗結(jié)果表明PRP方法比FR方法更加穩(wěn)健且有效.由于會出現(xiàn)取負值情況，導致相鄰迭代方向趨于相反方向，從而難以給出全局收斂定理.PRP方法將算法中7.4中的計算公式進行如下替換即得到PRP方法的計算步驟.PRP+方法將取為可以證明，對于一般非線性函數(shù)，在適當?shù)木€搜索條件下，PRP+方法的迭代方向為下降方向，且具有全局收斂性.7.3非線性共軛梯度方法7.3.1FR方法7.3.2

PRP方法7.3.3重啟共軛梯度方法7.3.4其他非線性共軛梯度方法重啟共軛梯度方法上節(jié)討論了極小化正定二次函數(shù)的共軛梯度方法.本節(jié)將其推廣到一般非線性函數(shù).求解一般非線性最優(yōu)化問題的共軛梯度方法被稱為非線性共軛梯度方法.

重啟共軛梯度方法上節(jié)討論了極小化正定二次函數(shù)的共軛梯度方法.本節(jié)將其推廣到一般非線性函數(shù).求解一般非線性最優(yōu)化問題的共軛梯度方法被稱為非線性共軛梯度方法.由Taylor定理可知，目標函數(shù)在極小點某個鄰域內(nèi)可以較好地被正定二次函數(shù)近似.由于線性共軛梯度方法的二次終止性需要初始迭代方向取為負梯度方向，故當?shù)M入到該鄰域內(nèi)，重新取負梯度方向為迭代方向，則其后的迭代方向接近于共軛方向.這樣可以使得方法具有較快的收斂速度.重啟共軛梯度方法算法7.

5:重啟共軛梯度方法給定若滿足終止準則，則停止迭代，;用一維線搜索求，計算

，若，令，轉(zhuǎn)步2；若，令，轉(zhuǎn)步2；計算，若

令轉(zhuǎn)步2；否則轉(zhuǎn)步3重啟共軛梯度方法

非線性共軛梯度方法7.3.1FR方法7.3.2

PRP方法7.3.3重啟共軛梯度方法7.3.4其他非線性共軛梯度方法其他非線性共軛梯度方法除前面介紹的FR方法和PRP方法外，本節(jié)再簡要介紹其他幾個具有代表性的非線性共軛梯度方法.1980年Fletcher提出的共軛下降（ConjugateDescent,CD）方法當使用強Wolfe非精確線搜索準則且

，共軛下降方法得到的迭代方向為下降方向.其他非線性共軛梯度方法除前面介紹的FR方法和PRP方法外，本節(jié)再簡要介紹其他幾個具有代表性的非線性共軛梯度方法.1995年戴彧虹和袁亞湘提出的DY(Dai-Yuan)方法當使用Wolfe非精確線搜索準則，該方法產(chǎn)生的迭代方向為下降方向，且方法具有全局收斂性.第7章共軛梯度方法7.1共軛方向方法7.2針對正定二次函數(shù)的共軛梯度方法7.3

非線性共軛梯度方法7.4數(shù)值實驗數(shù)值實驗在本小節(jié)中，我們應(yīng)用PRP方法求解上一章的6個典型最優(yōu)化問題以檢驗方法的有效性.迭代步長滿足Armijo線搜索準則迭代的終止準則為

最大迭代次數(shù)為10000.數(shù)值實驗問題

1全局最優(yōu)解為，最優(yōu)值為，考慮初始點，表7.1和圖7.3給出了迭代點信息.可以看出，PRP方法能較快收斂到最優(yōu)解。圖7.3PRP方法求解問題1的迭代點軌跡表7.1PRP方法求解問題1的部分迭代點信息數(shù)值實驗問題2全局最優(yōu)解為，最優(yōu)值為.以為初始點，PRP方法可以收斂到最優(yōu)解，但速度要明顯慢于BFGS方法（見圖7.4和表7.2）圖7.4PRP方法求解問題2的迭代點軌跡表7.2PRP方法求解問題2的部分迭代點信息數(shù)值實驗問題3全局最優(yōu)解為，最優(yōu)值為.當初始點為時，和最速下降方法類似，PRP方法也較難收斂(見圖7.5和表7.3).圖7.5PRP方法求解問題3的迭代點軌跡表7.3PRP方法求解問題3的部分迭代點信息數(shù)值實驗問題4全局最優(yōu)解為，最優(yōu)值為.當初始點時，PRP方法可以較快收斂到最優(yōu)解(見圖7.6和表7.4).圖7.6PRP方法求解問題4的迭代點軌跡表7.4PRP方法求解問題4的部分迭代點信息數(shù)值實驗問題5：全局最優(yōu)解為最優(yōu)值為PRP方法可以較快收斂到最優(yōu)解(見表7.5).表7.5PRP方法求解問題5的迭代點信息00.9487-0.63760.191310.3438-0.94260.102520.0197-1.00006.2365e-0333.8372e-06-1.00001.2134e-0642.8249e-17-1.00008.9332e-18數(shù)值實驗問題6：全局最優(yōu)解為最優(yōu)值為PRP方法表現(xiàn)差于BFGS方法，較難實現(xiàn)收斂.表7.6PRP方法求解問題6的迭代點信息01.581158.500051.0000

11.579953.800044.404721.579550.203438.465331.579647.141733.5037…………99990.00547.1535e-062.3184e-03100000.00537.1463e-062.3172e-07數(shù)據(jù)科學優(yōu)化方法Optimization

Method

in

Data

Science第8章約束最優(yōu)化問題的最優(yōu)性理論8.1約束最優(yōu)化問題的一般形式和定義8.2約束最優(yōu)化問題的一階最優(yōu)性條件8.3約束最優(yōu)化問題的二階最優(yōu)性條件8.4約束最優(yōu)化問題的對偶問題第8章約束最優(yōu)化問題的最優(yōu)性理論8.1約束最優(yōu)化問題的一般形式和定義8.2約束最優(yōu)化問題的一階最優(yōu)性條件8.3約束最優(yōu)化問題的二階最優(yōu)性條件8.4約束最優(yōu)化問題的對偶問題約束最優(yōu)化問題的一般形式和定義其中

，

均為

上的光滑實值函數(shù).對滿足約束條件的點稱為可行點，所有可行點的集合成為可行域，記為：考慮一般形式的約束最優(yōu)化問題約束最優(yōu)化問題的一般形式和定義約束條件其中

，

均為

上的光滑實值函數(shù).對滿足約束條件的點稱為可行點，所有可行點的集合成為可行域，記為：考慮一般形式的約束最優(yōu)化問題不等式約束等式約束約束最優(yōu)化問題的一般形式和定義對一般的約束最優(yōu)化問題，若，有

則稱為問題的全局最優(yōu)解.進一步，如果則稱為問題的嚴格全局最優(yōu)解.定義8.1.全局最優(yōu)解約束最優(yōu)化問題的一般形式和定義對一般的約束最優(yōu)化問題，若對于，存在的某個鄰域，有

則稱為問題的局部最優(yōu)解.進一步，如果則稱為問題的嚴格局部最優(yōu)解.定義8.2.局部最優(yōu)解約束最優(yōu)化問題的一般形式和定義除了嚴格局部最優(yōu)解之外還存在另外一種特殊局部最優(yōu)解：孤立局部最優(yōu)解注：孤立局部最優(yōu)解必是嚴格局部最優(yōu)解，反之則并不一定.對一般約束最優(yōu)化問題，若存在的一個鄰域，使得是內(nèi)唯一局部最優(yōu)解，則稱是問題的孤立局部最優(yōu)解定義8.3.孤立局部最優(yōu)解約束最優(yōu)化問題的一般形式和定義例8.1

考慮約束最優(yōu)化問題約束最優(yōu)化問題的一般形式和定義該問題有局部最優(yōu)解和全局最優(yōu)解,見圖8.1，虛線為目標函數(shù)等高線，實線為可行域，實心點為全局最優(yōu)解，空心點為局部最優(yōu)解圖8.1問題（8.1）目標函數(shù)的等高線和可行域約束最優(yōu)化問題的一般形式和定義約束最優(yōu)化問題的另一個重要概念是起作用約束對任何，稱集合為在點處的起作用約束集（或有效約束集、積極約束集），簡稱起作用集，稱為在點處的起作用約束，稱為在點處的不起作用約束.定義8.4.起作用約束集約束最優(yōu)化問題的一般形式和定義假定已知約束最優(yōu)化問題的起作用集為，此時不起作用約束可以忽略，則約束最優(yōu)化問題可以改寫為僅含等式約束的最優(yōu)化問題約束最優(yōu)化問題的一般形式和定義例8.2

考慮約束最優(yōu)化問題例8.2的最優(yōu)解，在最優(yōu)解處前兩個約束起作用，后兩個約束不起作用，故，去掉后兩個約束問題的解不變約束最優(yōu)化問題的一般形式和定義圖8.2問題（8.2）目標函數(shù)的等高線和可行域約束最優(yōu)化問題的一般形式和定義注：等式約束函數(shù)是線性函數(shù)、不等式約束函數(shù)是凹函數(shù)的約束構(gòu)成的可行域為凸集，凸優(yōu)化問題是求凸函數(shù)在凸集上的極值問題.設(shè)為凸函數(shù)，為線性函數(shù)，為凹函數(shù)，則稱問題是凸優(yōu)化（或凸規(guī)劃）問題.定義8.5.凸優(yōu)化問題約束最優(yōu)化問題的一般形式和定義設(shè)是定義在凸集上的凸函數(shù)，集合中是的局部最優(yōu)解，則必是的全局最優(yōu)解.定理8.1注：定理表明凸優(yōu)化問題的局部最優(yōu)解均為全局最優(yōu)解

約束最優(yōu)化問題的一般形式和定義因此對于，有由此可知，存在一個任意接近的點，其對應(yīng)的目標函數(shù)值更小.例如，對于收斂于的序列有.因此不是局部最優(yōu)解，與已知條件矛盾，定理得證.

約束最優(yōu)化問題的一般形式和定義第8章約束最優(yōu)化問題的最優(yōu)性理論8.1約束最優(yōu)化問題的一般形式和定義8.2約束最優(yōu)化問題的一階最優(yōu)性條件8.3約束最優(yōu)化問題的二階最優(yōu)性條件8.4約束最優(yōu)化問題的對偶問題約束最優(yōu)化問題的一階最優(yōu)性條件8.2.1三個約束最優(yōu)化問題的例子8.2.2可行方向和約束規(guī)范條件8.2.3一階最優(yōu)性條件例8.3

求解最優(yōu)化問題三個約束最優(yōu)化問題的例子等式約束的優(yōu)化問題解：根據(jù)一般約束最優(yōu)化問題的定義可以得到以下信息：最優(yōu)解以及對應(yīng)點的梯度為：三個約束最優(yōu)化問題的例子不難看出，在處與共線，故：其中.該例子中極大點處與共線，而其他點處并不共線.這意味著在這些點上總會有一個迭代方向使得迭代點依然在可行域之內(nèi)而目標函數(shù)值有所下降.例如對于圓周的右端點(1,0)，從該點出發(fā)沿順時針方向的迭代方向即滿足要求.三個約束最優(yōu)化問題的例子通過對目標函數(shù)和約束函數(shù)分別做一階泰勒近似，也可以得到在最優(yōu)解處，目標函數(shù)的梯度和等式約束的梯度共線的結(jié)論.

為了保證迭代點滿足，需要迭代方向滿足滿，對在點做一階泰勒近似，有因此三個約束最優(yōu)化問題的例子此時可以保證迭代點依然在可行域內(nèi).類似的對目標函數(shù)同樣進行一階泰勒近似為滿足迭代點處目標函數(shù)值減少，需要滿足若任意迭代方向不能同時滿足與，才可能是局部最優(yōu)解.只有二者共線時才可能出現(xiàn)不能同時滿足的情況.三個約束最優(yōu)化問題的例子為了簡化描述，引入Lagrange函數(shù)

其中，稱為的Lagrange乘子.由于，因此共線條件等價于上式表明可以通過尋找Lagrange函數(shù)的穩(wěn)定點來求解等式約束優(yōu)化問題.

三個約束最優(yōu)化問題的例子

注：由于極大點處共線條件同樣成立，故而

只是是等式約束最優(yōu)化問題的局部最優(yōu)解的必要非充分條件.三個約束最優(yōu)化問題的例子例8.4

求解最優(yōu)化問題三個約束最優(yōu)化問題的例子僅有一個不等式約束的優(yōu)化問題解：該問題的可行域為單位圓圓周和圓內(nèi).最優(yōu)解依舊是且仍然成立.區(qū)別于僅含等式的約束最優(yōu)化問題，Lagrange乘子的符號在此問題下至關(guān)重要.三個約束最優(yōu)化問題的例子采用例8.3中已經(jīng)使用過的分析思路，如果在可行點處存在迭代方向使得下一個迭代點在可行域內(nèi)且目標函數(shù)值下降則其必不是局部最優(yōu)解.在該問題下需要重新思考之處在于保證迭代點為可行點的條件，具體地，當依然為可行點，因此條件變?yōu)槿齻€約束最優(yōu)化問題的例子下面可以分兩個情形討論：情形1：位于可行域內(nèi)部，.令足夠小時則可以保證.如若令，當時，該迭代方向同時滿足與.當時則不存在滿足條件的迭代方向.

三個約束最優(yōu)化問題的例子情形2：位于可行域邊界，.此時原條件改變?yōu)?/p>

如右圖所示，上述兩不等式分別確定了半個平面，而只有當

時兩個半平面的交集才為空集.此時從處不存在同時滿足兩條件的迭代方向.此時需要要求.否則從圖中可知半平面的迭代方向均可滿足三個約束最優(yōu)化問題的例子用Lagrange函數(shù)總結(jié)上述兩種情況下的一階最優(yōu)性條件.當在點處不存在迭代方向，使得下一個迭代點依然在可行域內(nèi)且目標函數(shù)值有所下降，則

被稱為互補條件.該條件表明只有約束在處起作用時，才可能大于0.三個約束最優(yōu)化問題的例子例8.5

求解最優(yōu)化問題.三個約束最優(yōu)化問題的例子包含兩個不等式約束的優(yōu)化問題解：該問題的可行域變?yōu)樯习雸A，此時最優(yōu)解且兩個約束均起作用.采用例8.4類似的分析方法，若在處存在迭代方向滿足則一定不是該問題的局部最優(yōu)解.三個約束最優(yōu)化問題的例子對于該問題可以定義如下Lagrange函數(shù)其中為Lagrange乘子.于是可以推廣為兩個不等式的互補條件為上述三式共同構(gòu)成了該問題的一階最優(yōu)性條件.三個約束最優(yōu)化問題的例子驗證該問題的一階最優(yōu)性條件.在

處此時令則可使，故能夠滿足條件.下面考慮其他幾個可行點在

處兩約束均起作用.迭代方向

滿足條件

該點只有令條件才能成立，但，故一階最優(yōu)性條件無法同時滿足三個約束最優(yōu)化問題的例子在

處只有約束起作用.由于從該點出發(fā)的任意一小步均可實現(xiàn)，故條件可以簡化為：

容易看出滿足簡化后的條件.再考慮一階最優(yōu)性條件，由互補條件可知，于是

等價于

顯然并不存在能使該等式成立的.該點同樣不滿足一階最優(yōu)性條件.三個約束最優(yōu)化問題的例子約束最優(yōu)化問題的一階最優(yōu)性條件8.2.1三個約束最優(yōu)化問題的例子8.2.2可行方向和約束規(guī)范條件8.2.3一階最優(yōu)性條件可行方向和約束規(guī)范條件以上例子的分析方式需要線性化可以近似刻畫當前點附近可行域幾何特征時才有意義，因此我們需要對其做出必要假設(shè)，使得在點處的線性化近似與可行域一致.此類假設(shè)被稱為約束規(guī)范條件.為了定義約束規(guī)范條件我們需要先介紹兩類可行方向.可行方向和約束規(guī)范條件設(shè)為一般約束最優(yōu)化問題的可行點，若存在可行點序列，，和序列，使得：則稱為點處的序列可行方向,簡稱為可行方向.處的所有可行方向的集合記為定義8.6.可行方向注：可行方向不依賴于可行域的定義形式.如果為可行方向，則也是可行方向.可行方向和約束規(guī)范條件設(shè)為問題的可行點，起作用集為.如果則稱為點處的線性化可行方向.點處所有線性化可行方向的集合記為定義8.7.線性化可行方向注：線性化可行方向依賴于約束函數(shù)的具體定義.可行方向和約束規(guī)范條件例8.6

考慮如下最優(yōu)化問題在點

處的可行方向和線性化可行方向可行方向和約束規(guī)范條件解：該最優(yōu)化問題可行域為中心在原點，半徑為1的圓周.令易知是可行點且.進一步，有故為處的可行方向.沿著該可行方向目標函數(shù)值仍會繼續(xù)下降，故而必不是最優(yōu)解.可行方向和約束規(guī)范條件從相反方向可得到可行序列：令則可知為可行方向.利用可行方向的性質(zhì)，可以得到處可行方向的集合為：從定義8.7可知，當滿足時，為線性化可行方向，故處的線性化可行方向集合為：可行方向和約束規(guī)范條件在例8.6中，.然而這一結(jié)果并非總能成立.例如，我們將該問題的約束條件改為此時可行域未改變，相應(yīng)的可行方向集合未改變.由于故此時處的線性化可行方向集合,從而在點處，可行方向和約束規(guī)范條件可行點處的可行方向集合和線性化可行方向集合有如下關(guān)系：定理8.2注：從例8.6的討論中可以知道并不一定成立證明：設(shè)滿足定義8.6，即從而可以得到.下面證明..對任意，由泰勒定理有令，則可得到.可行方向和約束規(guī)范條件對任意的，有令則可得到.因此,可行方向和約束規(guī)范條件引入可行方向和線性化可行方向的目的是建立約束規(guī)范條件，從而建立最優(yōu)性條件.常用的一種為KT(Kuhn-Tucker)約束規(guī)范條件：.但KT約束規(guī)范條件不容易驗證.于是，我們給出如下容易驗證的線性無關(guān)約束規(guī)范條件(LICQ).可行方向和約束規(guī)范條件可行方向和約束規(guī)范條件給定點和起作用集，如果線性無關(guān)，則稱在點處線性無關(guān)約束規(guī)范（LICQ）成立.定義8.8.LICQ注:如果點處，LICQ條件成立，則，可行方向和約束規(guī)范條件若在可行點處LICQ條件成立，則定理8.3注:該定理說明線性無關(guān)約束規(guī)范強于KT條件.可行方向和約束規(guī)范條件設(shè)是一般約束最優(yōu)化問題的局部最優(yōu)解，則定理8.4證明：采用反證法.假設(shè)存在一個可行方向使得設(shè)是方向滿足定義8.6的序列.由和泰勒定理可知，對充分大的k有由于，故當，有因此,給定任意以為中心的鄰域,都可選取充分大的k使得在此鄰域內(nèi)，且,這與是局部最優(yōu)解矛盾.可行方向和約束規(guī)范條件定理8.4說明局部最優(yōu)解處沒有可行的下降方向.

上述命題逆命題不一定成立，即使對所有可行方向

，都有也可能不是局部最優(yōu)解.

可行方向和約束規(guī)范條件可行方向和約束規(guī)范條件例考慮如下約束最優(yōu)化問題該問題的最優(yōu)值為，對于原點，該點處的任何可行方向都必須滿足故但任取點處的目標函數(shù)值都小于原點處的函數(shù)值，因此原點不是局部最優(yōu)解.約束最優(yōu)化問題的一階最優(yōu)性條件8.2.1三個約束最優(yōu)化問題的例子8.2.2可行方向和約束規(guī)范條件8.2.3一階最優(yōu)性條件一階最優(yōu)性條件設(shè)為一般約束最優(yōu)化問題的局部最優(yōu)解，問題中的目標函數(shù)和約束函數(shù)均連續(xù)可微，且在點處約束規(guī)范條件LICQ成立，則存在Lagrange乘子，使得滿足其中為Lagrange函數(shù).定理8.5一階必要條件定理中的5個條件稱為KKT條件.滿足KKT條件的點稱為KKT點，相應(yīng)的稱為Lagrange乘子，稱為KKT對.注：對于最優(yōu)解，可能有很多滿足KKT條件.然而，可以證明，當LICQ條件成立時，是唯一的.一階最優(yōu)性條件穩(wěn)定條件可行條件非負條件互補條件定理中的5個條件稱為KKT條件.滿足KKT條件的點稱為KKT點，相應(yīng)的稱為Lagrange乘子，稱為KKT對.稱為互補條件，根據(jù)該條件可將改寫為當時，稱為嚴格互補條件.

滿足嚴格互補條件可使優(yōu)化方法收斂更快一階最優(yōu)性條件一階最優(yōu)性條件

歷史介紹一階最優(yōu)性條件

歷史介紹對于局部最優(yōu)解和給定的一個約束，就的兩種情況討論該約束不起作用，即.此時和對該約束并不敏感，微小擾動下仍為局部最優(yōu)解.由互補條件可得，由此可見該Lagrange乘子表明約束對于該問題的最優(yōu)解和最優(yōu)值并不重要.一階最優(yōu)性條件Lagrange乘子的意義該約束起作用，即.對該約束增加一個小擾動，例如將約束修改為.假設(shè)充分小，使得擾動后的最優(yōu)解起作用集和Lagrange乘子都不發(fā)生變化，此時可得從而根據(jù)有一階最優(yōu)性條件

令,有由此可見反映了最優(yōu)值對于約束的敏感程度.如果某些起作用約束對應(yīng)的Lagrange乘子為0，則微小擾動不會影響最優(yōu)值，此類約束稱為弱起作用約束.Lagrange乘子非零的起作用約束為強起作用約束.一階最優(yōu)性條件一階最優(yōu)性條件設(shè)和為n維向量，則集合為空集的充要條件是，存在，使得：引理8.1

Farkas引理為了證明KKT定理，我們需要引入Farkas引理.一階最優(yōu)性條件設(shè)和為n維向量，則集合為空集的充要條件是，存在，使得引理8.2.Farkas引理的推論將Farkas引理推廣到一般約束最優(yōu)化問題中的線性化可行下降方向集合可以得到引理8.2.證明：由于等價于故根據(jù)Farkas引理可知，存在使得其中一階最優(yōu)性條件一階最優(yōu)性條件設(shè)為一般約束最優(yōu)化問題問題的局部最優(yōu)解，問題中的目標函數(shù)和約束函數(shù)均連續(xù)可微，且在點處約束規(guī)范條件LICQ成立，則存在Lagrange乘子，使得滿足：其中為Lagrange函數(shù).定理8.5.一階必要條件證明：由于是問題的局部最優(yōu)解，故可行，從而成立.由定理8.4可知

.由于約束規(guī)范條件LICQ成立，故從而有由線性化可行方向的定義可知，集合是空集.一階最優(yōu)性條件利用引理8.2，存在和，使得再令，可得從而成立.一階最優(yōu)性條件一階最優(yōu)性條件例8.7

計算下列約束最優(yōu)化問題的所有KKT點解：該問題的Lagrange函數(shù)為KKT條件為當或，第一個條件不能滿足，故而進一步由互補條件可得，將其代入方程并考慮到，最終可求得一階最優(yōu)性條件一階最優(yōu)性條件設(shè)是一般約束最優(yōu)化問題的可行點，目標函數(shù)和約束函數(shù)均連續(xù)可微，且有則是問題的嚴格局部最優(yōu)解定理8.6.一階充分條件注：由于，因此如果把

換成，結(jié)論依然成立.證明：采用反證法.假設(shè)不是問題的嚴格局部最優(yōu)解，則存在一個可行點序列，其中，使得：定義由于有界，故有收斂子列.不妨設(shè)該子列為，且.由可行方向的定義有.此外：從而.令，得矛盾.一階最優(yōu)性條件第8章約束最優(yōu)化問題的最優(yōu)性理論8.1約束最優(yōu)化問題的一般形式和定義8.2約束最優(yōu)化問題的一階最優(yōu)性條件8.3約束最優(yōu)化問題的二階最優(yōu)性條件8.4約束最優(yōu)化問題的對偶問題約束最優(yōu)化問題的二階最優(yōu)性條件？約束最優(yōu)化的一階最優(yōu)性條件即KKT條件得到滿足時，從出發(fā)，沿任意線性化可行方向迭代會得到或?qū)τ诘诙N情況我們難以判斷目標函數(shù)值的變化.由此我們需要二階最優(yōu)化條件解決該問題.本節(jié)假設(shè)均為二階連續(xù)可微函數(shù)約束最優(yōu)化問題的二階最優(yōu)性條件首先對于給定的線性化可行方向集和滿足KKT條件的Lagrange乘子定義線性化可行方向集的子集.在點處，線性化可行方向集合的子集定義為定義8.9也稱為線性化零約束集合.不難發(fā)現(xiàn)，等價于

由互補條件可知，對于不起作用約束有

從而由KKT條件得約束最優(yōu)化問題的二階最優(yōu)性條件約束最優(yōu)化問題的二階最優(yōu)性條件設(shè)為一般約束最優(yōu)化問題的局部最優(yōu)解，且在點處約束規(guī)范條件LICQ成立，為相應(yīng)的Lagrange乘子，則定理8.7.二階必要條件證明：由于，故由定義8.6可知存在可行點序列，和序列，使得上式可以改寫為從而有結(jié)合的定義有

約束最優(yōu)化問題的二階最優(yōu)性條件另一方面，對進行二階泰勒展開由互補條件有，同時因為，可得進一步由于是局部最優(yōu)解，當k充分大時，有令，得約束最優(yōu)化問題的二階最優(yōu)性條件約束最優(yōu)化問題的二階最優(yōu)性條件設(shè)為一般約束最優(yōu)化問題的KKT點，為相應(yīng)的Lagrange乘子，若則是問題的嚴格局部最優(yōu)解定理8.8.二階充分條件注：定理8.8表明當時，KKT點就是一般約束最優(yōu)化問題的局部最優(yōu)解.證明：采用反證法.假設(shè)不是問題的嚴格局部最優(yōu)解，則存在一個可行點序列，其中，使得：定義由于有界，故有收斂子列.不妨設(shè)該子列為，且由可行方向的定義.此外由泰勒定理有從而令，得約束最優(yōu)化問題的二階最優(yōu)性條件下面就的兩種情況討論.情況1：若，則存在，使得而對于其他的，有因此，可得這與矛盾.約束最優(yōu)化問題的二階最優(yōu)性條件情況2：