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

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

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

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

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

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

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

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

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