×

zbMATH — the first resource for mathematics

A new one-step smoothing Newton method for second-order cone programming. (English) Zbl 1265.90229
The paper deals with the second-order cone programming (SOCP) problem. The authors present a one-step smoothing Newton method for solving the SOCP problem based on a new smoothing function of the Fischer-Burmeister function. The algorithm solves only one system of linear equations and performs only one Armijo-type line-search per iteration. Global and local quadratic convergence under standard assumptions are proved. Numerical experiments demonstrate efficiency of the algorithm.

MSC:
90C25 Convex programming
90C46 Optimality conditions and duality in mathematical programming
65K05 Numerical mathematical programming methods
49M15 Newton-type methods
Software:
SDPT3
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] F. Alizadeh, D. Goldfarb: Second-order cone programming. Math. Program. 95 (2003), 3–51. · Zbl 1153.90522
[2] Y.Q. Bai, G.Q. Wang, C. Roos: Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions. Nonlinear Anal., Theory Methods Appl. 70 (2009), 3584–3602. · Zbl 1190.90275
[3] B. Chen, N. Xiu: A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions. SIAM J. Optim. 9 (1999), 605–623. · Zbl 1037.90052
[4] J. S. Chen, P. Tseng: An unconstrained smooth minimization reformulation of the second-order cone complementarity problem. Math. Program., Ser B 104 (2005), 293–327. · Zbl 1093.90063
[5] F.H. Clarke: Optimization and Nonsmooth Analysis. Wiley & Sons, New York, 1983, Reprinted by SIAM, Philadelphia, 1990.
[6] R. Debnath, M. Muramatsu, H. Takahashi: An efficient support vector machine learning method with second-order cone programming for large-scale problems. Appl. Intel. 23 (2005), 219–239. · Zbl 1080.68618
[7] J. Faraut, A. Korányi: Analysis on Symmetric Cones. Clarendon Press, Oxford, 1994.
[8] L. Faybusovich: Euclidean Jordan algebras and interior-point algorithms. Positivity 1 (1997), 331–357. · Zbl 0973.90095
[9] M. Fukushima, Z.-Q. Luo, P. Tseng: Smoothing functions for second-order-cone complementarity problems. SIAM J. Optim. 12 (2002), 436–460. · Zbl 0995.90094
[10] S. Hayashi, N. Yamashita, M. Fukushima: A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J. Optim. 15 (2005), 593–615. · Zbl 1114.90139
[11] H. Jiang: Smoothed Fischer-Burmeister equation methods for the complementarity problem. Technical Report. Department of Mathematics, The University of Melbourne, Parille, Victoria, Australia, June 1997.
[12] Y.-J. Kuo, H.D. Mittelmann: Interior point methods for second-order cone programming and OR applications. Comput. Optim. Appl. 28 (2004), 255–285. · Zbl 1084.90046
[13] M. S. Lobo, L. Vandenberghe, S. Boyd, H. Lebret: Applications of second-order cone programming. Linear Algebra Appl. 284 (1998), 193–228. · Zbl 0946.90050
[14] R.D.C. Monteiro, T. Tsuchiya: Polynomial convergence of primal-dual algorithms for the second order program based the MZ-family of directions. Math. Program. 88 (2000), 61–83. · Zbl 0967.65077
[15] C. Ma, X. Chen: The convergence of a one-step smoothing Newton method for P0-NCP based on a new smoothing NCP-function. J. Comput. Appl. Math. 216 (2008), 1–13. · Zbl 1140.65046
[16] R. Mifflin: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15 (1977), 959–972. · Zbl 0376.90081
[17] Y.E. Nesterov, M. J. Todd: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8 (1998), 324–364. · Zbl 0922.90110
[18] X. Peng, I. King: Robust BMPM training based on second-order cone programming and its application in medical diagnosis. Neural Networks 21 (2008), 450–457. · Zbl 06126288
[19] J. Peng, C. Roos, T. Terlaky: A new class of polynomial primal-dual interior-point methods for second-order cone optimization based on self-regular proximities. SIAM J. Optim. 13 (2002), 179–203. · Zbl 1041.90072
[20] L. Qi, D. Sun: Improving the convergence of non-interior point algorithms for nonlinear complementarity problems. Math. Comput. 69 (2000), 283–304. · Zbl 0947.90117
[21] L. Qi, D. Sun, G. Zhou: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Math. Program. 87 (2000), 1–35. · Zbl 0989.90124
[22] L. Qi, J. Sun: A nonsmooth version of Newton’s method. Math. Program. 58 (1993), 353–367. · Zbl 0780.90090
[23] P.K. Shivaswamy, C. Bhattacharyya, A. J. Smola: Second order cone programming approaches for handling missing and uncertain data. J. Mach. Learn. Res. 7 (2006), 1283–1314. · Zbl 1222.68305
[24] S. Hayashi, N. Yamashita, M. Fukushima: A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J. Optim. 15 (2005), 593–615. · Zbl 1114.90139
[25] T. Sasakawa, T. Tsuchiya: Optimal magnetic shield design with second-order cone programming. SIAM J. Sci. Comput. 24 (2003), 1930–1950. · Zbl 1163.90796
[26] D. Sun, J. Sun: Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions. Math. Program., Ser A. 103 (2005), 575–581. · Zbl 1099.90062
[27] K.C. Toh, R.H. Tütüncü, M. J. Todd: SDPT3 Version 3.02-A MATLAB software for semidefinite-quadratic-linear programming. http://www.math.nus.edu.sg/\(\sim\)mattohkc/sdpt3.html .
[28] P. Tseng: Error bounds and superlinear convergence analysis of some Newton-type methods in optimization. Nonlinear Optimization and Related Topics (G. Di Pillo, F. Giannessi, eds.). Kluwer Academic Publishers, Dordrecht; Appl. Optim. 36 (2000), 445–462. · Zbl 0965.65091
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.