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

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

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

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

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

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

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

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

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