不等式約束問題-資料下載頁
2025-10-03 13:37本頁面
【導(dǎo)讀】如果是處不起作用的約束，則對任X?DXfT對任意的，如果，就。是下降方向充要條件的一個(gè)充分條件0)?是的某個(gè)鄰域內(nèi)的凸函數(shù))(XfX?其中是保證上述凸性的鄰域，令?線性方程組的解的各種可能的情況??情況2的例子：????理由：是可行方向D0?不能說是局部最優(yōu)解！?滿足上述條件的稱為K-T解。1）確定初始可行解X?3）如果，停止，是K-T解??
【正文】 ?? ? ? ? ? ?2200? ?iiTi i irrD f Y r y r??? ? ? ???? ? ?? 0TD f Y??? 0Y ??下降方向 ? 0 , 1 , 0iiy t d i n m t? ? ? ? ? ? ??? ?1 ? 0B b N Y? ??0D?? ?? 0TD f Y???可行下降方向的理由： 1）確定初始可行解 X?2）選擇 的前 個(gè)最大的正分量為 向量，確定 及可行解 m3）計(jì)算簡約梯度 和可行下降方向 如果 ，停止， 已是 KT解 0D?標(biāo)準(zhǔn)線性約束優(yōu)化問題的簡約梯度法 X?4）在 處沿方向 進(jìn)行一維搜索確定 ，然 后用 替換 ，用 和 更 換 ，再回到 2）繼續(xù)迭代 0? ?t? ?Y tD??Y DX?X?? ?? ?1m in ( ) s .t . 0 , 0f Y B b N Y Y? ? ? ??YD,1ir i n m? ? ?Z?Y ? ?1?Z B b N Y??? ?Y其他有關(guān)問題 )(m in XfX ??凸規(guī)劃問題的 KT解的性質(zhì) 凸規(guī)劃問題 需要： 凸函數(shù)， 凸集 f ?等式和不等式約束描述的凸規(guī)劃問題 mjXhliXgXfji,2,1,0)(,2,1,0)( s .t .)(m in??????需要： 凸函數(shù)， 都是凹函數(shù)， 都是線性函數(shù) fig容易驗(yàn)證，此時(shí)可行集是凸集 jbXPXh jTjj ??? ,)(jh利用可導(dǎo)凸（凹）函數(shù)的性質(zhì)可以得到 設(shè) 是滿足 KT條件的可行解， 是任意可行解 則有 )?()()?()?( XfXfXfXX T ????liXgXgXgXX iiiT ?1,0)?()()?()?( ????????X? XliXgXg ii ?1,0)?(,0)( ?????mjbXPbXP jTjjTj ????? 1,?,又因?yàn)? ，可知 jbXPXhjTjj ??? ,)(mjPXXXhXX jTjT ???????? 1,0)?()?()?(?0 , 1 , 2 , ,iw i l??滿足 , 1 , 2 , ,j jm? ??11? ? ?( ) ( ) ( )mlj j i ijif X h X w g X???? ? ? ? ???因?yàn)? 是滿足 KT條件的可行解，所以存在 X?和可正可負(fù)的 )?()()?()?( XfXfXfXX T ????利用 再利用 可得 mjXhXX jT ?????? 1,0)?()?(?1? ? ? ?( ) ( ) ( ) ( )lTTiiiX X f X w X X g X?? ? ? ? ??又可得 ?1? ? ?( ) ( ) ( ) ( )l Tiiif X f X w X X g X?? ? ? ??可以得到 最后，由于 ?0 , 1 , 2 , ,iw i l??liXgXX iT ?1,0)?()?( ??????)?()( XfXf ?由于 是任意可行解，所以 是全局最優(yōu)解 X?X?1? ? ?( ) ( ) ( ) ( )l Tiiif X f X w X X g X?? ? ? ??全局最優(yōu)解的充要條件 結(jié)論： 對于凸規(guī)劃問題， KuhnTucker條件是 一般性優(yōu)化問題的罰函數(shù)法（外點(diǎn)法） 對于一般性優(yōu)化問題 mjXhliXgXfji,2,1,0)(,2,1,0)( s .t .)(m in??????構(gòu)造加上懲罰項(xiàng)的目標(biāo)函數(shù) ? ? ? ? ? ????????mjjliik XhkXgkXfXF11)()()( ??外點(diǎn)法就是求解下述無約束問題逼近原問題的解 )(m in XF kRX n?其中 ? ? ? ? ? ?? ???????????000,0m i n, 222uuuuuuu ??不等式約束優(yōu)化問題的障礙函數(shù)法（內(nèi)點(diǎn)法） 對于一般性不等式約束優(yōu)化問題 liXgXfi ,2,1,0)( s . t .)(m in???構(gòu)造加上障礙函數(shù)項(xiàng)的目標(biāo)函數(shù)，如 ? ? ? ?????? liir XgrXfXf11)()(?可以從可行解開始求解下述無約束優(yōu)化問題逼近 )(?m in Xf rRX n?原問題的解 拉格朗日（ Lagrange）對偶問題 對于附加約束子集的一般性優(yōu)化問題 定義拉格朗日 對偶 問題為 其中 njiRXmjXhliXgXf???????,2,1,0)(,2,1,0)( s .t .)(m in??? ? ???????mjjjliii XhzXgyXfZYXL11)()()(,? ? ? ? TmTl zzzZyyyY ,, 2121 ?? ??? ? ? ?ZYXLZY X ,m in, ????? ?ZYY ,m a x0 ??0 s .t .m in??XbAXXC T例、 原問題 所以拉格朗日 對偶 問題為 ? ? ? ? ? ? ZbXZACbAXZXCZXL TTTTT ??????,? ? ? ??????????? 其他情況如果 ZACZbZXLZ TTX,m i n?則 ? ?0???? XRX nCZAZbTT? s . t.m a x0 s .t .m in??XbAXXC T仍然考慮原問題 所以拉格朗日 對偶 問題為 ? ? ? ?? ? ZbXZAYCbAXZXYXCZYXLTTTTTT????????,? ? ? ??????????? 其他情況如果 ZAYCZbZYXLZY TTRX n,m i n,?0, s . t .m a x??? YYZACZbTT如果不定義附加子集，即 ，則 nR??CZAZbTT? s . t.m a x?弱對偶定理 如果 是原問題的可行解， 是對偶問題可行 ? ? )?(?,? XfZY ??X? ? ?ZY ?,?解，那么一定成立 理由： ? ?)?()?(?)?()?(?)?(?)?(?,?,?111XfXgyXfXhzXgyXfZYXLliiimjjjliii????????????因?yàn)? ， jXhiXgji ???? ,0)?(,0)?(0? ?Y所以 又因?yàn)? ，所以 ??X?? ? ? ? ? ? )?(?,?,??,?,m i n?,? XfZYXLZYXLZY X ??? ???推論 是原問題的可行解 ? ? )?(?,? XfZY ??X?? ?ZY ?,?并且 X?? ?ZY ?,?是對偶問題可行解 如果 是對偶問題的最優(yōu)解 是原問題的最優(yōu)解 那么
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1