2024年5月19日发(作者：程序打开方式怎么还原)

二阶锥规划的一种Barzilai-Borwein梯度算法

张亚玲;穆学文

【摘 要】二阶锥规划是一个非光滑的凸规划问题,在电子工程、控制论、组合优化

等许多工程问题中有着广泛的应用.提出了一种求解二阶锥规划的Barzilai-

Borwein梯度算法.首先基于二阶锥规划的最优性条件,二阶锥规划问题被等价转化

为等式系统.然后利用一种有效的光滑技巧把二阶锥转化为光滑函数,该等式系统等

价转化为一个光滑的无约束优化问题.最后利用Barzilai-Borwein梯度法求解该无

约束优化问题.Barzilai-Borwein梯度法是一种有效的一阶梯度算法,理论证明了该

算法的收敛性.通过4个仿真算例测试提出的算法,实验结果表明了该算法有着较高

的精度,需要较少的计算时间,所以该算法是可行的和有效的.

【期刊名称】《广西师范大学学报（自然科学版）》

【年(卷),期】2013(031)003

【总页数】7页(P65-71)

【关键词】二阶锥规划;无约束优化问题;Barzilai-Borwein梯度法

【作 者】张亚玲;穆学文

【作者单位】西安科技大学计算机学院,陕西西安710054;西安电子科技大学数学

系,陕西西安710071

【正文语种】中 文

【中图分类】O221.7

二阶锥规划是在有限个二次锥的笛卡儿乘积的仿射子空间之交上极小化或极大化一

个线性函数的问题,其原对偶标准形式如下[1]

其中A=(A1，…，AN)∈Rm×n,b∈Rm,y∈Rm,x=(x1,…，xN)∈Rn,c=(c1，…，

cN)∈Rn,s=(s1，…，sN)∈Rn,Ai∈Rm×ni,ci,si,xi∈Rni,i=1,…,N,n1+…+nN=n。

Ki是在ni维空间的标准二阶锥,即

二阶锥规划是一个非光滑的凸规划问题,线性规划和凸二次规划可转化为二次锥规

划,同时二次锥规划也可转化为半定规划[1-2]。二次锥规划在电子工程、控制论、

组合优化等方面,如雷达方阵权的设计[3]、自适应脉冲滤波器的设计[4-6]、最大割

问题[7]有广泛的应用,所以对二次锥规划的研究有着非常重要的意义。

求解二次锥规划存在一些有效的多项式时间算法，这些方法包括内点算法[8-11]、

光滑牛顿算法[12-13]、优值函数方法[14]以及半光滑牛顿算法[15]。后3种算法

都是基于二阶锥互补函数或者优值函数设计对应的二阶算法。原对偶内点算法也是

一种二阶算法，算法的单步迭代需要计算一个等式系统。这些算法在求解中小规模

的问题和一些较大规模问题比较有效。但实际问题许多是大规模的甚至是超大规模

的。这样,已有的二阶算法由于计算量大,占用很大的内存,且需要很长时间,所以不能

有效地求解,甚至无法求解。

近年来,一阶算法成为求解大规模问题的一种可以选择的有效算法，虽然一阶算法

迭代步骤需要更多，但是一阶算法单步迭代只需要计算梯度即可。对于梯度算法，

搜索步长非常重要，不同的搜索步长决定不同的算法效率。文献[16]给出了一种有

效的线搜索方法并证明了该方法的收敛性。本文提出一种求解二阶锥规划的

Barzilai-Borwein梯度算法。利用一种有效的光滑函数,把二阶锥规划问题等价转

化一个光滑的无约束优化问题。利用已有的Barzilai-Borwein梯度法求解该无约

束优化问题。理论证明该算法的收敛性并进行仿真实验来验证算法的可行性和有效

性。

假设原对偶二阶锥规划问题的严格可性解集非空,根据二阶锥规划的对偶定理可知,

原规划和对偶规划问题的求解等价于求解如下系统

系统(1)是二阶锥规划的最优性条件[1]。

由于标准二阶锥是非光滑的,利用文献[2]给出的光滑化函数,得到其等价形式。

定义

由文献[2]可知函数gi、hi是光滑的凸函数。令

在构造无约束函数之前给出如下定理。

定理1 函数Fi(x),Hi(s)如上定义,则有如下结论成立。

a) Fi(x)、Hi(s)是可微凸函数,且

b) Fi(x)、Hi(s)的一阶梯度分别为

且xFi(x),sHi(s)是局部Lipschitz连续的,其中i=1，…,N。

证明 a) 由于

而Fi(x)是以下两个函数的复合函数

这里Fi=ψ(w)是单调递增的可微凸函数，w=gi(x)是可微的凸函数，则复合函数

Fi(x)是一个可微的凸函数。

同理可证,Hi(s)也是一个可微的凸函数。由以上证明显然可见

b) 参见文献[17]中定理1的证明方法。证毕。

由定理1的结论可得，最优性条件等价为

定义z-=(1/2)(zz|),z∈Rn。易证如下等价形式成立：

