Previous |  Up |  Next


Title: A new one-step smoothing newton method for second-order cone programming (English)
Author: Tang, Jingyong
Author: He, Guoping
Author: Dong, Li
Author: Fang, Liang
Language: English
Journal: Applications of Mathematics
ISSN: 0862-7940 (print)
ISSN: 1572-9109 (online)
Volume: 57
Issue: 4
Year: 2012
Pages: 311-331
Summary lang: English
Category: math
Summary: 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. (English)
Keyword: second-order cone programming
Keyword: smoothing Newton method
Keyword: global convergence
Keyword: quadratic convergence
Keyword: Fischer-Burmeister function
Keyword: Euclidean Jordan algebra
Keyword: local quadratic convergence
MSC: 49M15
MSC: 49M37
MSC: 65K05
MSC: 65Y20
MSC: 90C25
MSC: 90C30
MSC: 90C46
MSC: 90C53
idZBL: Zbl 1265.90229
idMR: MR2984606
DOI: 10.1007/s10492-012-0019-6
Date available: 2012-08-19T21:39:23Z
Last updated: 2020-07-02
Stable URL:
Reference: [1] Alizadeh, F., Goldfarb, D.: Second-order cone programming.Math. Program. 95 (2003), 3-51. Zbl 1153.90522, MR 1971381, 10.1007/s10107-002-0339-5
Reference: [2] Bai, Y. Q., Wang, G. Q., Roos, C.: 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, MR 2502767
Reference: [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 J. Optim. 9 (1999), 605-623. MR 1681059, 10.1137/S1052623497316191
Reference: [4] Chen, J. S., Tseng, P.: An unconstrained smooth minimization reformulation of the second-order cone complementarity problem.Math. Program., Ser B 104 (2005), 293-327. Zbl 1093.90063, MR 2179239, 10.1007/s10107-005-0617-0
Reference: [5] Clarke, F. H.: Optimization and Nonsmooth Analysis.Wiley & Sons New York (1983), Reprinted by SIAM, Philadelphia, 1990 \MR 0709590. Zbl 0582.49001, MR 1058436
Reference: [6] Debnath, R., Muramatsu, M., Takahashi, H.: 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, 10.1007/s10489-005-4609-9
Reference: [7] Faraut, J., Korányi, A.: Analysis on Symmetric Cones.Clarendon Press Oxford (1994). MR 1446489
Reference: [8] Faybusovich, L.: Euclidean Jordan algebras and interior-point algorithms.Positivity 1 (1997), 331-357. Zbl 0973.90095, MR 1660399, 10.1023/A:1009701824047
Reference: [9] Fukushima, M., Luo, Z.-Q., Tseng, P.: Smoothing functions for second-order-cone complementarity problems.SIAM J. Optim. 12 (2002), 436-460. MR 1885570, 10.1137/S1052623400380365
Reference: [10] Hayashi, S., Yamashita, N., Fukushima, M.: A combined smoothing and regularization method for monotone second-order cone complementarity problems.SIAM J. Optim. 15 (2005), 593-615. Zbl 1114.90139, MR 2144183, 10.1137/S1052623403421516
Reference: [11] Jiang, H.: Smoothed Fischer-Burmeister equation methods for the complementarity problem.Technical Report Department of Mathematics, The University of Melbourne Parille, Victoria, Australia, June 1997.
Reference: [12] Kuo, Y.-J., Mittelmann, H. D.: Interior point methods for second-order cone programming and OR applications.Comput. Optim. Appl. 28 (2004), 255-285. Zbl 1084.90046, MR 2080003, 10.1023/B:COAP.0000033964.95511.23
Reference: [13] Lobo, M. S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming.Linear Algebra Appl. 284 (1998), 193-228. Zbl 0946.90050, MR 1655138
Reference: [14] Monteiro, R. D. C., Tsuchiya, T.: Polynomial convergence of primal-dual algorithms for the second order program based the MZ-family of directions.Math. Program. 88 (2000), 61-83. MR 1765893, 10.1007/PL00011378
Reference: [15] Ma, C., Chen, X.: The convergence of a one-step smoothing Newton method for $P_0$-NCP based on a new smoothing NCP-function.J. Comput. Appl. Math. 216 (2008), 1-13. Zbl 1140.65046, MR 2421836, 10.1016/
Reference: [16] Mifflin, R.: Semismooth and semiconvex functions in constrained optimization.SIAM J. Control Optim. 15 (1977), 959-972. Zbl 0376.90081, MR 0461556, 10.1137/0315061
Reference: [17] Nesterov, Y. E., Todd, M. J.: Primal-dual interior-point methods for self-scaled cones.SIAM J. Optim. 8 (1998), 324-364. Zbl 0922.90110, MR 1618802, 10.1137/S1052623495290209
Reference: [18] Peng, X., King, I.: Robust BMPM training based on second-order cone programming and its application in medical diagnosis.Neural Networks 21 (2008), 450-457. 10.1016/j.neunet.2007.12.051
Reference: [19] 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 J. Optim. 13 (2002), 179-203. MR 1922760, 10.1137/S1052623401383236
Reference: [20] Qi, L., Sun, D.: Improving the convergence of non-interior point algorithms for nonlinear complementarity problems.Math. Comput. 69 (2000), 283-304. Zbl 0947.90117, MR 1642766, 10.1090/S0025-5718-99-01082-0
Reference: [21] Qi, L., Sun, D., Zhou, G.: 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, MR 1734657, 10.1007/s101079900127
Reference: [22] Qi, L., Sun, J.: A nonsmooth version of Newton's method.Math. Program. 58 (1993), 353-367. Zbl 0780.90090, MR 1216791, 10.1007/BF01581275
Reference: [23] Shivaswamy, P. K., Bhattacharyya, C., Smola, A. J.: Second order cone programming approaches for handling missing and uncertain data.J. Mach. Learn. Res. 7 (2006), 1283-1314. Zbl 1222.68305, MR 2274406
Reference: [24] Hayashi, S., Yamashita, N., Fukushima, M.: A combined smoothing and regularization method for monotone second-order cone complementarity problems.SIAM J. Optim. 15 (2005), 593-615. Zbl 1114.90139, MR 2144183, 10.1137/S1052623403421516
Reference: [25] Sasakawa, T., Tsuchiya, T.: Optimal magnetic shield design with second-order cone programming.SIAM J. Sci. Comput. 24 (2003), 1930-1950. Zbl 1163.90796, MR 2005615, 10.1137/S1064827500380350
Reference: [26] Sun, D., Sun, J.: Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions.Math. Program., Ser A. 103 (2005), 575-581. Zbl 1099.90062, MR 2166550, 10.1007/s10107-005-0577-4
Reference: [27] Toh, K. C., Tütüncü, R. H., Todd, M. J.: SDPT3 Version 3.02---A MATLAB software for semidefinite-quadratic-linear programming.(2002), {mattohkc\allowbreak/sdpt3.html}.
Reference: [28] Tseng, P.: Error bounds and superlinear convergence analysis of some Newton-type methods in optimization.Nonlinear Optimization and Related Topics G. Di Pillo, F. Giannessi Kluwer Academic Publishers Dordrecht Appl. Optim. 36 (2000), 445-462. Zbl 0965.65091, MR 1777934, 10.1007/978-1-4757-3226-9_24


Files Size Format View
AplMat_57-2012-4_1.pdf 325.5Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo