二阶锥规划的一步光滑牛顿法

数学物理学报 ›› 2012, Vol. 32 ›› Issue (4): 768-778.

二阶锥规划的一步光滑牛顿法

汤京永^1,2, 贺国平³

1.信阳师范学院数学与信息科学学院河南信阳 464000;
2.上海交通大学数学系上海 200240;
3.山东科技大学信息科学与工程学院山东青岛 266510

收稿日期:2010-12-29 修回日期:2012-01-13 出版日期:2012-08-25 发布日期:2012-08-25
基金资助:
国家自然科学基金(10971122)、山东省自然科学基金(Y2008A01)和高等学校博士学科点专项科研基金(20093718110005)资助

A One-step Smoothing Newton Method for Second-order Cone Programming

TANG Jing-Yong^1,2, HE Guo-Ping³

1.College of Mathematics and Information Science, Xinyang Normal University, Henan |Xinyang 464000;
2.Department of Mathematics, Shanghai Jiaotong University, Shanghai 200240；
3.College of Information Science and Engineering, Shandong University of Science and Technology, Shandong Qingdao 266510

Received:2010-12-29 Revised:2012-01-13 Online:2012-08-25 Published:2012-08-25
Supported by:
国家自然科学基金(10971122)、山东省自然科学基金(Y2008A01)和高等学校博士学科点专项科研基金(20093718110005)资助

摘要/Abstract

摘要：

研究一个新的求解二阶锥规划的一步光滑牛顿法. 该算法基于向量最小值函数的新光滑函数, 将二阶锥规划问题转化成一个非线性方程组问题, 再利用牛顿法求解此方程组. 算法不要求初始点及其迭代点严格可行, 并且在每一步迭代只需求解一个线性方程组并进行一次线性搜索. 在不需要满足严格互补条件下, 证明了算法是全局收敛且是局部二阶收敛的. 数值试验表明算法是有效的.

关键词: 二阶锥规划, 光滑牛顿法, 光滑函数, 全局收敛, 二阶收敛

Abstract:

In this paper, a new one-step smoothing Newton method is investigated for solving the second-order cone programming (SOCP). Based on a new smoothing function of the vector minimum function, the proposed algorithm reformulates the SOCP as a nonlinear system of equations and then applies Newton's method to the system. This algorithm does not require the initial point and iteration points to be in the sets of strictly feasible solutions, and solves only one linear system of equations and performs only one line search at each iteration. Without strict complementarity, it is proved that the proposed algorithm is globally and locally quadratically convergent. Numerical experiments demonstrate the feasibility and efficiency of our algorithm.

Key words: Second-order cone programming, Smoothing Newton method, Smoothing function, Global convergence, Quadratical convergence

中图分类号:

90C25

汤京永, 贺国平. 二阶锥规划的一步光滑牛顿法[J]. 数学物理学报, 2012, 32(4): 768-778.

TANG Jing-Yong, HE Guo-Ping. A One-step Smoothing Newton Method for Second-order Cone Programming[J]. Acta mathematica scientia,Series A, 2012, 32(4): 768-778.

参考文献

[1] Lobo M S, Vandenberghe L V, Boyd S. Application of the second-order cone programming. Linear Algebra and its Applications, 1998, 284: 193--228

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

[3] Bai Y Q, Wang G Q, Roos C. Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions. Nonlinear Analysis, 2009, 70: 3584--3602

[4] Monteiro R D C, Tsuchiya T. Polynomial convergence of primal-dual algorithms for the second order program based the MZ-family of directions. Mathematical Programming, 2000, 88: 61--93

[5] Peng J, Roos C, Terlaky T. A new class of polynomial primal-dual interior-point methods for second-order cone optimization based on self-regular proximities. SIAM Journal on Optimization, 2002, 13: 179--203

[6] Chi X N, Liu S Y. An infeasible-interior-point predictor-corrector algorithm for the second-order cone programming. Acta Mathematica Scientia, 2008, 28: 551--559

[7] Kuo Y J, Mittelmann H D. Interior point methods for second-order cone programming and OR applications. Computational Optimization and Applications, 2004, 28: 255--285

[8] Burke J, Xu S. A Non-interior Predictor-corrector Path-following Algorithm for LCP//Fukushima M, Qi L, eds. Reformulation: Nonsmooth, Piecewise Smooth and Smoothing Methods. Boston: Kluwer Academic Publishers, 1999: 45--64

[9] Burke J, Xu S. A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem. Mathematical Programming, 2000, 87: 113--130

[10] Chen B, Xiu N. A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions. {SIAM Journal on Optimization}, 1999, 9: 605--623.

[11] Qi L, Sun D. Improving the convergence of non-interior point algorithm for nonlinear complementarity problems. {Mathematics of Computation}, 2000, 69: 283--304

[12] Sun D, Sun J. L\"{o}wner operator and spectral functions in Euclidean Jordan algebras. Mathematics of Operations Research, 2008, 33, 421--445

[13] Engelke S, Kanzow C. Improved smoothing-type methods for the solution of linear programming. Numerical Mathematics, 2002, 90: 487--507

[14] Tseng P. Error Bounds and Superlinear Convergence Analysis of Some Newton-type Methods in Optimization//Pillo G Di, Giannessi F, eds. Nonlinear Optimization and Related Topics. Boston: Kluwer Academic Publishers, 2000: 445--462

[15] Huang Z H, Han J, Chen Z. A predictor-corrector smoothing Newton algorithm, based on a new smoothing function, for solving the nonlinear complementarity problem with a P₀ function. Journal of Optimization Theory and Applications, 2003, 117: 39--68

[16] Fukushima M, Luo Z Q, Tseng P. Smoothing functions for second-order-cone complementarity problems. SIAM Journal on Optimization, 2002, 12: 436--460

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

[18] Qi L, Sun D, Zhou G. A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Mathematical Programming, 2000, 87: 1--35

[19] 房亮, 贺国平, 王永丽. 带有P₀函数的非线性互补问题的一个新的非内点连续算法. 数学物理学报, 2011, 31: 229--238

[20] Jiang H. Smoothed Fischer-Burmeister Equation Methods for the Complementarity Problem. Technical Report. Australia: Department of Mathematics, the University of Melbourne, Parille, Victoria, 1997

[21] Clarke F H. Optimization and Nonsmooth Analysis. Wiley, New York: SIAM, 1990