所以有

下面给出一个函数

显然,函数E(x,y,s)非负。

定理2 E(x,y,s)=0⟺(x,y,s)是二次锥规划(P)和(DP)的最优解。

证明 由定理1以及式(3)可得:E(x,y,s)=0⟺(x,y,s)是二次锥规划原问题(P)和对偶问题

(DP)的最优解。

定理3 E(x,y,s)是一个可微的凸函数。

证明 显然||cTx-bTy||2，||ATy+s-c||2以及||Ax-b||2是可微凸函数,又由定理1可

得Hi(s),Fi(x),||||2,||||2是可微凸函数，所以E(x,y,s)是可微凸函数。定理得证。

显然

其中ek表示第k个元素为1,其余都为0的n维向量。

由上面结论可知，求解原对偶的二阶锥规划问题转化为无约束优化问题的极小值，

即

另外，由定理3知，E(x,y,s)是一个可微的凸函数，所以无约束优化问题(4)是一个

凸规划，利用凸规划的性质以及无约束问题的一阶必要条件可知，求解无约束优化

问题(4)的最优解等价于求解

这里

下面给出等价性定理。

定理4 假定M={z(x,y,s)∈R2n+m|E(z)=0}是无约束问题(4)的最优解集,且

Ω={z(x,y,s)}是二次锥规划的原问题和对偶问题的最优解集。则M=Ω。

证明 假定z∈M,z*∈Ω,由定理2可得E(z*)=0。由定理3可知E(z)是可微的凸函

数。由凸函数的性质可得

所以有

由z∈M,可得E(z)≤0。而根据无约束函数的定义可知E(z)≥0,所以有E(z)=0。由

定理2可得z∈Ω,所以M⊆Ω。

假定z∈Ω,由定理2可得E(z)=0,又由定理1可得

由式(2)可得

根据最优性条件(1)及式(6)～(8)可得E(z)=0,即z∈M,所以M⊇Ω。所以M=Ω,定

理得证。证毕。

变求解该无约束优化问题(4)需要利用迭代方法，如最简单的梯度下降法，当然还

有共轭梯度法、拟牛顿法、L-M法等。本文利用Barzilai-Borwein梯度算法求解

无约束优化问题(4)。

Barzilai-Borwein梯度算法最早由Barzilai和Borwein[18]提出，用来克服梯度下

降法收敛速度慢的缺点。该方法利用了前一步迭代的信息，设计一种步长，使这种

简单的步长能够含有二阶海塞矩阵的部分信息。在迭代过程中，利用负梯度方向，

结合新的Barzilai-Borwein步长，提高了最速下降算法的收敛效率，理论上能够

证明Barzilai-Borwein梯度算法对于变量维数为2的凸二次函数具有R-超线性收

敛的性质，R的阶数为[18]。下面给出Barzilai-Borwein梯度算法。

对无约束优化问题(4)，设第k-1步迭代得到的解为zk-1(xk-1,yk-1,sk-1)，令

假设第k步迭代得到的解为zk(xk,yk,sk)，则第k+1步迭代公式为

这里dk=-HkE(zk)，其中Hk=λkI,I是单位阵。选取的下降方向与拟牛顿法选取的

方向相似，但是拟牛顿法需要利用秩1和秩2矩阵校正生成，而Barzilai-

Borwein梯度方法只需要求解一个有效的λk，使得Hk尽量满足牛顿条件，即满

足

或者

由于Hk=λkI以及式(11)和(12)，可以得到两种步长

和

下面给出Barzilai-Borwein梯度方法。

步骤1：给定初始的z0,λ0=1，算法终止精度ε。令k=0。

步骤2：根据迭代公式(10)计算zk。

步骤3：判定||E(zk)||≤ε是否成立；若成立，则算法停止；否则，令k=k+1，转

步骤4。

步骤4:利用公式(13)或者(14)计算新的步长λk，转步骤2。

Barzilai-Borwein梯度方法已经运用非常成熟，其收敛性结果非常容易给出。

定理5 无约束优化问题(4)有解,且解是唯一的。

证明 由定理1可知xFi(x),sHi(s)局部Lipschitz连续,则是局部Lipschitz连续的。

又因为(xi0)-,(si0)-,i=1,…,N是局部Lipschitz连续的[17],所以可得E(z)是局部

Lipschitz连续的。由系统(5)的存在唯一性定理可知[19],无约束优化问题(4)有解,

且解是唯一的。

定理6 Barzilai-Borwein梯度方法产生的序列{zk}必有一个聚点，并且该聚点一定

是驻点。

证明 根据定理5，以及函数E(x,y,s)的特性，证明参见文献[18]。

由定理3可知，E(x,y,s)是可微的凸函数，且由定理6知，Barzilai-Borwein梯度

方法产生问题(4)唯一的驻点，所以很容易知道该驻点是问题(4)的全局极小点，由

定理4可知，该全局极小点也是原对偶二阶锥规划问题的最优解。

