| Title:
|
A smoothing Newton method for the second-order cone complementarity problem (English) |
| Author:
|
Tang, Jingyong |
| Author:
|
He, Guoping |
| Author:
|
Dong, Li |
| Author:
|
Fang, Liang |
| Author:
|
Zhou, Jinchuan |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
58 |
| Issue:
|
2 |
| Year:
|
2013 |
| Pages:
|
223-247 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
In this paper we introduce a new smoothing function and show that it is coercive under suitable assumptions. Based on this new function, we propose a smoothing Newton method for solving the second-order cone complementarity problem (SOCCP). The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. It is shown that any accumulation point of the iteration sequence generated by the proposed algorithm is a solution to the SOCCP. Furthermore, we prove that the generated sequence is bounded if the solution set of the SOCCP is nonempty and bounded. Under the assumption of nonsingularity, we establish the local quadratic convergence of the algorithm without the strict complementarity condition. Numerical results indicate that the proposed algorithm is promising. (English) |
| Keyword:
|
second-order cone complementarity problem |
| Keyword:
|
smoothing function |
| Keyword:
|
smoothing Newton method |
| Keyword:
|
global convergence |
| Keyword:
|
quadratic convergence |
| MSC:
|
90C25 |
| MSC:
|
90C30 |
| MSC:
|
90C33 |
| MSC:
|
90C53 |
| idZBL:
|
Zbl 1274.90268 |
| idMR:
|
MR3034823 |
| DOI:
|
10.1007/s10492-013-0011-9 |
| . |
| Date available:
|
2013-03-01T15:57:22Z |
| Last updated:
|
2020-07-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143164 |
| . |
| Reference:
|
[1] Burke, J., Xu, S.: A non-interior predictor-corrector path-following algorithm for LCP.Reformulation: Nonsmooth, Piecewise Smooth and Smoothing Methods M. Fukushima, L. Qi Kluwer Academic Publishers Boston (1999), 45-63. MR 1682736 |
| Reference:
|
[2] Burke, J., Xu, S.: A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem.Math. Program. 87 (2000), 113-130. Zbl 1081.90603, MR 1734661, 10.1007/s101079900111 |
| Reference:
|
[3] Chen, B., Chen, X.: A global and local superlinear continuation-smoothing method for $P_0+R_0$ and monotone NCP.SIAM J. Optim. 9 (1999), 624-645. MR 1681055, 10.1137/S1052623497321109 |
| Reference:
|
[4] Chen, B., Chen, X.: A global linear and local quadratic continuation smoothing method for variational inequalities with box constraints.Comput. Optim. Appl. 17 (2000), 131-158. Zbl 0987.90079, MR 1806250, 10.1023/A:1026546230851 |
| Reference:
|
[5] Chen, B., Xiu, N.: A global linear and local quadratic noninterior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions.SIAM J. Optim. 9 (1999), 605-623. Zbl 1037.90052, MR 1681059, 10.1137/S1052623497316191 |
| Reference:
|
[6] Chen, J.: A new merit function and its related properties for the second-order cone complementarity problem.Pac. J. Optim. 2 (2006), 167-179. Zbl 1178.90324, MR 2548216 |
| Reference:
|
[7] Chen, J., Chen, X., Tseng, P.: Analysis of nonsmooth vector-valued functions associated with second-order cones.Math. Program. 101 (2004), 95-117. Zbl 1065.49013, MR 2085260, 10.1007/s10107-004-0538-3 |
| Reference:
|
[8] Chen, J., Tseng, P.: An unconstrained smooth minimization reformulation of the second-order cone complementarity problem.Math. Program. 104 (2005), 293-327. Zbl 1093.90063, MR 2179239, 10.1007/s10107-005-0617-0 |
| Reference:
|
[9] Chen, X. D., Sun, D., Sun, J.: Complementarity functions and numerical experiments on some smoothing Newton methods for second-order-cone complementarity problems.Comput. Optim. Appl. 25 (2003), 39-56. Zbl 1038.90084, MR 1996662, 10.1023/A:1022996819381 |
| Reference:
|
[10] Chi, X. N., Liu, S. Y.: Analysis of a non-interior continuation method for second-order cone programming.J. Appl. Math. Comput. 27 (2008), 47-61. Zbl 1193.90169, MR 2403140, 10.1007/s12190-008-0057-0 |
| Reference:
|
[11] Chi, X. N., Liu, S. Y.: A one-step smoothing Newton method for second-order cone programming.J. Comput. Appl. Math. 223 (2009), 114-123. Zbl 1155.65045, MR 2463105, 10.1016/j.cam.2007.12.023 |
| Reference:
|
[12] Chi, X. N., Liu, S. Y.: A non-interior continuation method for second-order cone programming.Optimization 58 (2009), 965-979. Zbl 1177.90318, MR 2572781, 10.1080/02331930701763421 |
| Reference:
|
[13] Clarke, F. H.: Optimization and Nonsmooth Analysis.John Wiley & Sons New York (1983), reprinted by SIAM, Philadelphia, 1990. Zbl 0582.49001, MR 0709590 |
| Reference:
|
[14] Fang, L.: A new one-step smoothing Newton method for nonlinear complementarity problem with $P_0$-function.Appl. Math. Comput. 216 (2010), 1087-1095. Zbl 1239.65034, MR 2607218, 10.1016/j.amc.2010.02.001 |
| Reference:
|
[15] Fang, L., He, G. P., Hu, Y. H.: A new smoothing Newton-type method for second-order cone programming problems.Appl. Math. Comput. 215 (2009), 1020-1029. Zbl 1183.65065, MR 2568957, 10.1016/j.amc.2009.06.029 |
| Reference:
|
[16] Fukushima, M., Luo, Z., Tseng, P.: Smoothing functions for second-order-cone complementarity problems.SIAM J. Optim. 12 (2002), 436-460. MR 1885570, 10.1137/S1052623400380365 |
| Reference:
|
[17] Hayashi, S., Yamashita, N., Fukushima, M.: A combined smoothing and regularized method for monotone second-order cone complementarity problems.SIAM J. Optimization 15 (2005), 593-615. MR 2144183, 10.1137/S1052623403421516 |
| Reference:
|
[18] Huang, Z. H., Han, J. Y., Xu, D. C., Zhang, L. P.: The non-interior continuation methods for solving the $P_0$ function nonlinear complementarity problem.Sci. China, Ser. A 44 (2001), 1107-1114. Zbl 1002.90072, MR 1860828, 10.1007/BF02877427 |
| Reference:
|
[19] Huang, Z. H., Ni, T.: Smoothing algorithms for complementarity problems over symmetric cones.Comput. Optim. Appl. 45 (2010), 557-579. Zbl 1198.90373, MR 2600896, 10.1007/s10589-008-9180-y |
| Reference:
|
[20] 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:
|
[21] Mifflin, R.: Semismooth and semiconvex functions in constrained optimization.SIAM J. Control. Optim. 15 (1977), 957-972. Zbl 0376.90081, MR 0461556, 10.1137/0315061 |
| Reference:
|
[22] Pan, S. H., Chen, J. S.: A damped Gauss-Newton method for the second-order cone complementarity problem.Appl. Math. Optim. 59 (2009), 293-318. Zbl 1169.49031, MR 2491700, 10.1007/s00245-008-9054-9 |
| Reference:
|
[23] Pan, S. H., Chen, J. S.: A linearly convergent derivative-free descent method for the second-order cone complementarity problem.Optimization 59 (2010), 1173-1197. Zbl 1229.90239, MR 2738600, 10.1080/02331930903085359 |
| Reference:
|
[24] Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations.Math. Oper. Res. 18 (1993), 227-244. Zbl 0776.65037, MR 1250115, 10.1287/moor.18.1.227 |
| Reference:
|
[25] 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:
|
[26] Qi, L., Sun, D.: Improving the convergence of non-interior point algorithm for nonlinear complementarity problems.Math. Comput. 69 (2000), 283-304. MR 1642766, 10.1090/S0025-5718-99-01082-0 |
| Reference:
|
[27] 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:
|
[28] Tang, J. Y., He, G. P., Dong, L., Fang, L.: A smoothing Newton method for second-order cone optimization based on a new smoothing function.Appl. Math. Comput. 218 (2011), 1317-1329. Zbl 1229.65101, MR 2831640, 10.1016/j.amc.2011.06.015 |
| Reference:
|
[29] Toh, K. C., Tütüncü, R. H., Todd, M. J.: SDPT3 Version 3.02-A MATLAB software for semidefinite-quadratic-linear programming, 2000.\hfill http://www.math.nus.edu.sg/ {mattohkc/sdpt3.html}.. |
| Reference:
|
[30] Yoshise, A.: Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones.SIAM J. Optim. 17 (2006), 1129-1153. Zbl 1136.90039, MR 2274506, 10.1137/04061427X |
| Reference:
|
[31] Zhang, L., Han, J., Huang, Z.: Superlinear/quadratic one-step smoothing Newton method for $P_0$-NCP.Acta Math. Sin. 21 (2005), 117-128. Zbl 1124.90037, MR 2128829, 10.1007/s10114-004-0412-5 |
| Reference:
|
[32] Zhang, J., Zhang, K.: A variant smoothing Newton method for $P_0$-NCP based on a new smoothing function.J. Comput. Appl. Math. 225 (2009), 1-8. Zbl 1163.65043, MR 2490165, 10.1016/j.cam.2008.06.012 |
| Reference:
|
[33] Zhou, G., Sun, D., Qi, L.: Numerical experiments for a class of squared smoothing Newton methods for box constrained variational inequality problems.Reformulation-Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods M. Fukushima, L. Qi Kluwer Academic Publishers Boston (1999), 421-441. Zbl 0928.65080, MR 1682739 |
| . |
