非線性約束優(yōu)化

《非線性約束優(yōu)化》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、第四章約束最優(yōu)化方法問題minf(x)s.t.g(x)≤0h(x)=0約束集S={x

2、g(x)≤0,h(x)=0}(fgh)高等數(shù)學中所學的條件極值：一、等式約束性問題的最優(yōu)性條件：考慮minf(x)s.t.h(x)=0問題:在ф(x,y)=0的條件下,求z=f(x,y)極值.minf(x,y)。s.t.ф(x,y)=0引入Lagrange乘子：λLagrange函數(shù)L(x,y;λ)=f(x,y)+λф(x,y)一、等式約束性問題的最優(yōu)性條件：(續(xù))若(x*,y*)是條件極值，則存在λ*，使fx(x*,y*)+λ*

3、фx(x*,y*)=0fy(x*,y*)+λ*фy(x*,y*)=0Ф(x*,y*)=0推廣到多元情況，可得到對于(fh)的情況：minf(x)s.t.hj(x)=0j=1,2,…,l若x*是(fh)的l.opt.,則存在?*∈Rl使以及hj(x)=0，j=1,2,…,l一、等式約束性問題的最優(yōu)性條件：(續(xù))幾何意義是明顯的：考慮一個約束的情況：最優(yōu)性條件即：-▽f(ㄡ)ㄡ▽h(ㄡ)h(x)－▽f(x*)▽h(x*)這里x*---l.opt.▽f(x*)與▽h(x*)共線，而ㄡ非l.opt.▽f(ㄡ)與▽h(ㄡ)不

4、共線。一等式約束下的拉格朗日乘子算法考慮等式約束問題:令拉格朗日函數(shù):則等式約束下規(guī)劃問題轉化成無約束問題:minL(X,?)該問題有極值點的必要條件為:充分條件:如果且行列式方程:所有根Zj>0(j=1,2,…,n-l)，則X*為局部極小點；反之所有Zj<0，為局部極大點；有正有負非極值點例題4-1用拉格朗日乘子算法求解:解:令極大點的必要條件:對于得到的三個根。使用充分條件檢驗如下：計算:展開z的(n-l)=(2-1)=1次多項式方程，得一個信息處理技術中重要的例子－求最優(yōu)隸屬度函數(shù)１）背景介紹－聚類分析２）目

5、標函數(shù)－符號說明構造拉日函數(shù)：最優(yōu)化的一階必要條件為代回上式進入到約束條件：得所以FCM的中心迭代過程2)不等式約束問題的Khun-Tucker條件：考慮問題minf(x)s.t.gi(x)0i=1,2,…,m設x*∈S={x

6、gi(x)0i=1,2,…,m},并令I={i

7、gi(x*)=0，i=1,2,…,m}稱I為x*點處的起作用集（緊約束集）。如果x*是l.opt.,對每一個約束函數(shù)來說，只有當它是起作用約束時，才產(chǎn)生影響，如：g2(x)=0x*g1(x)=0g1(x*)=0,g1為起作用約束，約束集已知時回

8、歸到含等式優(yōu)化問題問題:事先并不知道約束集＝？定理（任意情況的最優(yōu)性必要條件）：（K-T條件）問題(fg),設Ｄ={x

9、gi(x)0，},x*∈Ｄ,I為x*點處的起作用集，設f,gi(x),i∈I在x*點可微，gi(x),iI在x*點連續(xù)。向量組{▽gi(x*),i∈I}線性無關。構造拉日函數(shù)：如果x*----l.opt.那么，u*i≥0,使得１）駐點條件：２）互補條件：３）非負條件：４）不等式約束：５）等式約束：說明：１）如果是max問題等，要改變敘述。２）在一定條件下上面敘述變成充要條件。２．二階充分條件設拉格

10、朗日函數(shù)為為非線性規(guī)劃的嚴格局部極小點的充分條件：１）　為Ｋ-Ｔ點；２）　拉日函數(shù)的海瑟矩陣在Ｙ方向正定，并且Ｙ方向滿足下列等式：例４２求解不等式約束問題的K-T點，并判斷是否為局部極小解：１）K-Ｔ條件：考慮兩種情況：２）局部最小判別：看課本3．罰函數(shù)法（外點法）例題４－３用外點法求解解：都是不等式約束。定義外部罰函數(shù)１．解法一可行域不可行域解法二　迭代法3.內(nèi)點罰函數(shù)法與外點法對應，但只適合不等式約束問題3.閘函數(shù)法：（續(xù)）因此，求解下列序貫無約束規(guī)劃問題例題　用內(nèi)點法求解解：構造罰函數(shù)：1）微分法：解得讓　　

11、　　，得4.罰函數(shù)類算法與閘函數(shù)法的缺點：1°當罰函數(shù)法（閘函數(shù)法）的μ→∞（μ→0+）時，懲罰項→+∞?0或0?+∞形式，在計算上有困難；2°計算一系列無約束問題，故計算量大。