求解二次錐規劃問題的非精確光滑算法

于桃艷, 劉三陽, 蔡曉娜, 張 菲

(西安電子科技大學 理學院, 西安 710071)

0 引 言

二次錐規劃是基于有限個二次錐的笛卡爾乘積的仿射子空間之交上的極小化或極大化線性函數[1]. 本文考慮下列二次錐規劃：

(1)

其對偶規劃為

(2)

其中:A∈Rm×n;c∈Rn;b∈Rm; 且集合

K={x=(x0,x1)∈R×Rn-1:x0≥‖x1‖}

是一個維數為n的二次錐, ‖·‖表示Euclid范數. 對任意的x=(x1,x2)∈R×Rn-1和s=(s1,s2)∈R×Rn-1,x°s=(xTs,x1s2+s1x2)∈R×Rn-1. 其中“°”表示Euclid約當代數中的約當積.

此外, 本文假設問題(1),(2)是嚴格可行的, 則問題(P)和(D)等價于下列最優性條件：

Ax=b,ATy+s=c,x°s=0,x∈K,s∈K.

近年來, 二次錐規劃問題在許多領域受到廣泛關注, 如支持向量機[2]和濾波器設計[3]等, 對于求解該類問題目前已有許多算法, 如內點算法[4]、 非內點連續算法[5]、 無導數下降法[6]和路徑跟蹤法[7]等. 而對于可行內點算法其要求初始點必須嚴格可行, 無導數下降法對函數要求較高, 一般要強單調或者單調, 且〈▽xφnew(x,y),▽yφnew(x,y)〉≥0, 而對很多函數計算通常特別復雜, 也很難判斷其正負性, 而光滑牛頓算法具有以下優勢[8]：

1) 算法對初始點無要求, 不一定要滿足可行, 即算法可以從任意點開始;

2) 算法只需解一個線性系統, 且得到唯一搜索方向;

3) 算法可全局收斂到最優解, 且在不需要強互補性的條件下可達到Q-超線性收斂速率.

因為牛頓方程一般不能求出它的精確解, 只能求出它的近似解, 因此文獻[9]對于半正定互補問題(SDCP)提出了一種非精確非內點連續算法, 得到了其超線性收斂速率. 基于此, 本文將其應用到二次錐上, 得到了二次錐上的非精確光滑算法. 因為非單調線性策略在實際問題中能提高找到解的可能性及收斂速率, 且能得到較好的數值結果, 故選擇步長時引進了非單調線性技術. 最后證明了該算法具有局部二次收斂速率.

1 預備知識

對二次錐上任意向量x=(x1,x2)∈R×Rn-1, 定義其譜分解為x=λ1u1+λ2u2, 其中λi和ui(i=1,2)分別為x的特征值和相應的特征向量, 且

λi=x1+(-1)i+1‖x2‖,

w∈Rn-1是使得‖w‖=1的任意向量. 如果x2≠0, 則上述分解是唯一的.

x°s=Lxs=LxLse,

且Lx為正定(半正定)矩陣當且僅當x∈intK(x∈K), 即x>K0(x≥K0).

2 一類新的光滑函數及其性質

考慮如下Fischer-Burmeister函數[10]:

φFB(x,y)=x+y-(x2+y2)1/2,

滿足

φFB(x,y)=0 ?x°y=0,x∈K,y∈K.

由于φFB(x,y)是非光滑的, 因此對φFB(x,y)進行光滑化可得新的向量值函數φ: R×Rn×Rn→Rn, 定義為

(3)

定理11) 函數φ(u,x,y)在任意點Lipschitz連續、 強半光滑且連續可導, 其Jacobi矩陣為

(4)

3 非精確光滑算法

本文基于光滑函數(3), 對于大規模的SOCP問題, 提出一種非精確光滑算法. 記z∶=(u,x,c-ATy)∈Rn×Rn×R, 根據光滑函數(3), 定義函數為H: R2n+1→R2n+1為

(5)

令z∶=(u,x,y), Δzk∶=(Δuk,Δxk,Δyk), 在精確光滑算法的每步迭代中, 需求出下面線性方程系統的精確解：

▽H(zk)Δzk=-H(zk),

(6)

其中▽H(zk)為每個迭代點zk的Jacobi矩陣. 由于方程(6)一般只能求出其近似解, 且對于大規模問題即當系數矩陣的維數越來越高時, 求解方程(6)會導致使解的準確性越來越小, 即偏離程度越來越大, 因此為保證精確解在一定的范圍內, 需解下列方程系統：

其中:β(zk)=γ‖H(zk)‖min(1,‖H(zk)‖),γ∈(0,1);μ>0是常數, 且滿足γμ<1; ‖rk‖=ηk‖H(zk)‖2,ηk∈(0,1),rk為殘余向量,ηk為強迫項用于控制精確度.

算法1非精確光滑算法.

1) 如果‖H(zk)‖≤ε, 則停止, 否則轉2);

4) 設zk+1=zk+θkΔzk,ηk+1=v(ηk), 置k=k+1, 轉1).

假設1矩陣A是行滿秩的.

引理1[8]對任意的x,y∈Rn,w>K0, 有

w2>Kx2+y2?Lw-Lx>0,Lw-Ly>0, (Lw-Lx)(Lw-Ly)>0.

定理2設z=(u,x,y)∈R×Rn×Rn,H: R2n+1→R2n+1定義如式(5), 則下列結論成立:

1)H在任意點全局Lipschitz連續、 光滑且連續可微, 且其Jacobi矩陣為

2) 在假設1下, ▽H(z)對任意的u>0是非奇異的, 即算法1中步驟2)是適定的.

證明： 1) 由式(4)可知顯然成立.

