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

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

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

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

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

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

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

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

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

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

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

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

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

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

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