【正文】 不等式約束問題 ? ?libXPXf iTi ??? 1, s . t .)(m i n線性不等式約束優(yōu)化問題 ? ?liXgXf i ??? 1,0)( s . t .)(m i n一般性不等式約束優(yōu)化問題 不等式約束在給定點的分類及其作用 liXg i ???? 1,0)?(設(shè) 滿足所有約束，即 X?0)?( ?Xg jX?如果 是 處不起作用的約束，則對任 X?0)( ?Xgj意的 都存在 滿足 tttDXg j ?0,0)?( ?????nRD ? 0??t所以， 構(gòu)造可行方向時不用考慮不起作用約束 在 處不起作用約束 ： 0)?( ?Xg jX?在 處起作用約束 ： 對起作用約束指標(biāo)集的約定 liXg i ?1,0)?( ????對任何滿足不等式約束的可行解 ，只要不特別說 明，總是假定其前 個約束是起作用約束，其它約 束是不起作用約束，即 lilXg i ????? 1?,0)?(l?X?線性不等式約束問題 線性不等式約束可行方向的充要條件 理由： 所以 0,?1,? ????? tlibXP iTi因為 對于線性不等式約束 ， 是 可行解 處的可行方向的 充要條件 是 libXP iTi ??? 1, nRD ?liDP Ti ?1,0 ????X?XPbDtPbtDXP TiiTiiTi ?)?( ?????liDPXPbDtP TiTiiTi ?1,0? ???????下降方向的充分條件 X?0?tttXftDXf ????? 0),?()?(?????? ??????? DtDXfDDXftXftDXf TT )?(21)?()?()?( 2 ?0)?( ?? DXfT對任意的 ，如果 ， 就 是 在 處的下降方向 nn RDRX ?? ,? D理由： 由于 ，一定存在 滿足 )(Xf0)?( ?? DXfTttDtDXfDDXf TT ???????? 0,0)?(21)?( 2 ?? 不是下降方向必要條件的原因 22 )?(21)?()?( DtDXfDXftDXf T ??????0)?( ?? DXfT0)?( ?? DXfTDDXfD T ??? 0)?(2?是下降方向 DDXfD T ??? 0)?(2 是上升方向 DDXfD T ??? 0)?(2 的性質(zhì)不定 是下降方向充要條件的一個充分條件 0)?( ?? DXfT是 的某個鄰域內(nèi)的凸函數(shù) )(Xf X?理由： 凸函數(shù)的一階必要條件 ? ?? ? ? ? ? ? ??????? 2112121 , XXXfXfXXXfT其中 是保證上述凸性的鄰域，令 ?tDXXXX ??? ?,? 21)?()?()?( XftDXfDXft T ????0)?( ?? DXfT 0),?()?( ???? ttDXfXf不是下降方向 代入上式可得 ?D?構(gòu)造線性不等式約束的可行下降方向 libXP iTi ??? 1,基本假定 基本途徑 的可行解，起作用約束的系數(shù)向量線性無關(guān) 即矩陣 的列向量線性無關(guān) 分析線性方程組 的解的情況 其中 是方程組的變量 ? ? AWXf ?? ?? ?TlW ?21 , ??是滿足線性不等式約束 X?? ?lPPPA ?21 , ??線性方程組 的解的各種可能的情況 ? ? AWXf ?? ?因為 的列向量線性無關(guān)， 有逆，可以定義 A AAT? ? )?(? 1 XfAAAW TT ?? ?情況 情況 0? ?kwWAXf ?)?( ?? 方程組無解 ? ? WAXf ~? ??情況 WAXf ?)?( ?? 但存在 滿足 lk ?1 ??WAXf ?)?( ?? 并且 0? ?W? ? ? ?? ? ? ?11? ??TTTTA W A A A A f XA A A A A W A W f X????? ? ? ?理由： ??? ?Xf ???X?11 bXP T ?1P情況 1的例子 ? ? WAXfPA ??,1 ???可行集 將負梯度投影到所有起作用約束的零空間，如上圖的 22 bXP T ?33 bXP T ?DD01 ?DP T 的零空間（滿足 的全體向量）的 投影矩陣 0?XA T? ? ? ? TT AAAAIAQ 1???其中 是單位矩陣 I? ? ? ? ? ?? ? )(2 AQAQAQAQ T ??? ? liAQP Ti ?1,0 ????? ? ? ? ? ? WAXfXfAQ ??? ????性質(zhì) 性質(zhì) 性質(zhì) ? ? 0?AQA T 即 A情況 1（ ）的可行下降方向 ? ? ? ?XfAQD ????理由：利用性質(zhì) 2可得 ? ? ? ?? ? ? ?? ? 0????? ???????? WAXfWAXfXfD TT由下降方向的充分條件可知是下降方向 利用性質(zhì) 3可得 由可行方向的充要條件可知是可行方向 liDP Ti ?1,0 ????WAXf ?)?( ??? ?Xf ???X?11 bXP T ?1P情況 2的例子： ? ? ? ? 0?,0?,??,2121 ????? wwWAXfPPA2PD0021??DPDPTT33 bXP T ?22 bXP T ?可行集 將負梯度投影到所有正 的起作用約束的零空間，如 Diw?情況 2（ ）的可行下降方向 其中 是 的第 個列向量，即 ? ? 1?AAA T理由： k第 個分量等于 1 0?,?)?( ??? kwWAXfkPD ?kP? ? ? ? 1?21 , ?? AAAPPP Tl?k? ? ? ? IAAAAPPPA TTlT ?? ? 1?21 , ?? ? ? 00,0,1,0,0 ???? TkkTT ePADA ???（可行） ? ? 0???? ????? kkTkTTT weWPAWDXf ?（下降） 情況 3的例子： 2P? ?Xf ???X?11 bXP T ?33 bXP T ?22 bXP T ?可行集 0?,?)?(,2 ???? WWAXfPA不存在滿足 的可行方向 ? ? 0? ?? DXfT情況 3（ ）的結(jié)論 0?,?)?( ??? WWAXf不存在滿足 的可行方向 ? ? 0? ?? DXfT理由： 是可行方向 D 0?DA T0?,?)?( ??? WWAXf ? ? ? ? 0?? ??? DAWDXf TTT? （充要條件） ?注意：