Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
second-order cone complementarity problem; smoothing function; smoothing Newton method; global convergence; quadratic convergence
second-order cone complementarity problem; smoothing function; smoothing Newton method; global convergence; quadratic convergence
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.
References:
[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
[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. DOI 10.1007/s101079900111 | MR 1734661 | Zbl 1081.90603
[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. DOI 10.1137/S1052623497321109 | MR 1681055
[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. DOI 10.1023/A:1026546230851 | MR 1806250 | Zbl 0987.90079
[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. DOI 10.1137/S1052623497316191 | MR 1681059 | Zbl 1037.90052
[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. MR 2548216 | Zbl 1178.90324
[7] Chen, J., Chen, X., Tseng, P.: Analysis of nonsmooth vector-valued functions associated with second-order cones. Math. Program. 101 (2004), 95-117. DOI 10.1007/s10107-004-0538-3 | MR 2085260 | Zbl 1065.49013
[8] Chen, J., Tseng, P.: An unconstrained smooth minimization reformulation of the second-order cone complementarity problem. Math. Program. 104 (2005), 293-327. DOI 10.1007/s10107-005-0617-0 | MR 2179239 | Zbl 1093.90063
[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. DOI 10.1023/A:1022996819381 | MR 1996662 | Zbl 1038.90084
[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. DOI 10.1007/s12190-008-0057-0 | MR 2403140 | Zbl 1193.90169
[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. DOI 10.1016/j.cam.2007.12.023 | MR 2463105 | Zbl 1155.65045
[12] Chi, X. N., Liu, S. Y.: A non-interior continuation method for second-order cone programming. Optimization 58 (2009), 965-979. DOI 10.1080/02331930701763421 | MR 2572781 | Zbl 1177.90318
[13] Clarke, F. H.: Optimization and Nonsmooth Analysis. John Wiley & Sons New York (1983), reprinted by SIAM, Philadelphia, 1990. MR 0709590 | Zbl 0582.49001
[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. DOI 10.1016/j.amc.2010.02.001 | MR 2607218 | Zbl 1239.65034
[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. DOI 10.1016/j.amc.2009.06.029 | MR 2568957 | Zbl 1183.65065
[16] Fukushima, M., Luo, Z., Tseng, P.: Smoothing functions for second-order-cone complementarity problems. SIAM J. Optim. 12 (2002), 436-460. DOI 10.1137/S1052623400380365 | MR 1885570
[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. DOI 10.1137/S1052623403421516 | MR 2144183
[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. DOI 10.1007/BF02877427 | MR 1860828 | Zbl 1002.90072
[19] Huang, Z. H., Ni, T.: Smoothing algorithms for complementarity problems over symmetric cones. Comput. Optim. Appl. 45 (2010), 557-579. DOI 10.1007/s10589-008-9180-y | MR 2600896 | Zbl 1198.90373
[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. DOI 10.1016/j.cam.2007.03.031 | MR 2421836 | Zbl 1140.65046
[21] Mifflin, R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control. Optim. 15 (1977), 957-972. DOI 10.1137/0315061 | MR 0461556 | Zbl 0376.90081
[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. DOI 10.1007/s00245-008-9054-9 | MR 2491700 | Zbl 1169.49031
[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. DOI 10.1080/02331930903085359 | MR 2738600 | Zbl 1229.90239
[24] Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18 (1993), 227-244. DOI 10.1287/moor.18.1.227 | MR 1250115 | Zbl 0776.65037
[25] 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
[26] Qi, L., Sun, D.: Improving the convergence of non-interior point algorithm for nonlinear complementarity problems. Math. Comput. 69 (2000), 283-304. DOI 10.1090/S0025-5718-99-01082-0 | MR 1642766
[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. DOI 10.1007/s101079900127 | MR 1734657 | Zbl 0989.90124
[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. DOI 10.1016/j.amc.2011.06.015 | MR 2831640 | Zbl 1229.65101
[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}.
[30] Yoshise, A.: Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones. SIAM J. Optim. 17 (2006), 1129-1153. DOI 10.1137/04061427X | MR 2274506 | Zbl 1136.90039
[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. DOI 10.1007/s10114-004-0412-5 | MR 2128829 | Zbl 1124.90037
[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. DOI 10.1016/j.cam.2008.06.012 | MR 2490165 | Zbl 1163.65043
[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. MR 1682739 | Zbl 0928.65080
Search
Partner of
