第八章約束優(yōu)化最優(yōu)性條件

1、第八章 約束優(yōu)化最優(yōu)性條件8.1 約束優(yōu)化問(wèn)題一、 問(wèn)題基本形式 （8.1）特別地，當(dāng)為二次函數(shù)，而約束是線性約束時(shí)，稱為二次規(guī)劃。記 ，稱之為可行域（約束域）。，稱是在處的積極約束的指標(biāo)集。積極約束也稱有效約束，起作用約束或緊約束（active constraints or binding constraints）。應(yīng)該指出的是，如果是（1）的局部最優(yōu)解，且有某個(gè)，使得則將此約束去掉，仍是余下問(wèn)題的局部最優(yōu)解。事實(shí)上，若不是去掉此約束后所得問(wèn)題的局部極小點(diǎn)，則意味著，存在，使得，且，這里滿足新問(wèn)題的全部約束。注意到當(dāng)充分小時(shí)，由的連續(xù)性，必有，由此知是原問(wèn)題的可行解，但，這與是局部極小點(diǎn)矛盾

2、。因此如果有某種方式，可以知道在最優(yōu)解處的積極約束指標(biāo)集，則問(wèn)題可轉(zhuǎn)化為等式的約束問(wèn)題： （8.2）一般地，這個(gè)問(wèn)題較原問(wèn)題（8.1）要簡(jiǎn)單，但遺憾的是，我們無(wú)法預(yù)先知道。8.2 一階最優(yōu)性條件一、幾種可行方向定義8.1 設(shè)，是一非零向量。如果存在，使得，則稱是處的一個(gè)可行方向。在處的的所有可行方向的集合記為定義8.2 設(shè)，若滿足： （8.3） （8.4）則稱是處的線性化可行方向。在處的的所有線性化可行方向的集合記為。定義8.3 設(shè)，若存在序列和，使得對(duì)一切，有，且，則稱是處的序列可行方向。在處的的所有序列可行方向的集合記為。引理8.4 設(shè)，且所有約束函數(shù)都在處均可微，則有： （8.5）證明：

3、 對(duì)任何，由定義8.1可知，存在使得，令 ，和 則顯然有 ，且 ，因而，由的任意性，即知。 又對(duì)任何，如果，則顯然。假定，由定義8.3，存在序列和，使得，且和。由有，在上兩式的左右兩端除以，然后令趨于無(wú)窮，即得滿足 因而，由的任意性，即知，證畢。二、一階最優(yōu)性條件引理8.5 設(shè)是問(wèn)題（8.1）的局部極小點(diǎn)，若和都在處可微，則必有，。證明：對(duì)任何，存在序列和，使得，且和。由，而且是局部極小點(diǎn)，故對(duì)充分大的有：由上式可知，引理于是證畢。 引理8.5表明：在極小點(diǎn)處，所有的序列可行方向都不是下降方向。引理8.6 （Farkas引理）線性方程組和不等式組無(wú)解的充要條件是存在實(shí)數(shù)和非負(fù)實(shí)數(shù)使得： （8.

4、9）證明：假定（8.9）式成立，且，那么對(duì)任意滿足（8.6），（8.7）的，都有因而不等式組無(wú)解。另一方面，若不存在實(shí)數(shù)，非負(fù)實(shí)數(shù)，使（8.9）式成立?？紤]集合：易證是中的一個(gè)閉凸錐，且。由凸集分離定理：必存在，使得 （是一常數(shù)）由于，所以。又由于是錐，故，有，從而因而必有 再由 有 類似可得 ，亦即 由以上討論可見，是不等式組（8.6）（8.8）的一個(gè)解。注： 這里介紹的Farkas引理，以及其他教科書上給出的擇一定理、Motzkin定理與Gordan定理，均是由凸集分離定理得出的同一類定理，它們?cè)趯?dǎo)出約束最優(yōu)性條件方面起著至關(guān)重要的作用。定理8.7（Karush-Kuhn-Tucker定理

5、）設(shè)是（8.1）的局部極小點(diǎn)，若，則必存在，使得： （8.10）證明：由引理8.5，有，因而 ，有。由的定義，知 無(wú)解。由Farkas引理，知存在和，使得再令 ，即得，且滿足。注：1) 稱為L(zhǎng)agrange函數(shù)，稱為L(zhǎng)agrange乘子；2）（8.10）通常稱為問(wèn)題（8.1）的K-T-T條件（或K-T條件），而滿足（8.10）的點(diǎn)稱為K-T-T點(diǎn)（或K-T點(diǎn)），（8.10）中的第二式稱為互補(bǔ)松弛條件；3）當(dāng)約束規(guī)范性條件不成立時(shí)，局部極小點(diǎn)不一定是K-T點(diǎn)。三、的一些充分條件定理8.8 若所有的都是線性函數(shù)，則。證明：，有取，那么當(dāng)時(shí)，有當(dāng)時(shí)，有 而當(dāng)時(shí)，由知：當(dāng)充分大時(shí)（），有。即有 這表明

