非線性規(guī)劃1約束極值問題

1、第四章 非線性規(guī)劃間接解法是將約束優(yōu)化問題轉(zhuǎn)化為一系列無約束優(yōu)化問題來解的一種方法。由于這類方法可以選用有效的無約束優(yōu)化方法，且易于處理同時(shí)具有不等式約束和等式約束的問題，因而在工程優(yōu)化中得到了廣泛的應(yīng)用。直接解法是在滿足不等式約束的可行設(shè)汁區(qū)域內(nèi)直接按索問題的約束最優(yōu)解。第一節(jié) 目標(biāo)函數(shù)的約束極值問題所謂約束優(yōu)化設(shè)計(jì)問題的最優(yōu)性條件就是指在滿足等式和不等式約束條件下，其目標(biāo)函數(shù)值最小的點(diǎn)必須滿足的條件，須注意的是，這只是對(duì)約束的局部最優(yōu)解而言。對(duì)于帶有約束條件的目標(biāo)函數(shù)，其求最優(yōu)解的過程可歸結(jié)為：一、約束與方向的定義一）起作用約束與松弛約束對(duì)于一個(gè)不等式約束來說，如果所討論的設(shè)計(jì)點(diǎn)使該約束(

2、或者說當(dāng)時(shí)正處在該約束的邊界上)時(shí)，則稱這個(gè)約束是點(diǎn)的一個(gè)起作用約束或緊約束，而其他滿足的約束稱為松弛約束。當(dāng)一個(gè)設(shè)計(jì)點(diǎn)同時(shí)有幾個(gè)約束起作用時(shí)，即可定義起作用約束集合為其意義是對(duì)點(diǎn)此時(shí)所有起作用約束下標(biāo)的集合。二）冗余約束如果一個(gè)不等式約束條件的約束面(即)對(duì)可行域的大小不發(fā)生影響，或是約冗余約束束面不與可行域D相交，即此約束稱為冗余約束。三）可行方向可行方向：一個(gè)設(shè)計(jì)點(diǎn)在可行域內(nèi)，沿某一個(gè)方向S移動(dòng)，仍可得到一個(gè)屬于可行域的新點(diǎn)，則稱該方向?yàn)榭尚蟹较颉?）設(shè)計(jì)點(diǎn)為自由點(diǎn)設(shè)計(jì)點(diǎn)在可行域內(nèi)是一個(gè)自由點(diǎn)，在各個(gè)方向上都可以作出移動(dòng)得到新點(diǎn)仍屬于可行域，如圖所示。2）設(shè)計(jì)點(diǎn)為約束邊界點(diǎn)當(dāng)設(shè)計(jì)點(diǎn)處于起

3、作用約束上時(shí)，它的移動(dòng)就會(huì)受到可行性的限制。此時(shí)，點(diǎn)的可行方向S必滿足條件： （解釋：，）可行方向當(dāng)時(shí)，方向S是約束函數(shù)在點(diǎn)處的切線方向，即。當(dāng)某個(gè)設(shè)計(jì)點(diǎn)x同時(shí)有幾個(gè)約束起作用時(shí)(如圖中的x點(diǎn)是約束和約束約束面的交點(diǎn))，其可行方向集合為：即圖中陰影部分的任一方向都是可行方向。同理，對(duì)于有不等式約束起作用約束集合和等式約束的情況，其可行方向的集合為：四）下降可行方向沿某一個(gè)可行方向S移動(dòng)一個(gè)微小距離0，有,（亦即f（）的方向?qū)?shù)小于0），則稱S為下降可行方向。對(duì)于一個(gè)求目標(biāo)函數(shù)極小化問題，當(dāng)沿某個(gè)可行方向向量作出微小的移動(dòng)時(shí)，其目標(biāo)函數(shù)的變化為：對(duì)于充分小，若成立，則不是函數(shù)的局部極小點(diǎn)，因?yàn)檠?/p>

4、著S方向存在目標(biāo)函數(shù)值更小的點(diǎn)。反之，若對(duì)于任何可行方向S均有 成立，則是函數(shù)的局部極小點(diǎn)，因?yàn)檠刂我釹方向找不到一個(gè)目標(biāo)函數(shù)值更小的點(diǎn)。剛好是上式的一種極限情況。根據(jù)以上分析，對(duì)于點(diǎn)的可行方向，若滿足（或，此時(shí)方向向量與負(fù)梯度方向夾角小于）的條件，則稱此可行方向S為目標(biāo)函數(shù)的下降可行方向，并定義 為點(diǎn)的目標(biāo)函數(shù)下降可行方向集合。二、約束問題的最優(yōu)解條件一）約束極值問題的不同情況在約束條件下的優(yōu)化問題比無約束條件下的優(yōu)化問題更為復(fù)雜，因?yàn)榧s束最優(yōu)點(diǎn)不僅與目標(biāo)函數(shù)本身的性質(zhì)有關(guān)，而且還與約束函數(shù)的性質(zhì)有關(guān)。在存在約束的條件下，為了要滿足約束條件的限制，其最優(yōu)點(diǎn)即約束最優(yōu)點(diǎn)，不一定是目標(biāo)函數(shù)的自

