約束優(yōu)化的共軛梯度算法及最優(yōu)性條件

1、約束優(yōu)化的共軌梯度算法及最優(yōu)性條件1概要1. 共軌梯度算法2. 必耍性最優(yōu)性條件3. 充分性最優(yōu)性條件4. 凸優(yōu)化5. 應(yīng)用2共宛梯度算法2.1二次換數(shù)linn/(x) = x'OX + c'x定義：d“,d”是0共覘,若d,豐 0, djQd)= 0,心 j幻燈片1幻燈片2命題：若&,.,"”是0共軌的，則是線性獨(dú)工的2.2起源給定0共純的山,”及X仁計(jì)算:幻燈片3nun f(xk + adk) = dxk + ac'dk + 0.5(x* +adk) = f(xk) + aVf(xky(ik a+ 0.5a2dkOdk解:Adg2.3生成子空間定理

2、幻燈片4心,4”是。共氟 則，x"1,求解nun f(x)ks.t. x = X + 工 jdj而且；x卄=X*2.4算法步 o ：給定丫，記k=ia=-w°）步刈*=i""進(jìn)行幻燈片52.5校正若阿X）卜G停止：否則:Aak = argmina f(xk + adk)=x*+1 = xk +ak dk 心呵(嚴(yán))+ S ，f(xyodkAt =:dg定理:方向是0共輒的dg2.6收斂性質(zhì) 這是有限的算法 如果Q只有k個(gè)不同的待征值,則在k步內(nèi)CGA能找到最優(yōu)解 考偲min / (sx) = (sx)'0(sx) + c'sx«

3、2使徇s'G的不同的特征值的個(gè)數(shù)很小2.7例子幻燈片6幻燈片7幻燈片R(3519222816194333195223340291228192939161651216123277416561486426240224、404480 =327745101416561481122246426202400402241202440448440416丿(100-3且。=0-20-6-7K(Q) 17.641（K（0）+1 丿= 0.999774幻燈片幻燈片12步0：給定孫設(shè)k = h cl, =-W0）幻燈片109k冷）/X)/(/)/()-/(/)/(.嚴(yán))_/&)112.00000025

4、93.7268521.00000028.7585782590.4854300.99875031.8692182583.5960690.9973414-12.7773742568.9494780.9943315-30.4794832551.2473690.9931096-187.8043672393.9224850.9383347-309.8369072271.8899450.9490248-408.5904282173.1364240.9565329-754.8875181826.8393340.84064610-2567.15842114.5684310.00797511-2581.7116

5、720.0151800.00104212-2581.726852-0.000000-0.0000002.8 一般問題幻燈片12幻燈片12步1:若阿（川|",停止；否則Adga* = aignuna f(xk 4- adk)=幻燈片12幻燈片12A=xk + ak dk幻燈片12步2： k + 轉(zhuǎn)向步1幻燈片113必要的最優(yōu)性條件3.1非線性優(yōu)化nun f (x)hi(x) = Oj =P = xgj (x) < O.j = 1p,加(x) = 0j = 1 .，加3.2 KKT條件ill Kamsh_Kului_Tuckey 在 1950*5 發(fā)現(xiàn)定理：如果 壬是P的局部最小值

6、點(diǎn) Z =約束指標(biāo)集 約束規(guī)格條件(CQC):向 g Pgj(X), j G I、" (X),Z =獨(dú)立的則，存在向量(u, v)：1. Vf(x)+,(x)+= 01=12 wO3 W?g/x) = 03.3線性優(yōu)化的一些直觀形式在解壬的領(lǐng)域內(nèi)將負(fù)數(shù)線性的，問題化成：min f (x) + Yf(xy(x - x)sJ.gj(x) + 阻(x)'(x-x) <0,y gZW(x)+V(x/(x-x) = O.j = 1m這是一個(gè)LO問題，對(duì)偶可行性：八E 人一_ 八刃仃 G)+%石)=wG) "SO jeJi«i取"丿=-Mz，Vr =

