×

zbMATH — the first resource for mathematics

A smoothing Newton method for second-order cone optimization based on a new smoothing function. (English) Zbl 1229.65101
Summary: A new smoothing function is given by smoothing the symmetric perturbed Fischer-Burmeister function. Based on this new smoothing function, we present a smoothing Newton method for solving the second-order cone optimization (SOCO). The method solves only one linear system of equations and performs only one line search at each iteration. Without requiring strict complementarity assumption at the SOCO solution, the proposed algorithm is shown to be globally and locally quadratically convergent. Numerical results demonstrate that our algorithm is promising and comparable to interior-point methods.

MSC:
65K05 Numerical mathematical programming methods
90C25 Convex programming
90C53 Methods of quasi-Newton type
90C51 Interior-point methods
Software:
SDPT3
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alizadeh, F.; Goldfarb, D., Second-order cone programming, Mathematical programming, 95, 3-51, (2003) · Zbl 1153.90522
[2] Bai, Y.Q.; Wang, G.Q.; Roos, C., Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions, Nonlinear analysis, 70, 3584-3602, (2009) · Zbl 1190.90275
[3] 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, 9, 605-623, (1999) · Zbl 1037.90052
[4] Chen, J.; Tseng, P., An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Mathematical programming series B, 104, 293-327, (2005) · Zbl 1093.90063
[5] F.H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983. Reprinted by SIAM, Philadelphia, 1990. · Zbl 0582.49001
[6] Chi, X.N.; Liu, S.Y., A one-step smoothing Newton method for second-order cone programming, Journal of computational and applied mathematics, 223, 114-123, (2009) · Zbl 1155.65045
[7] Chi, X.N.; Liu, S.Y., A non-interior continuation method for second-order cone programming, Optimization, 58, 965-979, (2009) · Zbl 1177.90318
[8] Debnath, R.; Muramatsu, M.; Takahashi, H., An efficient support vector machine learning method with second-order cone programming for large-scale problems, Applied intelligence, 23, 219-239, (2005) · Zbl 1080.68618
[9] Fang, L.; He, G.P.; Hu, Y.H., A new smoothing Newton-type method for second-order cone programming problems, Applied mathematics and computation, 215, 1020-1029, (2009) · Zbl 1183.65065
[10] Faraut, J.; Koranyi, A., Analysis on symmetric cones, (1994), Oxford University Press London, New York · Zbl 0841.43002
[11] Faybusovich, L., Euclidean Jordan algebras and interior-point algorithms, Positivity, 1, 331-357, (1997) · Zbl 0973.90095
[12] Fukushima, M.; Luo, Z.; Tseng, P., Smoothing functions for second-order-cone complementarity problems, SIAM journal on optimization, 12, 2, 436-460, (2002) · Zbl 0995.90094
[13] Hayashi, S.; Yamashita, N.; Fukushima, M., A combined smoothing and regularized method for monotone second-order cone complementarity problems, SIAM journal on optimization, 15, 593-615, (2005) · Zbl 1114.90139
[14] 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.
[15] Kuo, Y.J.; Mittelmann, H.D., Interior point methods for second-order cone programming and OR applications, Computational optimization and applications, 28, 255-285, (2004) · Zbl 1084.90046
[16] Lobo, M.S.; Vandenberghe, L.; Boyd, S.; Lebret, H., Applications of second-order cone programming, Linear algebra and its applications, 284, 193-228, (1998) · Zbl 0946.90050
[17] Liu, Y.; Zhang, L.; Wang, Y., Analysis of a smoothing method for symmetric cone linear programming, Journal of applied mathematics and computing, 22, 133-148, (2006) · Zbl 1132.90353
[18] Ma, C.; Chen, X., The convergence of a one-step smoothing Newton method for P_{0}-NCP based on a new smoothing NCP-function, Journal of computational and applied mathematics, 216, 1-13, (2008) · Zbl 1140.65046
[19] Miffin, R., Semismooth and semiconvex functions in constrained optimization, SIAM journal on control and optimization, 15, 957-972, (1977)
[20] Nesterov, Y.E.; Todd, M.J., Primal-dual interior-point methods for self-scaled cones, SIAM journal on optimization, 8, 2, 324-364, (1998) · Zbl 0922.90110
[21] Peng, X.; King, I., Robust BMPM training based on second-order cone programming and its application in medical diagnosis, Neural networks, 21, 450-457, (2008)
[22] Peng, J.; Roos, C.; Terlaky, T., Primal-dual interior-point methods for second-order conic optimization based on self-regular proximities, SIAM journal on optimization, 13, 1, 179-203, (2002) · Zbl 1041.90072
[23] S. Pan, J. Chen, A semismooth Newton method for SOCCPs based on a one-parametric class of SOC complementarity functions, Computational Optimization and Applications. doi:10.1007/s10589-008-9166-9. · Zbl 1208.90170
[24] Qi, L.; Sun, D., Improving the convergence of non-interior point algorithm for nonlinear complementarity problems, Mathematics of computation, 69, 283-304, (2000) · Zbl 0947.90117
[25] Qi, L.; Sun, D.; Zhou, G., A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Mathematical programming, 87, 1-35, (2000) · Zbl 0989.90124
[26] Qi, L.; Sun, J., A nonsmooth version of newton’s method, Mathematical programming, 58, 353-367, (1993) · Zbl 0780.90090
[27] Qi, L., Convergence analysis of some algorithms for solving nonsmooth equations, Mathematics of operational research, 18, 227-244, (1993) · Zbl 0776.65037
[28] Shivaswamy, P.K.; Bhattacharyya, C.; Smola, A.J., Second order cone programming approaches for handling missing and uncertain data, Journal of machine learning research, 7, 1283-1314, (2006) · Zbl 1222.68305
[29] Schmieta, S.H.; Alizadeh, F., Extension of primal-dual interior-point algorithms to symmetric cones, Mathematical programming series A, 96, 409-438, (2003) · Zbl 1023.90083
[30] Sasakawa, T.; Tsuchiya, T., Optimal magnetic shield design with second-order cone programming, SIAM journal of science and computation, 24, 6, 1930-1950, (2003) · Zbl 1163.90796
[31] Sun, D.; Sun, J., Strong semismoothness of the fischer – burmeister SDC and SOC complementarity functions, Mathematical programming series A, 103, 575-581, (2005) · Zbl 1099.90062
[32] K.C. Toh, R.H. Tütüncü, M.J. Todd, SDPT3 Version 3.02-A MATLAB software for semidefinite-quadratic-linear programming, 2002. <http://www.math.nus.edu.sg/mattohkc/sdpt3.html>.
[33] Tseng, P., Error bounds and superlinear convergence analysis of some Newton-type methods in optimization, (), 445-462 · Zbl 0965.65091
[34] Wang, G.Q.; Bai, Y.Q.; Roos, C., A primal-dual interior-point algorithm for second-order cone optimization with full nesterov – todd step, Applied mathematics and computation, 215, 1047-1061, (2009) · Zbl 1183.65073
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.