第7章 約束問題的優(yōu)化方法

1、90第7章約束問題的優(yōu)化方法約束問題的優(yōu)化方法7.1可行方向法可行方向法7.1.1可行方向法的基本思想可行方向法的基本思想可行方向法是一類算法可看作無約束下降算法的自然推廣。典型策略是從可行點(diǎn)出發(fā)，沿著下降可行方向進(jìn)行搜索，求出使目標(biāo)函數(shù)值下降的新的可行點(diǎn)考慮只含線性約束的非線性規(guī)劃問題：（1）eExbAxxf??s.t.)(min為非線性函數(shù)，，，，.)(xfnmRA??nlRE??mRb?lRe?注1：線性約束規(guī)格保證了優(yōu)化問題（1

2、）的可行方向集、線性化可行方向集以及序列化可行方向集是等同的。當(dāng)某個(gè)可行方向同時(shí)也是目標(biāo)函數(shù)的下降方向時(shí)，沿此方向移動(dòng)一定會(huì)在滿足可行性的情況下改進(jìn)迭代點(diǎn)的目標(biāo)函數(shù)值。目前已經(jīng)提出許多可行方向法，用來處理具有線性約束的非線性規(guī)劃問題。搜索方向選擇方式不同形成不同的可行方向法：（1）Zoutendijk可行方向法（2）Rosen梯度投影法（3）Wolfe既約梯度法可行方向的判定：定理1：設(shè)是問題（1）的可行解，在點(diǎn)處有，，其中x?x?11

3、?bxA?22?bxA?，???????21AAA???????21bbb則非零向量為處的可行方向的充要條件是dx?，01?dA0?Ed證明：必要性：設(shè)非零向量是處的可行方向根據(jù)可行方向的定義，，使得對(duì)每dx?0???個(gè)有為可行點(diǎn)，即，.)0(???dx???bdxA??)?(?edxE??)?(??????????????????????????21221121?)?()?(bbdAxAdAbdxAAdxA????由于，由上式得到0?

4、?01?dA又由得到.edxE??)?(?0?Ed92在點(diǎn)處，把不等式約束區(qū)分為起作用約束和不起作用約束：，)(kx1)(1bxAk?2)(2bxAk?(3)式中第1個(gè)約束可以寫成（4）???????????????21)(2)(2)(1)(1bbdAxAdAxAkkkk??由于為可行方向，，，以及，因此自)(kd0)(1?kdA0??1)(1bxAk?1)(1)(1bdAxAkk???然成立約束條件（4）簡化為2)(2)(2bdAxA

5、kk???問題（3）簡化為（5）0s.t.)(min2)(2)(2)()(???????bdAxAdxfkkkk根據(jù)（5）式的約束條件，容易求出的上限，令?)(22?kxAbb??)(2?kdAd?由知.2)(2bxAk?0??b(5)式的約束條件寫成：?????0????bd由此得到的上限：????????????????????0?0?0?|??minmaxd，dddbiii不大于?問題（3）最終簡化成：（6）max)()(0s.t