7、-V,得_人_w A_AW(x)+ 5?仃 Vgj(x)+ 工必加(x) = 0: Uj > 0 jeZi-i34 例1mm f (x) =(X 一 12)2 + (x2 + 6)2sl.hL (x) = 8X + 4x2 -20 = 0gjx) = x; + x; + 3x1 一 4.5x2 -6.5 <0 gjd)=(兀 -9尸 + 兀；-64 W 0x = (2,1)' g (x) = 0, g2 (x) = -14,曾(a) = 0 / = W1,J”是線性幻燈片13幻燈片14幻燈片15幻燈片16幻燈片17W) = (-20,14y； Vg1(x) =(7-2.5)

8、t Vg2(x) = (-14,2)艸(兀)=(8,4)， © = 4,y = 0,片=一1 (壬)是線性獨(dú)立的VfW +(x) + w2Vg2 (x) + vg (x) = 03.5 例 2幻燈片18max x'Oxs.t.x'x < 1Q任意；不是一個(gè)凸優(yōu)化問題。max x9 Oxs.t.x'x < 13.5.1 KKT一 2Ox + lux = 0x'x <1z/>0“(1 一丫 x) = 03.5.2 KKT 的解 亍=0,帀=0,目標(biāo)值0幻燈片19幻燈片20 J 0 => Px = ux'x = w =&

9、gt;xQ的非負(fù)特征值u的特征向© x'Ox = ux'x = u 因此，選取Q的最人的非負(fù)特征值7解為和應(yīng)的特征向杲f的標(biāo)準(zhǔn)化，使 得?x = l.若所有特征向最是負(fù)的.x = 03.6 CQC是必耍的嗎？minXs.t.x -x2 <0x2 =0幻燈片21町行空間是(o,o)= 20、'7、(一 14、+ 4+ 0+ (一 1)4丿-2-5,1 2 )KKT：KKT：乘子不存在，當(dāng)(0,0)是丿d部極小值點(diǎn)，檢件Vg|(0,0)和 V7“(0,0)3.7約束規(guī)格Sla血條件：存在X0使得gj (x°) V 0 J二I,.,p且九(x

10、6;),對(duì)所有i = l,?w定理:在Slater條件下,KKT條件是必要的4充分性最優(yōu)性條件定理若 壬是p的可行解 p的可行集是凸集，/(x)是凸集 存在向最(u, V), 1/0巧(匚)+工知斥)+ £叫(打=01=1ygj(x) = 0j = l,.,p貝|J，X &p的全局最小值點(diǎn)4.1 證明 設(shè)x w p ,則+ /Lv e py對(duì)久 e 0J Sj (x + 2(x - x) < 0 =>gj (討(壬)<0幻燈片22幻燈片23幻燈片24 類似地，ht(x + 2(x-x)<0=>ht (x + 2(x-x)<0=> VA

11、r (x)*(x-x) = 0幻燈片 25 因此-打=(P_ m_ A _-+ 円心),(x-x)>0/(.v)>/(x)k J1冋幻燈片265凸優(yōu)化 在CQC卜，KKT條件一般都是必要的 對(duì)凸優(yōu)化問題，KKT條件是充分的 在CQC卜，對(duì)J：凸優(yōu)化問題，KKT條件是充要的 min f (x), s.t. Ax = b,x > 0 , f (x)是凸的,KKT 是充要的,即使沒有 CQC(約束規(guī)格條件)5.0.1超平面分離幻燈片27定理 設(shè)S是2T的一個(gè)非空閑凸子集，設(shè)”是一個(gè)不BJ'S的向昴，則，存在向”使得cPvc,最所WxeS證明見BT.P.1705.1凸性卜的證

12、明方法幻燈片28 假定壬是一個(gè)局部(因此也是整體)鼓優(yōu)解f(x) < /(x), gj (X) 0, j = l,.,p,/?f(X)= 0,7 = 1,.,7W 是不可行的設(shè)C7 = (w0,w,v,)| /f&x .f(x) (/(x),0,0)電 S幻燈片29 凸的 由超平面分離定理，存在一個(gè)向鼠(c°,c,“)：叫 > c°/Gw("o，s)1-1* c° no及>o對(duì)jwz (約束g,(x)<o是緊的)為什么？ i?(u0,M,v)G t7,則(m0 +A,m,v)gC7對(duì)人 no,因此V2 > O,Aro

13、 + 工CjUj 4- f 再 > cof(x) =>c0 >0選取("o,z/,v) = (/(x) + A,g1 (X),., gp (X),人(x),.,力p(A)G Upm CoUG) + 刃 +(x) + 工仏兒(x) > cj(x)j=lr=lpnt_讓A->0c°/(x) + £cjg'x)+ 工> c°/(x)>=i c0 > 0(此外需耍約束規(guī)格)pm/(X) +(x) + 工吶(X) >> 0J«1»«1/(X) + 工"jgj

14、 (x) + fl 也(x) s f(x) < /(x)+ J-l1-1p加工啡八丫)+»也(*) 因此/=皿 fW + £1 仃gj (x) + 工訥(X)< /=!P_工“局=0 n Ujgx) = 0 尸】 無約束最優(yōu)性條件vw+E uj % 丿 G)+E % w w = oJ=11=16應(yīng)用6.1線性優(yōu)化nun c'x幻燈片30sJ.Ax = bx>0min dxsl.Ax = b-x<06.1.1 KKTA幻燈片31c + A'u-v = 0v>0嚀j = oAx-b = 0x>0u = -iiA'u<c對(duì)偶町行性(cj - AjiXj = 0 互補(bǔ)性A