最優(yōu)化方法4 - 約束最優(yōu)化 (1)

《最優(yōu)化方法4 - 約束最優(yōu)化 (1)》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、最優(yōu)化–約束1最優(yōu)化方法及應(yīng)用OptimizationMethodsandTheirApplications約束最優(yōu)化Constrainedoptimization2017年秋季提綱約束最優(yōu)化問(wèn)題的一般形式約束優(yōu)化問(wèn)題局部解的一階必要條件Kuhn-Tucker條件典型的約束最優(yōu)化方法罰函數(shù)法復(fù)合形法其可行域?yàn)椋浩淇尚杏驗(yàn)椋浩淇尚杏驗(yàn)椋阂话慵s束優(yōu)化問(wèn)題，其約束包含不等式約束和等式約束．起作用約束在可行點(diǎn)處，如果有，則該約束稱(chēng)可行點(diǎn)的起作用約束；不起作用約束如果有，則該約束稱(chēng)可行點(diǎn)的不起作用約束．對(duì)于等式約束，

2、顯然在任意可行點(diǎn)處的等式約束都是起作用約束．在某個(gè)可行點(diǎn)處，起作用約束在的鄰域內(nèi)起到限制可行域范圍的作用，而不起作用約束在處的鄰域內(nèi)就不產(chǎn)生影響．因此，應(yīng)把注意力集中在起作用約束上．起作用約束和不起作用約束例：具有三個(gè)不等式約束的二維最優(yōu)化問(wèn)題（a）是最優(yōu)點(diǎn)在可行域內(nèi)部的一種情況．在此種情形下，點(diǎn)的全部約束函數(shù)值均大于零，所以這組約束條件對(duì)其最優(yōu)點(diǎn)都不起作用．換句話(huà)說(shuō)，如果除掉全部約束，其最優(yōu)點(diǎn)也仍是同一個(gè)點(diǎn)．因此這種約束優(yōu)化問(wèn)題IP型約束問(wèn)題的一階必要條件與無(wú)約束優(yōu)化問(wèn)題是等價(jià)的．（b）約束最優(yōu)點(diǎn)在的邊界

3、曲線(xiàn)與目標(biāo)函數(shù)等值線(xiàn)的切點(diǎn)處．此時(shí)，，，，所以是起作用約束，而其余的兩個(gè)是不起作用約束．既然約束最優(yōu)點(diǎn)是目標(biāo)函數(shù)等值線(xiàn)與邊界的切點(diǎn)，則在點(diǎn)處目標(biāo)函數(shù)的梯度與約束函數(shù)梯度矢量必共線(xiàn)，而且方向一致．若取非負(fù)乘子，則在處存在如下關(guān)系（c）當(dāng)前迭代點(diǎn)在兩約束交點(diǎn)上，該點(diǎn)目標(biāo)函數(shù)的梯度矢量夾于兩約束函數(shù)的梯度矢量，之間．顯然，在點(diǎn)鄰近的可行域內(nèi)部不存在目標(biāo)函數(shù)值比更小的可行點(diǎn)．因此，點(diǎn)就是約束最優(yōu)點(diǎn)，記作．由圖可知，此時(shí)點(diǎn)目標(biāo)函數(shù)的梯度可表達(dá)為約束函數(shù)梯度和的線(xiàn)性組合．若用代替即有成立，且式中的乘子和必為非負(fù).總結(jié)以

4、上各種情況，最優(yōu)解的一階必要條件為IP型約束問(wèn)題的一階必要條件將以上分析推廣至一般情況，并且把個(gè)約束全部考慮進(jìn)去，取不起作用約束的相應(yīng)乘子為零，則IP問(wèn)題的最優(yōu)解的一階必要條件為其中是最優(yōu)點(diǎn)。因?yàn)樵趯?shí)際求解過(guò)程中，并不能預(yù)先知道最優(yōu)點(diǎn)位于哪一個(gè)或哪幾個(gè)約束邊界的匯交處．為此，把個(gè)約束全部考慮進(jìn)去，并取不起作用約束的相應(yīng)乘子為零。對(duì)于起作用約束，必有，因此式中的第四式成立；對(duì)于不起作用約束，雖然而必有IP型約束問(wèn)題的一階必要條件EP問(wèn)題中，等式約束曲線(xiàn)是它的可行域，而且目標(biāo)函數(shù)等值線(xiàn)與約束曲線(xiàn)的切點(diǎn)是該約束問(wèn)