2) 設Δz∶=(Δu,Δx,Δy), 對任意固定的u>0, 要證▽H(z)是非奇異的等價于▽H(z)Δz=0只有零解, 即判斷

(7)

因為

所以由引理1可得

(8)

其中殘余向量r滿足‖r‖≤η‖H(z)‖, 則由式(8)可得Δu=-u+μβ(z), 從而

u+θΔu=(1-θ)u+θμβ(z)>0.

(9)

定義g(θ)=φ(zk+θΔzk)-φ(zk)-θ(φ′(zk))TΔzk, 則由φ的連續性可得‖g(θ)‖=o(θ), 于是

當‖H(zk)‖>1時,β(zk)=γ‖H(zk)‖min(1,‖H(zk)‖)=γ‖H(zk)‖; 當‖H(zk)‖≤1時,β(zk)=γ‖H(zk)‖min(1,‖H(zk)‖)=γ‖H2(zk)‖≤γ‖H(zk)‖. 故有

定理4設zk∈Ω(μ), 且zk+1是由算法1產生的序列, 則zk+1∈Ω(μ).

證明： 由zk∈Ω(μ)有uk≥μβ(zk). 由‖H(zk+1)‖≤‖H(zk)‖, 再結合式(9), 分以下兩種情形：

1) 當‖H(zk)‖>1時,

β(zk+1)=γ‖H(zk+1)‖min(1,‖H(zk+1)‖)=γ‖H(zk+1)‖≤γ‖H(zk)‖,

2) 當H(zk)≤1時,

β(zk+1)=γ‖H(zk+1)‖2≤γ‖H(zk)‖2,

綜上可知, 對任何情況uk+1-μβ(zk+1)≥0都成立, 即zk+1∈Ω(μ).

4 收斂性分析

假設2鄰域Ω(μ)是有界的.

引理2設序列{zk}是由算法1得到的, 如果假設2成立, 則序列{zk}的任意聚點都是H(u,x,y)=0的解.

證明類似于文獻[9]的定理3.1.

定理5(局部二次收斂性) 序列{zk}是由算法1得到的且收斂到z*, 如果假設2成立, 殘余向量序列rk滿足‖rk‖=O(‖H(z)‖2), 則序列{zk}局部二次收斂到z*, 即‖zk+1-z*‖=O(‖zk-z*‖2), 且uk+1=O((uk)2).

證明： 由▽H(zk)的非奇異性可知, 對任意的k≥0, ?C>0, 使得‖▽H(zk)‖≤C. 又因為H(z)是全局Lipschitz連續且強半光滑的, 則當k足夠大時, 有

‖H(zk)‖=‖H(zk)-H(z*)‖=O(‖zk-z*‖),

‖H(zk)-H(z*)-▽H(zk)(zk-z*)‖=O(‖zk-z*‖2),

故可得

由于當zk充分接近z*時, 有zk+1=zk+Δzk, 故有‖zk+1-z*‖=O(‖zk-z*‖2).

又因為

uk+1=uk+Δuk=μβ(zk)=μγ‖H(zk)‖2,

(12)

故由式(11),(12)可得

即uk+1=O((uk)2).

綜上, 本文給出了一種基于一類新的擾動Fischer-Burmeister函數的二次錐規劃非精確光滑算法. 該算法的每步只要求解一個線性系統, 且不要求求出牛頓方程的精確解, 在確定步長的非單調策略下能保證每個迭代點不會遠離最優解.當引進的殘余向量rk滿足‖rk‖=O(‖H(z)‖2)時, 能得到算法的局部二次收斂速率.

[1] Alizadeh F, Goldfarb D. Second-Order Cone Programming [J]. Mathematical Programming, 2003, 95： 3-51.

[2] Debnath R, Muramatsu M, Takahashi H. An Effcient Support Vector Machine Learning Method with Second-Order Cone Programming for Large-Scale Problems [J]. Applied Intelligence, 2005, 23(3)： 219-239.

[3] Shivaswamy P K, Bhattacharyya C, Smola A J. Second Order Cone Programming Approaches for Handling Missing and Uncertain Data [J]. Journal of Machine Learning Research, 2006, 7： 1283-1314.

[4] KUO Yu-ju, Mittelmann H D. Interior Point Methods for Second-Order Cone Programming and OR Applications [J]. Computational Optimization and Applications, 2004, 28(3)： 255-285.

[5] LIANG Fang, HE Guo-ping. A New Non-interior Contimuation Method for Second-Order Cone Programming [J]. International Joint Conference on Computational Sciences and Optimization, 2009, 2： 719-722.

[6] PAN Shao-hua, CHEN Jein-shan. A Linearly Convergent Derivative-Free Descent Method for the Second-Order Cone Complementarity Problem [J]. Optimization, 2010, 59(8)： 1173-1197.

[7] Tsuchiya T. A Polynomial Primal-Dual Path-Following Algorithm for Second-Order Cone Programming [R]. Tokyo: The Institute of Statistical Mathematics, 1997.

[8] Fukushima M, LUO Zhi-quan, Tseng P. Smoothing Functions for Second-Order-Cone Complimentarity Problems [J]. SIAM Journal on Optimization, 2002, 12(2)： 436-460.

[9] RUI Shao-ping, XU Cheng-xian. Inexact Non-interior Continuation Method for Solving Large-Scale Monotone SDCP [J]. Applied Mathematics and Computation, 2009, 215(7)： 2521-2527.

[10] SUN De-feng, SUN Jie. Strong Semismoothness of the Fischer-Burmeister SDC and SOC Complementarity Functions [J]. Mathematical Programming: Ser A, 2005, 103(3)： 575-581.