6、 即 再由，即得，證畢。定理8.8 若1) 線性無(wú)關(guān)； 2）集合非空。則。證明：先證 設(shè)是中任一向量，令是子空間的正交補(bǔ)中的標(biāo)準(zhǔn)正交基。（由，故與正交，因而上述生成子空間的維數(shù)為）。 考慮下面以為參數(shù)的非線性方程組 （8.11）它將確定以為參數(shù)的一個(gè)隱函數(shù)。由于在處，上述方程組的Jacobi矩陣非奇異，且是方程組的解。根據(jù)隱函數(shù)定理，對(duì)充分小的，必存在解且滿足。事實(shí)上，將方程組確定的隱函數(shù)對(duì)求導(dǎo)，有令，得上述方程組得系數(shù)矩陣非奇異，故有唯一解，又顯然方程組的解，因而有。下證當(dāng)充分小時(shí)，。事實(shí)上，由是由方程組（8.11）確定的隱函數(shù)，由方程組（8.11）的第一式知，當(dāng)時(shí)，由的定義，有 故當(dāng)充分小

7、時(shí)，有最后一個(gè)不等式是由于時(shí)，當(dāng)時(shí)，由。故當(dāng)充分?。ǎr(shí)，有 。因此有?，F(xiàn)取 則有 （，）由上面分析， 這表明 ，或 由是中任意向量，故。再由是閉集（可直接驗(yàn)證），故有注意到 從而得： ，定理證畢。定理8.9 若在處線性無(wú)關(guān)，則。證明：1）若是空集，則易知上一定理的條件滿足，從而結(jié)論成立。2） 若非空，那么對(duì)任何，由于線性無(wú)關(guān)，必存在，使得： （，），。 事實(shí)上，若記，則線性無(wú)關(guān)。記是的一組標(biāo)準(zhǔn)正交基。取則與正交，即與正交。因此有： 而 因而取 即滿足要求，對(duì)每個(gè)，均可仿此構(gòu)造出。令 ，易證：，即非空，由上一定理有：。注：定理8.9 是最重要、最常用的約束規(guī)范性條件。四、一階充分性條件定理8.

8、10 設(shè)，若和在處都可微，且，（） （8.12）則是問(wèn)題（8.1）的嚴(yán)格局部極小點(diǎn)。證明：假定（8.12）成立，而不是局部嚴(yán)格極小點(diǎn)，則存在，使得 （8.13）且有 不失一般性，可設(shè) （否則，取其收斂子序列）。令 即知 再由（8.13），有 其中，位于由與確定的線段上。進(jìn)而有在上式中，令，即得這與（8.12）矛盾。定理于是證畢。推論 設(shè)，若和在處都可微，且，（） （8.14）則是問(wèn)題（8.1）的嚴(yán)格局部極小點(diǎn)。五、Fritz-John必要條件定理8.11 設(shè)，在上連續(xù)可微，若是問(wèn)題（8.1）的局部極小點(diǎn)，則必存在，使得注：1) Fritz-John必要條件對(duì)約束不附加任何條件（即不要求約束滿足

9、約束規(guī)范性條件）；2) 時(shí)，是K-T條件；時(shí)，目標(biāo)函數(shù)從條件中消失。這是條件僅描述了約束條件之間的關(guān)系，使得到的Fritz-John點(diǎn)不是極小點(diǎn)的可能性增大，則也是Fritz-John條件不如Karush-Kuhn-Tucker條件使用廣泛的原因；3）證明可參見俞玉森等著數(shù)學(xué)規(guī)劃原理和方法。8.3 二階最優(yōu)性條件1）若且，都有，則由前一節(jié)的充分性條件知是局部嚴(yán)格極小點(diǎn)；2）若，使，則是處的一個(gè)下降可行方向，因而不是極小點(diǎn)。以上兩種情形都可得到確定的結(jié)果，但若這兩種情形都不出現(xiàn)，即 ， （8.15）且 ，（）使 （8.16）如果仍假定約束規(guī)范性條件滿足，那么類似定理8.7的證明可知是K-T點(diǎn)。記

10、是相應(yīng)的Lagrange乘子，顯然對(duì)使（8.16）成立的，有 。由，知，由上式可推出，。由此，引入下述定義定義8.12 設(shè)是K-T點(diǎn)，是相應(yīng)的Lagrange乘子，若，且滿足： 則稱是在處的線性化零約束方向。處所有線性化零約束方向記為。若處的Lagrange乘子唯一，則簡(jiǎn)記為。定義8.13 設(shè)是K-T點(diǎn)，是相應(yīng)的Lagrange乘子，如果存在向量序列和數(shù)列，使得 ，且有，則稱是在處的序列零約束方向，處的序列零約束方向的集合記為。由定義顯然有： 且類似于 有 下面證明這一結(jié)論。事實(shí)上，任取，由的定義知，存在，（）使 ，且 （這里，對(duì)應(yīng)的） 。將在處展開，則有1）若， 兩邊除，令，得2）若，類似可