5、題的最優(yōu)解．在點(diǎn)處，目標(biāo)函數(shù)的梯度與約束函數(shù)的梯度共線(xiàn)．因此，在最優(yōu)點(diǎn)處一定存在一個(gè)乘子，使得成立。對(duì)于一般的維等式約束優(yōu)化問(wèn)題，為其解的一階必要條件為EP型約束問(wèn)題的一階必要條件由上述不等式約束優(yōu)化與等式約束優(yōu)化問(wèn)題的一階必要條件，可以推出一般約束優(yōu)化問(wèn)題的條件．為其解的一階必要條件應(yīng)為GP型約束問(wèn)題的一階必要條件函數(shù)稱(chēng)為關(guān)于GP型問(wèn)題的廣義拉格朗日函數(shù)，式中為拉格朗日乘子．由于引入拉格朗日函數(shù)，一階必要條件中的第一式可寫(xiě)為GP型問(wèn)題的廣義拉格朗日函數(shù)在優(yōu)化實(shí)用計(jì)算中，常常需要判斷某可行迭代點(diǎn)是否可作為約

6、束最優(yōu)點(diǎn)輸出而結(jié)束迭代，或者對(duì)此輸出的可行結(jié)果進(jìn)行檢查，觀察它是否已滿(mǎn)足約束最優(yōu)解的必要條件，這種判斷或檢驗(yàn)通常借助于Kuhn—Tucker條件進(jìn)行．Kuhn-Tucker條件如果是一個(gè)局部極小點(diǎn)，且各梯度矢量組成線(xiàn)性無(wú)關(guān)的矢量系，那么必存在一組非負(fù)乘子，使得成立。滿(mǎn)足這一條件的（）稱(chēng)為一個(gè)K-T點(diǎn).IP型問(wèn)題的Kuhn-Tucker條件應(yīng)用Kuhn-Tucker條件檢驗(yàn)?zāi)车c(diǎn)是否為約束最優(yōu)點(diǎn)的具體作法可按下述步驟進(jìn)行：（1）檢驗(yàn)是否為可行點(diǎn)．為此需要計(jì)算處的諸約束函數(shù)值，若是可行點(diǎn)，則（2）選出可行點(diǎn)處

7、的起作用約束．前面已求得個(gè)值，其中等于零或相當(dāng)接近零的約束就是起作用約束．把這些起作用約束重新編排成序列，（3）計(jì)算點(diǎn)目標(biāo)函數(shù)的梯度和個(gè)起作用約束函數(shù)的梯度（4）按K-T條件，點(diǎn)應(yīng)滿(mǎn)足IP型問(wèn)題的Kuhn-Tucker條件檢驗(yàn)算法將上式中的各梯度矢量用其分量表示，則可得到為變量的線(xiàn)性方程組由于矢量系是線(xiàn)性無(wú)關(guān)的，所以該方程組存在唯一解．通過(guò)解此線(xiàn)性方程組，求得一組乘子，若所有乘子均為非負(fù)，即，，則即為約束最優(yōu)解．否則，點(diǎn)就不是約束最優(yōu)點(diǎn)．IP型問(wèn)題的Kuhn-Tucker條件檢驗(yàn)算法例如果是一個(gè)局部極小點(diǎn)，

8、且各梯度矢量和組成線(xiàn)性無(wú)關(guān)的矢量系，那么必存在兩組非負(fù)乘子和，使得成立。GP型問(wèn)題的Kuhn-Tucker條件由處理約束條件的辦法不同，約束優(yōu)化方法也可分為直接法和間接法兩大類(lèi)．間接法的基本思想是將約束優(yōu)化問(wèn)題首先轉(zhuǎn)換為一系列的無(wú)約束優(yōu)化問(wèn)題，然后利用無(wú)約束優(yōu)化方法來(lái)求解，逐漸逼近約束問(wèn)題的最優(yōu)解．這些算法一般比較復(fù)雜，但由于它們可以采用計(jì)算效率高、穩(wěn)定性好的無(wú)約束優(yōu)化方法，故可用于求解高維的優(yōu)化問(wèn)題．直接法的基