凸二次規(guī)劃的原-對(duì)偶內(nèi)點(diǎn)算法概要

1、XIAN JIAOTONG I NIVEKSITY,最優(yōu)化理論與方法報(bào)告凸二次規(guī)劃的原對(duì)偶內(nèi)點(diǎn)算法西安交通大學(xué)理學(xué)院崔恒斌劉禧劉玉英lmagicqgsolTeSuh& .tx w b. wiwrc A ei>riiiitiCtiic pueitixT dcnnitc. ifiiiig lite Cunjualc Grtulicut ui&lxxilldantzig.pdSuht?» P【2 Illx' Dauitxix.J|ifinud-<hial nl|(<jnllutLSidvij th<* iw.rrn PfmiYinE4ti41

2、ii inililiMu Pa) fillclCCixiiiiH tvuiUdtcode.pdlirHW |M*ognunining) iu*ing x|prim>dHuK algovithmIgpdJhf hztamUrJ Dm山 Pursuit |iioblcin (九)h卜limdvhkaiXunUHu.llqe.lcgbarrierItnKT rner" limit(<k -Milving cpich ilical (i inuiiiuization (厲)llqcxevtQQNwtoci (和111«*) iteratiocib (or H>lv

3、iim quminiiKMl (i iiMiiiiuMatiuu i P,).ly cuiiMtnuiKMltvdmtzlgjogbarricr| IluTitt itiAfiuiuur idtutig1 Dautjig >dech“EZ廠tvdantzigjiQvxonMewuxxi itamiuua tut- iTIn».r/eq-lcgbarrier1 Bnrricr itmuhm卜 rqiudily1A niifiiinirmtixi 1 / V)tveqjDewtoaNorton iteratiini fcr (Fli).tvqc.logbarrier| Barrio

4、*quafiratk-Ally cotwtraiiKxi 1(八2廠tvqcjwwtooilratigo Sue iTla).凸二次規(guī)劃及其對(duì)偶問題凸二次規(guī)劃問題(P)min p(x) = xtQx+ctxst Ax=bx>0> Lagrange函數(shù)：L(x, y, z) = xTQx+crx- y1(.Ax-b)-zrx 2> Karush-Kuhn-Tucher條件:X為(P)的最優(yōu)解0Qx" + c-龍 y-z" = 0z" x* = 0, z* 0Ax* - b = 0, y' > 0凸二次規(guī)劃及其對(duì)偶問題根據(jù)Lagrang

5、e對(duì)偶原理:原凸二次規(guī)劃o max min L($y.z)y.z x>對(duì)偶問題：( max d(y, z) = xTQxb ¥” 2(D)rt. Qx + c A7 y- z=0,z>0Ax = b, x > 0>假設(shè)：1(i) 集合 S = xeRn| Ax = b,x>O0(ii) 集合 T = (y.z)|-Qx+Ary4- z 二 c, z>o工 0凸二次規(guī)劃及其對(duì)偶問題>將對(duì)數(shù)障礙罰函數(shù)法擴(kuò)展到凸二次規(guī)劃中: min ©In 齊st. Ax= b,x> 0(或障礙因子)其中“>0,稱為壁壘參數(shù)>相應(yīng)的KK

6、T條件為：'Ax = b, x > 0-Qx+ Ary+z = c,z>0 丨 XZe = “eV其中,X = diag(x15xzr-%)(原可行性)(對(duì)偶可行性)(互補(bǔ)松弛性)diag(Zp弓,心),e = (hL,l)T> 記上述系統(tǒng)的解(x(“),y(“),z(“)±v(“)2凸二次規(guī)劃及其對(duì)偶問題XI AN JMOTONG I NlYFRSm*>原問題與對(duì)偶問題的對(duì)偶間隙為:P(K)- d(x) = M“)T 次“)=n “顯然,當(dāng)“TO時(shí),p(x)-d(x)->0 >定理：在假設(shè)條件(i), (ii)下，上述系統(tǒng)的解W(“),

7、當(dāng)“TO時(shí)，x(“)、(y(“),z(“)分別收斂到 原問題(P)和對(duì)偶問題(D)的最優(yōu)解。I算法分析"" r I%XWN Jf AOTONG CNIVFRSmr號(hào) 初始點(diǎn)和障礙因子必須滿足如下條件：|f0-A|<()(xo)T(zp)其中,fO = £f，W，££ ' e = (l,LH > “二>障礙因子更新策略：才/(_刃石)>算法具體步驟：Stepl：選取切始點(diǎn)“列弋#”* 且滿足()式，給定較小的正數(shù)仇,給定終止亙足&>0, gk = 0 ；Step2：計(jì)算對(duì)偶間隙則停止迭代，x，為(P)

8、的近似解：否則轉(zhuǎn)Step3：Step3：令嚴(yán)=/k(l-J/Vn),計(jì)算AW，= (Ax,Ay,Az)Step4： w，" 蘭kkl 轉(zhuǎn)Step2AAx = b- Axk理注： -QAx. fAy.AzuQx11. AV-h+c* jFZkAxXkAz = /?e-ZkXke數(shù)值實(shí)驗(yàn)考慮如下凸二次規(guī)劃問題及其對(duì)偶問題:nun(P) 81+ £ + £ +7齊-5兀24為+ 9兀厶片_齊+齊=1320h斗m-7-2勺-為為x2=-S(D10 0 0-1 1 (f1 0 1 b2)." 20-7-5-249初始點(diǎn):x°= (6,4,lLl)T,y&

9、#176;= (-3, -3)T ,z°=(2,3,1,13)T 參數(shù)：5 = 0丄& = 0.12, £ = 0.01數(shù)值實(shí)驗(yàn)IliHiAlHMq 詢p迭代過程中目標(biāo)密數(shù)的變化情況1989年,和I.Adler給出了用原對(duì)偶內(nèi)點(diǎn) 算法求解凸二次規(guī)劃問題的一個(gè)版本，井證明了其交 雜度為O(nT),其中迭代次數(shù)為0(L)o主程序結(jié)論與展望原-對(duì)偶內(nèi)點(diǎn)算法融合了對(duì)偶原理、Lagra nge乘子法、內(nèi)點(diǎn)罰 函數(shù)法和Newton法，具有傳統(tǒng)優(yōu)化的特點(diǎn)，同時(shí)也大大擴(kuò) 大了內(nèi) 點(diǎn)算法的應(yīng)用領(lǐng)域；原-對(duì)偶內(nèi)點(diǎn)算法在解決線性規(guī)劃、二次規(guī)劃、半定規(guī)劃、錐規(guī)劃以及壓縮傳感、機(jī)器學(xué)習(xí)問題中起到了很好的作用；原-對(duì)偶內(nèi)點(diǎn)算法在初始值的確定上，靈活度遠(yuǎn)大于一般的內(nèi)點(diǎn)算法；對(duì)于原-對(duì)偶內(nèi)點(diǎn)算法加速技術(shù)的研究，主要還是集中在如