5、然極值點(diǎn)，如圖所示。約束問題最優(yōu)點(diǎn)可能出現(xiàn)兩種情況：一種是最優(yōu)點(diǎn)在可行域的內(nèi)部，即最優(yōu)點(diǎn)是個(gè)內(nèi)點(diǎn)，此時(shí)的所有約束均為不起支配作用，這就是說，目標(biāo)函數(shù)無約束極小點(diǎn)也就是約束最優(yōu)點(diǎn)；（無約束極值）另一種情況是最優(yōu)點(diǎn)在可行域的邊界上，對(duì)于這種情況，其極值條件不僅與目標(biāo)函數(shù)而且也與約束集合的性質(zhì)有關(guān)，即該點(diǎn)既在起作用約束的約束面上，又是目標(biāo)函數(shù)值最小的點(diǎn)。（約束極值）二）約束極值的必要條件庫恩-塔克條件點(diǎn)成為約束最優(yōu)點(diǎn)的必要條件為：是否存在一個(gè)可行方向，使得，若存在，則不是。或者：在點(diǎn)周圍是否存在下降可行方向，用集合的形式表示為：1.只有一個(gè)起作用約束條件的情況從設(shè)計(jì)空間的幾何意義可以很清楚的了解到這

6、一點(diǎn)。在圖a中，目標(biāo)函數(shù)和約束函數(shù)均為凸函數(shù)，僅有一個(gè)起作用的約束，在存在一個(gè)可行方向向量S，使得（或）成立，S就是一個(gè)可行下降方向，不是約束最優(yōu)點(diǎn)。目標(biāo)函數(shù)在該點(diǎn)處沿約束面的切線方向的方向?qū)?shù)或變化率不等于零，不穩(wěn)定點(diǎn)在圖b中，在不存在一個(gè)可行方向向量S，使得（或）成立，因此是一個(gè)局部約束最優(yōu)點(diǎn)。此處是目標(biāo)函數(shù)等值線與約束函數(shù)邊界的切點(diǎn)，在該點(diǎn)處約束函數(shù)的梯度向量與目標(biāo)函數(shù)的負(fù)梯度向量重合。目標(biāo)函數(shù)在該點(diǎn)處沿約束面的切線方向的方向?qū)?shù)或變化率等于零。2.有兩個(gè)起作用的約束條件的情況圖a，為非約束最優(yōu)點(diǎn)，位于和構(gòu)成的夾角之外。圖b，為約束最優(yōu)點(diǎn)，位于和構(gòu)成的夾角之內(nèi)。這時(shí)，可以表示為和的線性組

7、合：3.一般情況將上述條件推廣到一般情況，表述如下：設(shè)某一設(shè)計(jì)點(diǎn)有q個(gè)起作用約束，也就是在q個(gè)約束面的交集上。為局部最優(yōu)點(diǎn)的必要條件是：目標(biāo)函數(shù)負(fù)梯度可以表示成所有起作用約束的線性組合，即：這就是約束優(yōu)化問題最優(yōu)解的必要條件庫恩-塔克條件（Kuhn-Tucker condition）4. 庫恩-塔克條件的幾何意義庫恩-塔克條件的幾何意義如圖，起作用約束的梯度向量，在設(shè)計(jì)空間內(nèi)構(gòu)成一個(gè)椎體，目標(biāo)函數(shù)的負(fù)梯度方向應(yīng)包含在此椎體內(nèi)。庫恩-塔克條件判定的只是局部最優(yōu)點(diǎn)，只有當(dāng)目標(biāo)函數(shù)和約束函數(shù)均為凸函數(shù)時(shí)（即所謂的凸規(guī)劃問題），判定的條件極值點(diǎn)才是全域最優(yōu)點(diǎn)，并且?guī)於?塔克條件也才是充分條件。庫恩-塔

8、克條件的重要性在于：（1）可以通過這個(gè)條件檢驗(yàn)是否為條件極值點(diǎn)；（2）可以檢驗(yàn)一種搜索方法是否合理，如果用這種方法求得的最優(yōu)點(diǎn)符合K-T條件，則該方法可以認(rèn)為是可行的。三）k-T條件的算例作業(yè)：三、約束優(yōu)化迭代終止準(zhǔn)則庫恩-塔克條件： （i=1,2,3, ,n）用矩陣形式表示：令令 r為起作用約束的數(shù)目 令 于是庫恩-塔克條件可寫為方程組這樣得到了n個(gè)方程，而未知數(shù)只有r個(gè)，r0時(shí)，則設(shè)計(jì)點(diǎn)為約束極值點(diǎn)。因此，可以通過求解D的值來判斷。將公式進(jìn)行變換，求取D的表達(dá)式： （左乘） （） （左乘，注意逆矩陣存在的條件）對(duì)上式進(jìn)行討論：（1）若D=0（零向量），且Ci0時(shí)（i=1,2,3, ,r），則設(shè)計(jì)點(diǎn)為局部最優(yōu)點(diǎn)，如果問題是凸規(guī)劃，則為全局最優(yōu)點(diǎn)；（2）若D0，則該點(diǎn)不是最優(yōu)點(diǎn)。（3）若D=0