11、得： 故有 由的任意性，有 。 注：1）；2）若，則存在，使得且，；，。二階最優(yōu)性條件定理8.14 設(shè)是局部極小點(diǎn)，是對(duì)應(yīng)的Lagrange乘子，則必有，使得，其中是Lagrange函數(shù)。（二階必要條件）證明：（略）定理8.15 設(shè)是一個(gè)K-T點(diǎn)，是對(duì)應(yīng)的Lagrange乘子。如果，則是局部嚴(yán)格極小點(diǎn)。（二階充分條件）證明：（略）注：1）一階充分性條件與二階充分性條件不是誰(shuí)比誰(shuí)弱的關(guān)系，彼此之間不存在簡(jiǎn)單的邏輯蘊(yùn)含。2）對(duì)一階充分性條件，。若出現(xiàn)某些，使，這時(shí)一階條件無(wú)效，可以轉(zhuǎn)而考察二階條件。8.4 凸規(guī)劃問(wèn)題定義8.16 若為凸集，為上的凸函數(shù)，則稱 （8.17）為凸規(guī)劃。在 （8.18）

12、中，若，均為凸函數(shù)，則為凸集，從而上述問(wèn)題為凸規(guī)劃問(wèn)題。注：在（8.18）中沒有考慮等式約束。事實(shí)上，在凸規(guī)劃問(wèn)題中，若包含等式約束，則該約束必為線性約束，因而為簡(jiǎn)單計(jì)，假定不含等式約束，對(duì)于包含等式約束的凸規(guī)劃問(wèn)題，所有討論只須稍作修正，則同樣有效。定理8.17 若在（8.18）中，均為凸函數(shù)，則其任何局部最優(yōu)解均為全局最優(yōu)解。證明：設(shè)為局部最優(yōu)解，若它不是全局最優(yōu)解，則必存，使得，有 當(dāng)時(shí)，落入的鄰域，但這與為局部最優(yōu)解矛盾，所以必為全局最優(yōu)。定理8.18 若為嚴(yán)格凸函數(shù)，而均為凸函數(shù)。若（8.18）有最優(yōu)解，則必唯一。證明：設(shè)是（8.18）的最優(yōu)解，而是另一最優(yōu)解。于是，因而有 這與為最

13、優(yōu)解矛盾，故最優(yōu)解唯一。定理8.19 設(shè)，均為凸函數(shù)，且在可微，又是問(wèn)題的K-T點(diǎn)，則是全局最優(yōu)解。證明：由在上凸，故，有再由的凸性，有當(dāng)時(shí)，而，故有，而當(dāng)時(shí)，由互補(bǔ)松弛條件，有，故有 因此有 所以是全局最優(yōu)解。8.5 凸規(guī)劃的對(duì)偶理論和線性規(guī)劃一樣，對(duì)偶理論在非線性規(guī)劃的理論與算法研究中也起著重要作用。由于構(gòu)造對(duì)偶問(wèn)題的不同方法，因而有不同的對(duì)偶理論。如Rockafellare對(duì)偶理論，Wolfe對(duì)偶理論，F(xiàn)enchel對(duì)偶理論。這里只介紹Wolfe對(duì)偶理論，一方面是因?yàn)樗容^簡(jiǎn)單，從計(jì)算的觀點(diǎn)看較為方便。另一方面，它也是目前文獻(xiàn)中最常采用的對(duì)偶形式。考慮非線性規(guī)劃問(wèn)題（NLP）： 記，稱函

14、數(shù)： 為對(duì)偶目標(biāo)函數(shù)，而稱問(wèn)題（DNLP） 對(duì)原問(wèn)題的對(duì)偶問(wèn)題。對(duì)一般非線性規(guī)劃問(wèn)題，對(duì)偶問(wèn)題的形式比較復(fù)雜，較難處理。但當(dāng)，均為上的凸函數(shù)時(shí)，由于為凸函數(shù)，而且，其中由解出。因而對(duì)偶問(wèn)題可化為（DNLP1）：對(duì)偶理論設(shè)原問(wèn)題為： 對(duì)偶問(wèn)題為： 若是原問(wèn)題的可行解，是對(duì)偶問(wèn)題的可行解，則有，即總有，這就是所謂弱對(duì)偶定理。若進(jìn)一步有，即，則與是分別是原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解。這就是所謂強(qiáng)對(duì)偶定理。8.6 鞍點(diǎn)問(wèn)題對(duì)任一非線性規(guī)劃問(wèn)題，可以考慮下面三個(gè)密切相關(guān)的問(wèn)題。1）原始不等式約束問(wèn)題（PP） 2） 廣義Lagrange問(wèn)題（K-T條件）記 3）鞍點(diǎn)問(wèn)題（SP）求，（），使得，及都有，稱為的鞍點(diǎn)。定理8.20 設(shè)，可微，是（PP）的最優(yōu)解。若在處滿足約束規(guī)范性條件，則必存在Lagrange乘子，使得是