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

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

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

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

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

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

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

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