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

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

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

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

4、，因為沿著S方向存在目標(biāo)函數(shù)值更小的點(diǎn)。反之，若對于任何可行方向S均有成立，則是函數(shù)的局部極小點(diǎn)，因為沿著任意S方向找不到一個目標(biāo)函數(shù)值更小的點(diǎn)。剛好是上式的一種極限情況。根據(jù)以上分析，對于點(diǎn)的可行方向，若滿足（或，此時方向向量與負(fù)梯度方向夾角小于）的條件，則稱此可行方向S為目標(biāo)函數(shù)的下降可行方向，并定義為點(diǎn)的目標(biāo)函數(shù)下降可行方向集合。二、約束問題的最優(yōu)解條件一）約束極值問題的不同情況在約束條件下的優(yōu)化問題比無約束條件下的優(yōu)化問題更為復(fù)雜，因為約束最優(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)是個內(nèi)點(diǎn)，此時的所有約束均為不起支配作用，這就是說，目標(biāo)函數(shù)無約束極小點(diǎn)也就是約束最優(yōu)點(diǎn)；（無約束極值）另一種情況是最優(yōu)點(diǎn)在可行域的邊界上，對于這種情況，其極值條件不僅與目標(biāo)函數(shù)而且也與約束集合的性質(zhì)有關(guān)，即該點(diǎn)既在起作用約束的約束面上，又是目標(biāo)函數(shù)值最小的點(diǎn)。（約束極值）二）約束極值的必要條件庫恩-塔克條件點(diǎn)成為約束最優(yōu)點(diǎn)的必要條件為：是否存在一個可行方向，使得，若存在，則不是。或者：在點(diǎn)周圍是否存在下降可行方向，用集合的形式表示為：1.只有一個起作用約束條件的情況從設(shè)計空間的幾何意義可以很清楚的了解

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

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

8、-塔克條件的重要性在于：（1）可以通過這個條件檢驗是否為條件極值點(diǎn)；（2）可以檢驗一種搜索方法是否合理，如果用這種方法求得的最優(yōu)點(diǎn)符合K-T條件，則該方法可以認(rèn)為是可行的。三）k-T條件的算例作業(yè)：三、約束優(yōu)化迭代終止準(zhǔn)則庫恩-塔克條件： （i=1,2,3, ,n）用矩陣形式表示：令令 r為起作用約束的數(shù)目令 于是庫恩-塔克條件可寫為方程組這樣得到了n個方程，而未知數(shù)只有r個，r<n是一個超靜定方程。這樣可能出現(xiàn)三種情況：（1）有唯一解；（2）無解（即不存在滿足所有這些方程的乘子）；（3）方程的解是不定的，無窮個解（1）（2）是正常預(yù)料中的結(jié)果，而（3）則是一種當(dāng)起作用約束的梯度向量不完全獨(dú)立時出現(xiàn)的情況。引入公式 （D為補(bǔ)償向量）且令 （D與所有起作用約束正交）這樣，可以得到K-T條件的另一種描述方法：D=0（零向量），且Ci>0時，則設(shè)計點(diǎn)為約束極值點(diǎn)。因此，可以通過求解D的值來判斷。將公式進(jìn)行變換，求取D的表達(dá)式： （左乘） （）（左乘，注意逆矩陣存在的條件）對上式進(jìn)行討論：（1）若D=0（零向量），且Ci>0時（i=1,2,3, ,r），則設(shè)計點(diǎn)為局部最優(yōu)點(diǎn)，如果問題是凸規(guī)劃，則為全局最優(yōu)點(diǎn)；（2）若D0，則該點(diǎn)不是最優(yōu)點(diǎn)。（3）若D=