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

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

CLC Number:

90C25

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.

Trendmd

References

[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

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

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 6

Metrics

Comments

Recommended 10

[1]	HU Chao-Ming, WAN Zhong, WANG Xu. A New Nonmonotone Spectral Conjugate Gradient Algorithm [J]. Acta mathematica scientia,Series A, 2013, 33(1): 78-88.
[2]	Zhang Li; Zhou Weijun. On the Global Convergence of the Hager-Zhang Conjugate Gradient Method with Armijo Line Search [J]. Acta mathematica scientia,Series A, 2008, 28(5): 840-845.
[3]	Tong Xiaojiao ;He Wei. Lagrangian Globalization Projection Methods for Nonlinear Constrained Equations [J]. Acta mathematica scientia,Series A, 2008, 28(1): 96-108.
[4]	Zhou Changyin; He Guoping; Wang Yongli. An Active Constraints Identification Technique-based SSLE Algorithm and Its Convergence Analysis [J]. Acta mathematica scientia,Series A, 2007, 27(3): 535-540.
[5]	GAO Zi-You, Ren Hua-Ling, HE Guo-Ping. A New Sequential Systems of Linear Equations Algorithm Without Strict Complementary Slackness [J]. Acta mathematica scientia,Series A, 2004, 24(3): 275-284.
[6]	Shi Baochang, Chen Ting, Zhu Shijing. A Unified Approach to Method of Centers for Multiobjective Decision Making [J]. Acta mathematica scientia,Series A, 1997, 17(S1): 15-22.