二阶锥规划一个超线性收敛的非内部连续化算法

运筹学学报 ›› 2015, Vol. 19 ›› Issue (1): 18-30.

二阶锥规划一个超线性收敛的非内部连续化算法

曾友芳^1,*, 唐春明¹

1. 广西大学数学与信息科学学院，南宁 530004

收稿日期:2014-09-28 出版日期:2015-03-15 发布日期:2015-03-15
通讯作者: 曾友芳 E-mail:zengyf@gxu.edu.cn
基金资助:
广西大学科研基金(No. XBZ111216)

A non-interior-point continuous algorithm with superlinear convergence for second-order cone programming

ZENG Youfang^1,*, TANG Chunming¹

1. College of Mathematics and Information Science, Guangxi University, Nanning 530004, China

Received:2014-09-28 Online:2015-03-15 Published:2015-03-15

摘要/Abstract

摘要： 基于非光滑向量值最小函数的一个新光滑函数, 建立了二阶锥规划一个超线性收敛的非内部连续化算法. 该算法的特点如下: 首先, 初始点任意; 其次, 每次迭代只需求解一个线性方程组即可得到搜索方向; 最后, 在无严格互补假设下, 获得算法的全局收敛性、强收敛性和超线性收敛性. 数值结果表明算法是有效的.

关键词: 二阶锥规划, 连续化算法, 向量值最小函数, 超线性收敛

Abstract: In this paper, based on a new smoothing function of the well-known nonsmooth vector-valued min-function, a non-interior-point continuous algorithm for second-order cone programming is presented. The features of this method are as follows: firstly, the starting point can be chosen arbitrarily; secondly, at each iteration, only one system of linear equations is performed for searching an improving direction; finally, global, strong and superlinear convergence are obtained without assumption of strict complementarity. The numerical results demonstrate the effectiveness of the algorithm.

Key words: second-order cone programming, continuous algorithm, vector-valued min-function, superlinear convergence

中图分类号:

O221.2

曾友芳, 唐春明. 二阶锥规划一个超线性收敛的非内部连续化算法[J]. 运筹学学报, 2015, 19(1): 18-30.

ZENG Youfang, TANG Chunming. A non-interior-point continuous algorithm with superlinear convergence for second-order cone programming[J]. Operations Research Transactions, 2015, 19(1): 18-30.

参考文献

Alizadeh F, Goldfarb D. Second-order cone programming [J]. Mathematical Programming: Series B, 2003, 95: 3-51.

Zeng Y F, Bai Y Q, Jian J B, et al. Two new predictor-corrector algorithms for second-order cone programming [J]. Applied Mathematics and Mechanics (English Edition), 2011, 32(4): 521-532.

Sun D, Sun J. Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions [J]. Mathematical Programming: Series A, 2005, 103: 575-581.

Zarantonello E H. Projections on Convex Sets in Hilbert Space and Spectral Theory [M]. New York: Academic Press, 1971.

Chen X D, Sun D, Sun J. Complementarity functions and numerical experiments on some smoothing Newton methods for second-order-cone complementarity problems [J]. Computational Optimization and Applications, 2003, 25: 39-56.

Chi X N, Liu S Y. Analysis of a non-interior continuation method for second-order cone programming [J]. Journal of Applied Mathematics and Computing, 2008, 27: 47-61.

Chen J S, Chen X, Tseng P. Analysis of nonsmooth vector-valued functions associated with second-order cones [J]. Mathematical Programming: Series B, 2004, 101: 95-117.

Fukushima M, Luo Z Q, Tseng P. Smoothing functions for second-order-cone complementarity problems [J]. SIAM Journal on Optimization, 2001, 12(2): 436-460.
Qi L, Sun D, Zhou G. A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities [J]. Mathematical Programming: Series A, 2000, 87: 1-35.

Fang L, He G P, Hu Y H. A new smoothing Newton-type method for second-order cone programming problems [J]. Applied Mathematics and Computation, 2009, 215: 1020-1029.

Zeng Y F, Jian J B, Tang C M. A new smoothing method based on nonsmooth FB function for second-order cone programming [C]//Advanced Materials Research, Materials Science and Information Technology II, 2012, 532-533: 1000-1005.

Qi L, Sun J. A nonsmooth version of Newton's method [J]. Mathematical Programming, 1993, 58: 353-367.
Bai Y Q, Wang G Q, Roos C. Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions [J]. Nonlinear Analysis, 2009, 70: 3584-3602.

Pataki G, Schmieta S. The DIMACS library of mixed semidefinite-quadratic-linear programs, Computational Optimization Research Center, Columbia University, New York. http://dimacs.rutgers.edu/Challenges/Seventh/Instances/.

Chen J S, Pan S H. A survey on SOC complementarity functions and solution methods for SOCPs and SOCCPs [J]. Pacific Journal of Optimization, 2012, 8(1): 33-74.

[1]	任烨权, 白延琴, 李倩, 余长君, 张连生. 一个求解池化问题的二阶锥逼近算法[J]. 运筹学学报, 2020, 24(2): 61-72.
[2]	张景, 白延琴. 二阶锥规划的基于自协调指数核函数的原始-对偶内点算法[J]. 运筹学学报, 2014, 18(4): 11-24.
[3]	赵奇, 张燕. 求解极小极大问题的非单调过滤算法[J]. 运筹学学报, 2012, 16(2): 91-104.
[4]	简金宝, 韦小鹏, 曾汉君, 潘华琴. 一般约束优化基于识别函数的模松弛算法[J]. 运筹学学报, 2011, 15(2): 28-44.