本文利用Matlab 7.0编程设计Barzilai-Borwein梯度方法，选取下面4个数值算

例验证算法的有效性。

例1 对二次锥规划的原对偶问题(P)和(DP),取

该问题的二次锥数目为N=1，1个二次锥的维数为n1=4。分别取初始解为:

得到相同的最优解

相同最优值为21.750。

例2 对二次锥规划的原对偶问题(P)和(DP),取

该问题的二次锥数目为N=2，2个二次锥的维数为n1=n2=3。取初始解为:

得到相同的最优解：

相同最优值为18。

例3 对二次锥规划的原对偶问题(P)和(DP),取

该问题的二次锥数目为N=3，3个二次锥的维数为n1=n2=n3=3。取初始解为:

得到相同的最优解为

相同最优值为18.797 9。

例4 下面我们测试文献[20]提出的一个鲁棒最小二乘问题，

这里

该问题的对偶问题容易求得[19]。利用神经网络算法得到该问题的最优解:

最优值为3.332 9。

我们还取了许多不同的初值,无论初值是否满足可行解的要求,总能得到相同最优解

和最优值。由此说明了算法的全局一致稳定性和有效性。

本文给出了求解二阶锥规划问题的一阶Barzilai-Borwein梯度算法。相对于二阶

算法，一阶算法的单步迭代简单，而且Barzilai-Borwein梯度算法利用了海塞矩

阵的部分信息，收敛速度相比较梯度下降法较快。

【相关文献】

[1]LOBO M S,VANDENBERGHE L,BOYD S,et ation of second order cone

programming[J].Linear Algebra and Its Applications,1998,284(1):193-228.

[2]BENSON H Y,VANDERBEI R g problems with semidefinite and related

constraints using interior-point methods for nonlinear programming[J].Math

Program:Series B,2003,95(2):279-302.

[3]LEBRET H,BOYD a array pattern synthesis via convex optimization[J].IEEE

Transactions on Signal Processing,1997,45(3):526-532.

[4]LU Wu-sheng,HINAMOTO l design of IIR digital filters with robust stability

using conic-quadratic-programming updates[J].IEEE Transactions on Signal

Processing,2003,51(6):1581-1592.

[5]MURAMATSU M,SUZUKI T.A new second-order cone programming relaxation for Max-

cut problems[J].Journal of the Operations Research Society of Japan,2003,46(2):164-177.

[6]LUO ations of convex optimization in signal processing and digital

communication[J].Math Program:Series B,2003,97(1/2):177-207.

[7]RIKA I,FUJIE T,SUYAMA K,et methods of FIR filters with signed power of two

coefficients using a new linear programming relaxation with triangle

inequalities[J].International Journal of Innovative Computing,Information and

Control,2006,2(1):441-448.

[8]MONTEIRO R D C,TAKASHI mial convergence of primal-dual algorithms for the

second-order cone program based on the MZ-family of directions[J].Math Program:Series

B,2000,88(1):61-83.

[9]ALIZADEH F,GOLDFARB -order cone programming[J].Math Program:Series

B,2003,95(1):3-51.

[10]KUO Yu-ju,MITTELMANN H or point methods for second-order cone

programming and OR applications[J].Computational Optimization and

Application,2004,28(3):255-285.

[11]CAI Zhi,TOH K g SOCP via a reduced augmented system[J].SIAM Journal on

Optimization,2006,17(3):711-737.

[12]CHEN X D,SUN D,SUN mentarity functions and numerical experiments for

second-order cone complementarity problems[J].Computational Optimization and

Applications,2003,25(1/3):39-56.

[13]FUKUSHIMA M,LUO Zhi-quan,TSENG ing functions for second-order cone

complementarity problems[J].SIAM Journal on Optimization,2002,12(2):436-460.

[14]CHEN Jein-shan,TSENG unconstrained smooth minimization reformulation of the

second-order cone complementarity problems[J].Mathematical Programming:Series

B,2005,104(2/3):293-327.

[15]KANZOW C,FERENCZI I,FUKUSHIMA the local convergence of semismooth

Newton methods for linear and nonlinear second-order cone programs without strict

complementarity[J].SIAM Journal on Optimization,2009,20(1):297-320.

[16]陆春桃.一些修正的线搜索及其收敛性[J].广西师范学院学报：自然科学版,2006,23(2):13-19.

[17]LEUNG Y,CHEN Kai-zhou,JIAO Yong-chang,et al.A new gradient-based neural network

for solving linear and quadratic programming problems[J].IEEE Eransactions on Neural

Networks,2001,12(5):1074-1083.

[18]BARZILAI J,BORWEIN J point step size gradient methods[J].IMA J Numer

Anal,1988,8(1):141-148.

[19]SCALLE J L,LEFSCHETZ ity by Lyapunov's Direct Method with

Applications[M].New York:Academic,1961:61-81.

[20]GHAOUI L E,LEBRET solutions to least-squares problems with uncertain

data[J].SIAM Journal on Matrix Analysis and Applications,1997,18(4):1035-1064.