广西师范大学学报（自然科学版） ›› 2013, Vol. 31 ›› Issue (3): 65-71.

• • 上一篇    下一篇

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

张亚玲1, 穆学文2   

  1. 1.西安科技大学计算机学院,陕西西安710054;
    2.西安电子科技大学数学系,陕西西安710071
  • 收稿日期:2013-04-20 出版日期:2013-09-20 发布日期:2018-11-26
  • 通讯作者: 穆学文(1979—),男,山西朔州人,西安电子科技大学副教授,博士。E-mail:xdmuxuewen@hotmail.com
  • 基金资助:
    国家自然科学青年基金资助项目(11101320);西安科技大学校培育基金资助项目(2010032)

A Barzilai-Borwein Gradient Algorithm for Second-order Conic Programming

ZHANG Ya-ling1, MU Xue-wen2   

  1. 1.College of Computer Science,Xi'an Science and Technology University,Xi'an Shaanxi 710054,China;
    2.Department of Mathematics,Xidian University,Xi'an Shaanxi 710071,China
  • Received:2013-04-20 Online:2013-09-20 Published:2018-11-26

摘要： 二阶锥规划是一个非光滑的凸规划问题,在电子工程、控制论、组合优化等许多工程问题中有着广泛的应用。提出了一种求解二阶锥规划的Barzilai-Borwein 梯度算法。首先基于二阶锥规划的最优性条件,二阶锥规划问题被等价转化为等式系统。然后利用一种有效的光滑技巧把二阶锥转化为光滑函数,该等式系统等价转化为一个光滑的无约束优化问题。最后利用Barzilai-Borwein梯度法求解该无约束优化问题。Barzilai-Borwein梯度法是一种有效的一阶梯度算法,理论证明了该算法的收敛性。通过4个仿真算例测试提出的算法,实验结果表明了该算法有着较高的精度,需要较少的计算时间,所以该算法是可行的和有效的。

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

Abstract: Second-order cone programming is unsmooth convex programming problem,SOCP is widely applied in the engineering areas,such as electronic engineering,control theory,and combinational optimization.A Barzilai-Borwein algorithm for second-order conic programming is proposed.Firstly,based on the optimization condition of second-order cone programming,the second-order cone programming is equivalent to an equation system.Then,by the smooth function,the second-order conic is transmitted to a smooth function,and the equation system is equivalent to an unconstraint optimization problem.Finally,the Barzilai-Borwein algorithm is used to solve the constraint optimization problem.The Barzilai-Borwein gradient algorithm is an efficient gradient algorithm.The convergence of the algorithm has been improved.Four simulation numerical examples are used to test the new method,and the simulation results show the algorithm is feasible and efficient.

Key words: second-order conic programming, unconstraint optimization, Barzilai-Borwein gradient algorithm

中图分类号: 

  • O221.7
[1] LOBO M S,VANDENBERGHE L,BOYD S,et al.Application of second order cone programming[J].Linear Algebra and Its Applications,1998,284(1):193-228.
[2] BENSON H Y,VANDERBEI R J.Solving 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 S.Antenna array pattern synthesis via convex optimization[J].IEEE Transactions on Signal Processing,1997,45(3):526-532.
[4] LU Wu-sheng,HINAMOTO T.Optimal 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 Zhi-quan.Applications 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 al.Design 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 T.Polynomial 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 D.Second-order cone programming[J].Math Program:Series B,2003,95(1):3-51.
[10] KUO Yu-ju,MITTELMANN H D.Interior 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 C.Solving SOCP via a reduced augmented system[J].SIAM Journal on Optimization,2006,17(3):711-737.
[12] CHEN X D,SUN D,SUN J.Complementarity 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 P.Smoothing functions for second-order cone complementarity problems[J].SIAM Journal on Optimization,2002,12(2):436-460.
[14] CHEN Jein-shan,TSENG P.An 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 M.On 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 M.Two point step size gradient methods[J].IMA J Numer Anal,1988,8(1):141-148.
[19] SCALLE J L,LEFSCHETZ S.Stability by Lyapunov's Direct Method with Applications[M].New York:Academic,1961:61-81.
[20] GHAOUI L E,LEBRET H.Robust solutions to least-squares problems with uncertain data[J].SIAM Journal on Matrix Analysis and Applications,1997,18(4):1035-1064.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 广西师范大学学报（自然科学版）编辑部
地址：广西桂林市三里店育才路15号　邮编：541004
电话：0773-5857325　E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发