資源描述：
《最優(yōu)化方法-約束非線性最優(yōu)化方法.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(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ù)學(xué)中所學(xué)的條件極值：一、等式約束性問題的最優(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*)+λ*фx(x*,y*)=0f
3、y(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ī)劃問題轉(zhuǎn)化成無約束問題:minL(X,?)該問題有極值點的必要條件為:充分條件:如果且行列式方程:所有根Zj>0(j=1,2,…,n-l)，則X*為局部極小點；反之所有Zj<0，為局部極大點；有正有負非極值點例題4-1用拉格朗日乘子算法求解:解:令極大點的必要條件:對于得到的三個根。使用充分條件檢驗如下：計算:展開z的(n-l)=(2-1)=1次多項式方程，得一個信息處理技術(shù)中重要的例子－求最優(yōu)隸屬度函數(shù)１）背景介紹－聚類分析２）目標函數(shù)－符號說明構(gòu)造拉日函數(shù)：最優(yōu)化的一階必要條件為代回上式進入到約束
5、條件：得所以FCM的中心迭代過程2)不等式約束問題的Khun-Tucker條件：考慮問題minf(x)s.t.gi(x)0i=1,2,…,m設(shè)x*∈S={x
6、gi(x) 0i=1,2,…,m},并令I(lǐng)={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為起作用約束，約束集已知時回歸到含等式優(yōu)化問題問題: 事先并不知道約束集＝？定理（任意情況的最優(yōu)性必要條件）：（K-T條
8、件）問題(fg),設(shè)Ｄ={x
9、gi(x)0， }, x*∈Ｄ, I為x*點處的起作用集，設(shè)f,gi(x),i∈I在x*點可微，gi(x),iI在x*點連續(xù)。向量組{▽gi(x*),i∈I}線性無關(guān)。構(gòu)造拉日函數(shù)：如果x*----l.opt.那么，u*i≥0,使得１）駐點條件：２）互補條件：３）非負條件：４）不等式約束：５）等式約束：說明：１）如果是max問題等，要改變敘述。２）在一定條件下上面敘述變成充要條件。２．二階充分條件設(shè)拉格朗日函數(shù)為為非線性規(guī)劃的嚴格局部極小點的充分條件：１） 為Ｋ-Ｔ點；２） 拉日函數(shù)的海瑟矩
10、陣在Ｙ方向正定，并且Ｙ方向滿足下列等式：例４２求解不等式約束問題的K-T點，并判斷是否為局部極小解：１）K-Ｔ條件：考慮兩種情況：２）局部最小判別：看課本3．罰函數(shù)法（外點法）例題４－３用外點法求解解：都是不等式約束。定義外部罰函數(shù)１．解法一可行域不可行域解法二 迭代法3. 內(nèi)點罰函數(shù)法與外點法對應(yīng)，但只適合不等式約束問題3. 閘函數(shù)法：（續(xù)）因此，求解下列序貫無約束規(guī)劃問題例題 用內(nèi)點法求解解：構(gòu)造罰函數(shù)：1）微分法：解得讓 ，得4. 罰函數(shù)類算法與閘函數(shù)法的缺點：1°當罰函數(shù)法（閘函數(shù)法）的μ→∞（μ→0+）時，懲罰項→+∞?0
11、或0?+∞形式，在計算上有困難；2°計算一系列無約束問題，故計算量大。謝謝！
