Abstract
In this paper, we present a new one-step smoothing Newton method for solving the second-order cone programming (SOCP). Based on a new smoothing function of the well-known Fischer-Burmeister function, the SOCP is approximated by a family of parameterized smooth equations. Our algorithm solves only one system of linear equations and performs only one Armijo-type line search at each iteration. It can start from an arbitrary initial point and does not require the iterative points to be in the sets of strictly feasible solutions. Without requiring strict complementarity at the SOCP solution, the proposed algorithm is shown to be globally and locally quadratically convergent under suitable assumptions. Numerical experiments demonstrate the feasibility and efficiency of our algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
F. Alizadeh, D. Goldfarb: Second-order cone programming. Math. Program. 95 (2003), 3–51.
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.
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.
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.
F.H. Clarke: Optimization and Nonsmooth Analysis. Wiley & Sons, New York, 1983, Reprinted by SIAM, Philadelphia, 1990.
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.
J. Faraut, A. Korányi: Analysis on Symmetric Cones. Clarendon Press, Oxford, 1994.
L. Faybusovich: Euclidean Jordan algebras and interior-point algorithms. Positivity 1 (1997), 331–357.
M. Fukushima, Z.-Q. Luo, P. Tseng: Smoothing functions for second-order-cone complementarity problems. SIAM J. Optim. 12 (2002), 436–460.
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.
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.
Y.-J. Kuo, H.D. Mittelmann: Interior point methods for second-order cone programming and OR applications. Comput. Optim. Appl. 28 (2004), 255–285.
M. S. Lobo, L. Vandenberghe, S. Boyd, H. Lebret: Applications of second-order cone programming. Linear Algebra Appl. 284 (1998), 193–228.
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.
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.
R. Mifflin: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15 (1977), 959–972.
Y.E. Nesterov, M. J. Todd: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8 (1998), 324–364.
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.
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.
L. Qi, D. Sun: Improving the convergence of non-interior point algorithms for nonlinear complementarity problems. Math. Comput. 69 (2000), 283–304.
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.
L. Qi, J. Sun: A nonsmooth version of Newton’s method. Math. Program. 58 (1993), 353–367.
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.
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.
T. Sasakawa, T. Tsuchiya: Optimal magnetic shield design with second-order cone programming. SIAM J. Sci. Comput. 24 (2003), 1930–1950.
D. Sun, J. Sun: Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions. Math. Program., Ser A. 103 (2005), 575–581.
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/~mattohkc/sdpt3.html.
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.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by National Natural Science Foundation of China (10971122), Natural Science Foundation of Shandong Province (Y2008A01), Specialized Research Foundation for the Doctoral Program of Higher Education (20093718110005) and Project of Shandong Province Higher Educational Science and Technology Program (J10LA51).
Rights and permissions
About this article
Cite this article
Tang, J., He, G., Dong, L. et al. A new one-step smoothing Newton method for second-order cone programming. Appl Math 57, 311–331 (2012). https://doi.org/10.1007/s10492-012-0019-6
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10492-012-0019-6