最優(yōu)化方法(約束優(yōu)化問題的最優(yōu)性條件)

1、最優(yōu)化方法補(bǔ)充內(nèi)容10約束優(yōu)化問題的最優(yōu)性條件約束優(yōu)化問題的最優(yōu)性條件先看等式約束問題先看等式約束問題回顧以前學(xué)的知識(shí)什么定理？推廣到一般的情況幾何解釋幾何解釋二階充分條件二階充分條件不等式約束問題不等式約束問題不等式約束問題和等式約束問題之不等式約束問題和等式約束問題之間是否存在什么關(guān)系？間是否存在什么關(guān)系？有效約束和非有效約束有效約束和非有效約束再換句話說，不等式約束問題的在最優(yōu)解處的某再換句話說，不等式約束問題的在最優(yōu)解處的某個(gè)小鄰域內(nèi)，看以看成等式約束問題個(gè)小鄰域內(nèi)，看以看成等式約束問題回想最優(yōu)解的定義，可行的概念對(duì)回想最優(yōu)解的定義，可行的概念對(duì)于不等式約束是怎么樣的概念？于不等式約束

2、是怎么樣的概念？一一個(gè)個(gè)可可行行方方向向。處處的的為為則則稱稱有有使使得得對(duì)對(duì)任任意意的的，實(shí)實(shí)數(shù)數(shù)為為一一個(gè)個(gè)向向量量。如如果果存存在在，設(shè)設(shè)可可行行方方向向：000,00 xdQdxdQx 0)(1xc0 x1x1d1d2d2d?？尚杏?yàn)?)(|xcxQ0)(. .)(minxctsxf是是可可行行方方向向？如如何何判判斷斷一一個(gè)個(gè)向向量量是是否否可行方向。的是點(diǎn)則有，如果對(duì)任意的向量。給定的有效約束指標(biāo)集為記點(diǎn)給定點(diǎn)定理xddxcxIidxIxQxTi,0)()()(,1：證明證明有有則則對(duì)對(duì)任任意意的的。令令, )(0,xIitdtxx )|()()() (2tdodxctxcxcTi

3、ii)|()(2tdodxctTi0 為可行方向。為可行方向。即即dQx, 行行下下降降方方向向。處處的的可可為為點(diǎn)點(diǎn)的的下下降降方方向向，則則稱稱的的可可行行方方向向，又又是是該該點(diǎn)點(diǎn)處處既既是是點(diǎn)點(diǎn)，如如果果給給定定向向量量，設(shè)設(shè)點(diǎn)點(diǎn)可可行行下下降降方方向向：xdxddQx 處的可行下降方向。是點(diǎn)則向量滿足，如果向量。給定的積極約束指標(biāo)集為記點(diǎn)給定點(diǎn)定理xddxfxIidxcddxIxQxTTi0)()(0)()(,2極值點(diǎn)的必要條件：極值點(diǎn)的必要條件：處沒有可行下降方向。點(diǎn)）的局部極小點(diǎn)，則在是約束極值問題（續(xù)。如果處連在點(diǎn)處可微，在點(diǎn)和是其有效約束指標(biāo)集。，設(shè)定理*1*)*)()(*)

4、*)()()(*)(*3xxxxIixcxxIixcxfxIQxii0)()(0)(dxfxIidxcTTi0)()(0)(dxfxIidxcTTi 無解 有解錐和錐和 Farkas引理引理Gordan引理引理處沒有可行下降方向。點(diǎn)）的局部極小點(diǎn)，則在是約束極值問題（續(xù)。如果處連在點(diǎn)處可微，在點(diǎn)和是其有效約束指標(biāo)集。，設(shè)定理*1*)*)()(*)*)()()(*)(*3xxxxIixcxxIixcxfxIQxii解釋解釋Fritz-John一階必要條件一階必要條件舉例驗(yàn)證舉例驗(yàn)證KT條件條件 KKT最優(yōu)化條件是Karush1939以及Kuhn和Tucker1951先后獨(dú)立發(fā)表出來的。這組最優(yōu)化

5、條件在Kuhn和Tucker 發(fā)表之后才逐漸受到重視，因此許多書只記載成Kuhn-Tucker 最優(yōu)化條件 (Kuhn-Tucker conditions)。 凸錐中凸錐中最優(yōu)解不一定是KT點(diǎn)二階充分條件二階充分條件凸規(guī)劃問題的充分條件凸規(guī)劃問題的充分條件KT條件就是最優(yōu)條件條件就是最優(yōu)條件驗(yàn)證驗(yàn)證KT點(diǎn)點(diǎn)驗(yàn)證KT點(diǎn)的步驟 小結(jié) 1 化為標(biāo)準(zhǔn)形式化為標(biāo)準(zhǔn)形式 2 驗(yàn)證約束成立驗(yàn)證約束成立 并且求得有效約束并且求得有效約束 3 約束規(guī)范約束規(guī)范 4 一階條件方程一階條件方程 例如例如 5 驗(yàn)證不等式約束互補(bǔ)條件、乘子的非負(fù)性驗(yàn)證不等式約束互補(bǔ)條件、乘子的非負(fù)性 6結(jié)論結(jié)論0)()()(*22*1

6、1* xcxcxf 點(diǎn)的計(jì)算點(diǎn)的計(jì)算TK . 3求約束極值問題求約束極值問題例例004. .)866(5 . 0)(min2121212221xxxxtsxxxxxf。點(diǎn)點(diǎn)的的TK 解：解：。3,3)(21Txxxf2114)(xxxg Txg1,1)(1 。Txgxxg0,1)(,)(212 。Txgxxg1,0)(,)(323 條條件件得得由由TK 01001113332121 xx條條件件及及約約束束條條件件得得由由TK 0,4000)4(3321321212312211312211xxxxxxxxxx 以下分情況討論：以下分情況討論：:0)1(21 xx若若?？傻每傻糜捎?0)4(1211 xx321 32 矛盾。矛盾。這與這與02 :0,0)2(21 xx若若03 332112 x022 x022 x 矛盾。矛盾。這與這與02 :0,0)3(21 xx若若02 0,4000)4(3321321212312211312211xxxxxxxxxx 333111 x031 x013 x 矛盾。矛盾。這與這與03 :0,0)4(21 xx若若032 331211 xx21xx 421 xx若若01 321 xx4621 xx矛盾。矛盾。421 xx221 xx11 點(diǎn)。點(diǎn)。為為TKT