Article
MSC:
49M15,
49M37,
65K05,
65Y20,
90C25,
90C30,
90C46,
90C53 | MR 2984606 | Zbl 1265.90229 | DOI: 10.1007/s10492-012-0019-6
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
second-order cone programming; smoothing Newton method; global convergence; quadratic convergence; Fischer-Burmeister function; Euclidean Jordan algebra; local quadratic convergence
second-order cone programming; smoothing Newton method; global convergence; quadratic convergence; Fischer-Burmeister function; Euclidean Jordan algebra; local quadratic convergence
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.
References:
[1] Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95 (2003), 3-51. DOI 10.1007/s10107-002-0339-5 | MR 1971381 | 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 Anal., Theory Methods Appl. 70 (2009), 3584-3602. MR 2502767 | 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 J. Optim. 9 (1999), 605-623. DOI 10.1137/S1052623497316191 | MR 1681059
[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. DOI 10.1007/s10107-005-0617-0 | MR 2179239 | Zbl 1093.90063
[5] Clarke, F. H.: Optimization and Nonsmooth Analysis. Wiley & Sons New York (1983), Reprinted by SIAM, Philadelphia, 1990 \MR 0709590. MR 1058436 | Zbl 0582.49001
[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. DOI 10.1007/s10489-005-4609-9 | Zbl 1080.68618
[7] Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Clarendon Press Oxford (1994). MR 1446489
[8] Faybusovich, L.: Euclidean Jordan algebras and interior-point algorithms. Positivity 1 (1997), 331-357. DOI 10.1023/A:1009701824047 | MR 1660399 | Zbl 0973.90095
[9] Fukushima, M., Luo, Z.-Q., Tseng, P.: Smoothing functions for second-order-cone complementarity problems. SIAM J. Optim. 12 (2002), 436-460. DOI 10.1137/S1052623400380365 | MR 1885570
[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. DOI 10.1137/S1052623403421516 | MR 2144183 | Zbl 1114.90139
[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.
[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. DOI 10.1023/B:COAP.0000033964.95511.23 | MR 2080003 | Zbl 1084.90046
[13] Lobo, M. S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284 (1998), 193-228. MR 1655138 | Zbl 0946.90050
[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. DOI 10.1007/PL00011378 | MR 1765893
[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. DOI 10.1016/j.cam.2007.03.031 | MR 2421836 | Zbl 1140.65046
[16] Mifflin, R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15 (1977), 959-972. DOI 10.1137/0315061 | MR 0461556 | Zbl 0376.90081
[17] Nesterov, Y. E., Todd, M. J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8 (1998), 324-364. DOI 10.1137/S1052623495290209 | MR 1618802 | Zbl 0922.90110
[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. DOI 10.1016/j.neunet.2007.12.051
[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. DOI 10.1137/S1052623401383236 | MR 1922760
[20] Qi, L., Sun, D.: Improving the convergence of non-interior point algorithms for nonlinear complementarity problems. Math. Comput. 69 (2000), 283-304. DOI 10.1090/S0025-5718-99-01082-0 | MR 1642766 | Zbl 0947.90117
[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. DOI 10.1007/s101079900127 | MR 1734657 | Zbl 0989.90124
[22] Qi, L., Sun, J.: A nonsmooth version of Newton's method. Math. Program. 58 (1993), 353-367. DOI 10.1007/BF01581275 | MR 1216791 | Zbl 0780.90090
[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. MR 2274406 | Zbl 1222.68305
[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. DOI 10.1137/S1052623403421516 | MR 2144183 | Zbl 1114.90139
[25] Sasakawa, T., Tsuchiya, T.: Optimal magnetic shield design with second-order cone programming. SIAM J. Sci. Comput. 24 (2003), 1930-1950. DOI 10.1137/S1064827500380350 | MR 2005615 | Zbl 1163.90796
[26] Sun, D., Sun, J.: Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions. Math. Program., Ser A. 103 (2005), 575-581. DOI 10.1007/s10107-005-0577-4 | MR 2166550 | Zbl 1099.90062
[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), http://www.math.nus.edu.sg/ {mattohkc\allowbreak/sdpt3.html}.
[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. DOI 10.1007/978-1-4757-3226-9_24 | MR 1777934 | Zbl 0965.65091
Search
Partner of
