| 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:
|
http://hdl.handle.net/10338.dmlcz/142901 |
| . |
| 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/j.cam.2007.03.031 |
| 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), http://www.math.nus.edu.sg/ {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 |
| . |
