最優(yōu)化方法及應用_郭科_約束問題的最優(yōu)性條件

1、2.7約束問題的最優(yōu)性條件所謂最優(yōu)性條件就是最優(yōu)化問題的目標函數(shù)與約束函數(shù)在最優(yōu)點處滿足的充要條件這種條件對于最優(yōu)化算法的終止判定和最優(yōu)化理論推證都是至關重要的最優(yōu)性必要條件是指在最優(yōu)點處滿足哪些條件；充分條件是指滿足哪些條件的點是最優(yōu)點本節(jié)僅講述最基本的結(jié)論一、約束最優(yōu)解對約束優(yōu)化問題的求解，其目的是在由約束條件所規(guī)定的可行域D內(nèi)，尋求一個目標函數(shù)值最小的點X及其函數(shù)值)(Xf這樣的解))((XfX稱為約束最優(yōu)解約束最優(yōu)點除了可能落在

2、可行域D內(nèi)的情況外，更常常是在約束邊界上或等式約束曲面上，因此它的定義及它的一階必要條件與無約束優(yōu)化問題不同（一）約束優(yōu)化問題的類型約束優(yōu)化問題根據(jù)約束條件類型的不同分為三種，其數(shù)學模型如下：（1）不等式約束優(yōu)化問題（IP型）min()..()012ifXstgXil???，，，，（2.16）（2）等式約束優(yōu)化問題（EP型）min()..()012jfXsthXjm???，，，，，（3）一般約束優(yōu)化問題（GP型）min()()012..

3、()012ijfXgXilsthXjm???????????，，，，，，，，，，（二）約束優(yōu)化問題的局部解與全局解按一般約束優(yōu)化問題，其可行域為210)(210)(|mjXhliXgXDji，，，，；，，，，???????若對某可行點X存在0??，當X與它鄰域的點X之距離???||||XX時，總有)()(XfXf?則稱X為該約束優(yōu)化問題的一個局部最優(yōu)解下面以一個簡單例子說明設有??????????????，，09)2()(02)(..)

4、1()(min222122221xxXhxXgtsxxXf該問題的幾何圖形如圖2.8所示從圖上的目標函數(shù)等值線和不等式約束與等式約束的函數(shù)曲線可寫出它的兩個局部最優(yōu)解TTXX]05[]01[21，，，???這是因為在1X點鄰域的任一滿足約束的點X，都有)()(1XfXf?；同理，2X亦然圖2.9圖2.9（a）是最優(yōu)點X在可行域內(nèi)部的一種情況在此種情形下，X點的全部約束函數(shù)值)(Xgi均大于零)321(，，?i，所以這組約束條件對其最優(yōu)點

5、X都不起作用換句話說，如果除掉全部約束，其最優(yōu)點也仍是同一個X點因此這種約束優(yōu)化問題與無約束優(yōu)化問題是等價的圖2.9（b）所示的約束最優(yōu)點X在)(1Xg的邊界曲線與目標函數(shù)等值線的切點處此時，0)(0)(0)(321???XgXgXg，，，所以)(1Xg是起作用約束，而其余的兩個是不起作用約束既然約束最優(yōu)點X是目標函數(shù)等值線與)(1Xg邊界的切點，則在X點處目標函數(shù)的梯度)(Xf?與約束函數(shù)梯度矢量)(1Xg?必共線，而且方向一致若取非

6、負乘子01??，則在X處存在如下關系0)()(11????XgXf?另一種情況如圖2.9（c）所示當前迭代點kX在兩約束交點上，該點目標函數(shù)的梯度矢量)(kXf?夾于兩約束函數(shù)的梯度矢量)()(21kkXgXg??，之間顯然，在kX點鄰近的可行域內(nèi)部不存在目標函數(shù)值比)(kXf更小的可行點因此，點kX就是約束最優(yōu)點，記作X由圖可知，此時kX點目標函數(shù)的梯度)(kXf?可表達為約束函數(shù)梯度)(1kXg?和)(2kXg?的線性組合若用X代替

7、kX即有)()()(2211XgXgXf???????成立，且式中的乘子1?和2?必為非負總結(jié)以上各種情況，最優(yōu)解的一階必要條件為??????????????????，，，，210)(00)()(211iXgXgXfiiii??對于（2.16）IP型約束問題的一階必要條件討論如下：設最優(yōu)點X位于j個約束邊界的匯交處，則這j個約束條件組成一個起作用的約束集按上面的分析，對于X點必有下式成立??????????????????，，，，，，j