0,使對??∈[0,?]均有?+??∈?,則稱?是可行域?在可行解?處的可行方向,可行域?在可行解ˉ?處的所有可行方向記為FD(?,?),簡記為FD(?)定理5.1設(shè)?">
約束優(yōu)化常見算法

約束優(yōu)化常見算法

ID:40878624

大小:41.06 KB

頁數(shù):10頁

時間:2019-08-09

約束優(yōu)化常見算法_第1頁
約束優(yōu)化常見算法_第2頁
約束優(yōu)化常見算法_第3頁
約束優(yōu)化常見算法_第4頁
約束優(yōu)化常見算法_第5頁
資源描述:

《約束優(yōu)化常見算法》由會員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第五章約束優(yōu)化常見算法定義5.1設(shè)x∈?為一可行點(diǎn),?∈Rn,若存在?>0,使對??∈[0,?]均有?+??∈?,則稱?是可行域?在可行解?處的可行方向,可行域?在可行解ˉ?處的所有可行方向記為FD(?,?),簡記為FD(?)定理5.1設(shè)?是問題(5.1)的可行解,在點(diǎn)?處有A1?=b1,A2?>b2,其中A=A1A2,B=b1b2則非零向量?為?處的可行方向的充要條件是A1?≥0,??=0。Zoutendijk方法:如果非零向量?同時滿足?fxT?<0,A1?≥0,??=0,則?是在?處的下降可行方向。因此,Zout

2、endijk法把確定搜索方向歸結(jié)為求解線性規(guī)劃問題:min?fxT?s.tA1?≥0??=0‖?‖≤1.(5.2)其中增加約束條件‖?‖≤1是為了獲得一個有限解。在(5.2)中,顯然?=0是可行解,因此最優(yōu)目標(biāo)值小于或等于零.如果?fxT?<0,則得到下降可行方向?;如果最優(yōu)值為零,則有如下結(jié)果.定理5.2考慮問題(5.1),設(shè)?是可行解,在點(diǎn)?處有A1?=b1,A2?>b2,其中A=A1A2,B=b1b2則?為Kuhn-Tucker點(diǎn)的充要條件是問題(5.2)的最優(yōu)目標(biāo)值為零。Rosen投影梯度法定義5.2設(shè)?為?階

3、矩陣,若?=PT且P2=?,則稱?為投影矩陣。定理5.3設(shè)?是問題(5.1)的可行解,在點(diǎn)?處,有?1?=?1,?2?>?2,其中A=A1A2,B=b1b2又設(shè)M=A1E為行滿秩矩陣,則?=??MTMMT-1?是一個投影矩陣,且若???(?)≠0,則?=????(?)是下降可行方向.定理5.4設(shè)?是問題(5.1)的一個可行解,A1,A2,?的定義同定理5.3,且?為行滿秩矩陣,令?=MMT-1???(?)=uv其中?和?分別對應(yīng)于A1和?.若???(?)=0,則1如果?≥0,那么?是K-T點(diǎn);2如果?中含有負(fù)分量,不妨

4、設(shè)uj<0,這時從?1中去掉uj對應(yīng)的行,得到A1,令M=A1E,P=I-MTMMT-1M?=?P??(?)那么?為下降可行方向。梯度投影法計算步驟1.給定給定初始可行點(diǎn)x1,置?=1。2.在點(diǎn)xk處,將?和?分別分解成A1,A2和b1,b2,使得A1?=b1,A2?>b2.3.令M=A1E如果?是空的,令?=?(單位矩陣),否則令?=??MTMMT-1?.4.令dk=????(xk).若?(?)≠0,則轉(zhuǎn)步6;若?(?)=0,則進(jìn)行步5.若?是空的,則停止計算,得到xk;否則,令?=MMT-1???(?)=uv如果?

5、≥0,則停止計算,xk為K-T點(diǎn);如果?中包含負(fù)分量,則選擇一個負(fù)分量,比如uj,修正A1,去掉A1中對應(yīng)uj的行,返回步3。根據(jù)式(5.4)計算λmax,然后解下列問題,min?(xk+?dk)?.?0≤?≤λmax得步長λk,令xk+1=xk+λkdk,置?:=?+1,返回步2Du&Zhang的修改1.給定給定初始可行點(diǎn)x1和一個正常數(shù)?>0,置?=1。2.在點(diǎn)xk處,將?和?分別分解成A1,A2和b1,b2,使得A1?=b1,A2?>b2.3令?=uv如果?是空的,令?=?(單位矩陣),否則令?=??MTMMT-

6、1?.4計算?=MMT-1???(?)=uv和?(?)=????(xk).5.定義uh,min{uj

7、?=1,...,?}.如果‖dk‖=0且uh≥0(或?是空的),則停止計算,xk為K-T點(diǎn);若‖dk‖≥?uh?,dk不變,轉(zhuǎn)下步;若‖dk‖

8、束問題min?(?)s.t.cj(?)=0,?=1,...,me(5.6)可定義輔助函數(shù)F1(?,?)=(?)+?j=1mecj2x(5.7)參數(shù)?是很大的正數(shù)。這樣就能把(5.6)轉(zhuǎn)化為無約束問題minF1(?,?)=?(?)+?j=1mecj2x(5.8)顯然,(5.8)的最優(yōu)解必使得cj(?)接近零,因為如若不然,(5.7)的第2項將是很大的正數(shù),現(xiàn)行點(diǎn)必不是極小點(diǎn)。由此可見,求解問題(5.8)能夠得到問題(5.6)的近似解。罰函數(shù)的理論分析考慮min?(?)s.t.ci(?)=0,?∈?ci(?)≥0,?∈??

9、∈?其中?是非空閉集,?={1,...,me},?={me+1,...,?}.定義?={?∈Rn

10、ci(?)=0,?∈?;ci(?)≥0,?∈?}該問題對應(yīng)的罰函數(shù)優(yōu)化問題是:min?(?,?)=?(?)+??(?).s.t.?∈?且:?∈???(?)=0,?≠???(?)>0定義:θσ=infFx,σ

11、x∈X引理5.1設(shè)?,?均

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費(fèi)完成后未能成功下載的用戶請聯(lián)系客服處理。