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

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

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

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

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

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

6、1* xcxcxf 點的計算點的計算TK . 3求約束極值問題求約束極值問題例例004. .)866(5 . 0)(min2121212221xxxxtsxxxxxf。點點的的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 點。點。為為TKT