不等式約束問(wèn)題-文庫(kù)吧
2024-09-22 13:37 本頁(yè)面
【正文】 不存在滿足 的可行方向 ? ? 0? ?? DXfT在 處不存在可行下降方向 ?只有 是 的某個(gè)鄰域內(nèi)的凸函數(shù)，兩者等價(jià) )(XfX?X?X?不能說(shuō) 是局部最優(yōu)解！ ?線性不等式約束問(wèn)題最優(yōu)解的必要條件 ? ?libXPXf iTi ??? 1, s . t .)(m i n對(duì)于線性不等式約束的優(yōu)化問(wèn)題 如果 是局部最優(yōu)解， 是以 處起作用約束 X? AWAXf ?)?( ??0? ?WX?（ KuhnTucker條件） 的系數(shù)向量為列向量構(gòu)成的矩陣，并且假定其列 向量線性無(wú)關(guān)，那么一定存在 滿足 注意： 的列向量線性無(wú)關(guān)是上述結(jié)論成立的條件 ！ AX?滿足上述條件的 稱為 KT解 1）確定初始可行解 X?2）構(gòu)造 處起作用約束對(duì)應(yīng)的 矩陣，計(jì)算 A? ? ? ?XfAAAW TT ?? 1 ?? ?3）如果 ，停止， 是 KT解 ? ? WAXfW ??,0? ???線性不等式約束問(wèn)題的 投影梯度法 X?否則按照情況 1或情況 2對(duì)應(yīng)的方法確定可行 下降方向 D4）在 處沿方向 進(jìn)行一維搜索確定 0? ?tDtX ?? ?用 替換 ，然后回到 2）繼續(xù)迭代 X? DX?X?可行步長(zhǎng)應(yīng)該滿足 由于 ，所以最大可行步長(zhǎng)為 ???????????? liDPDPbXPt TiTiiTi 1,0?m i n線性不等式約束一維搜索的 最大可行步長(zhǎng) ? ? libtDXP iTi ????? 1,?0?DP Ti等價(jià)于 liDtPbXPTiiTi ?????? 1,?ibXP iTi ??? ,0?注意到對(duì)起作用約束有 ，所以 ????????????? lilDPDPbXPt TiTiiTi 1?,0?m i n如果 ，則有 iDP Ti ?? ,0 ??t不保證下降！ 一般性不等式約束問(wèn)題 ? ?liXgXf i ??? 1,0)( s . t .)(m i n一般性不等式約束優(yōu)化問(wèn)題 假定 滿足以下條件： liXg i ?1,0)?( ???lilXg i ???? 1?,0)?(? ?)?(,),?(),?( ?21 XgXgXgA l???? ?列線性無(wú)關(guān) （起作用約束） （不起作用約束） nRX ??如果 ，則有 以上條件和對(duì)線性不等式約束所假定的條件一致 ibXPXg iTii ??? ,)( ii PXg ?? )(非線性不等式約束可行方向的充分條件 liDXg iT ?1,0)?( ?????22 )?(21)?( DtDXgDtDXgiTi ?????理由： 不是必要條件的原因： 0)?( ?Xg i0)?( ?? DXg iT??????? ?????? DtDXgDDXgttDXg iTiTi )?(21)?()?( 2 ??X?0)(1 ?Xg可行集 不可行 X?11 bXP T ?1P可行集 01 ?DPT可行 0)?(1 ?? DXgT)?(1 XgT?線性約束 非線性約束 非線性不等式約束和線性不等式約束的本質(zhì)區(qū)別 01 ?DP T0)?(1 ?? DXgT如果 滿足適合線性不等式約束的可行下降 nRD ?方向的條件，即 一定存在 ，使 lRC ??滿足 ? ? CAAADD T 1???因此 是非線性不等式約束的可行下降方向 線性和非線性不等式約束可行下降方向之間的關(guān)系 liDXgDXf iTT ?1,0)?(,0)?( ???????liDXgDXf iTT ?1,0)?(,0)?( ???????D理由： 0)?( ?? DXfT已知條件 ? ?? ? CDACAAADADA TTTT ???? ? 1? ?)?(,),?(),?( ?21 XgXgXgA l???? ?因?yàn)? 所以 ? ? IAAAATT ?? 10?DA T其中 由于 ，只要 的分量都大于 0， 0?DA T C DAT另一方面，因?yàn)? 以及 0)?( ?? DXfTliDXg iT ?1,0)?( ?????每個(gè)分量就大于 0，即 ? ? CAAAXfDXfDXf TTTT 1)?()?()?( ??????只要 的每個(gè)分量充分小，就會(huì)有 C 0)?( ?? DXfT非線性不等式約束問(wèn)題可行下降方向的存在性定理 ? ? AWXf ?? ?? ?)?(,),?(),?( ?21 XgXgXgA l???? ?其中 ? ? )?(? 1 XfAAAW TT ?? ?如果 （等價(jià)于方程組無(wú)解）或者 WAXf ?)?( ??有小于 0的分量，一定存在 滿足 W?，令 nRD ?liDXgDXf iTT ?1,0)?(,0)?( ???????根據(jù)線性和非線性不等式約束可行下降方向之間的關(guān) 系，此時(shí)在 處一定存在可行下降方向 X?考慮 起作用約束構(gòu)成的線性方程組 ? ?liXgXf i ??? 1,0)( s . t .)(m i n不等式約束優(yōu)化問(wèn)題最優(yōu)解的必要條件 如果 是上述問(wèn)題的局部最優(yōu)解，線性方程 lilXgliXg ii ??????? 1?,0)?(,?1,0)?(? ?)?(,),?(),?( ?21 XgXgXgA l???? ?列線性無(wú)關(guān) 等價(jià)表述 結(jié)論 X?問(wèn)題 條件 組 一定存在分量非負(fù)的解 ? ? AWXf ?? ?如果 是上述問(wèn)題的局部最優(yōu)解，向量 X? 一定滿足線性方程組 ，并且其每個(gè)分量都不小于 0 ? ? )?(? 1 XfAAAW TT ?? ?? ? AWXf ?? ?（ KuhnTucker條件） 一般性等式和不等式約束問(wèn)題 假設(shè)條件：已知 滿足 ? nXR?1） 2） 線性無(wú)關(guān) ? ? ? ? ? ? ? ??11? ? ? ?, , , , ,m lh X h X g X g X? ? ? ?優(yōu)化模型 ? ?m i n ( ) s . t . ( ) 0 , 1 , ( ) 0 , 1jif X h X j m g X i l? ? ? ? ? ??( ) 0 , 1? ?? ?( ) 0 , 1 , ( ) 0 , 1jiih X j mg X i l g X l i l? ? ?? ? ? ? ? ? ?如果 是最優(yōu)解，還必須滿足什么條件？ ?X要回答的問(wèn)題： 1 ( , )( , )( , )mh Z YH Z Yh Z Y????? ????? ? ? ? ? ? ? ??11? ? ? ?, , , , ,m lh X h X g X g X? ? ? ?存在 的 個(gè)分量，記為 ，滿足 線性無(wú)關(guān) ? ? ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1