×

zbMATH — the first resource for mathematics

A smoothing Newton method for the second-order cone complementarity problem. (English) Zbl 1274.90268
The paper introduces a new variant of smoothing Newton method for the second-order cone complementarity problem based on a new type of smoothing of Fischer-Burmeister NCP function. The authors propose to use a smoothing function \[ \varphi (\mu, x, y) = (\cos \mu + \sin \mu )(x + y) - \sqrt{(\cos \mu - \sin \mu )^2 (x-y)^2 + 4\mu ^2 e}, \] where \(e\) is the identity element with respect to Jordan product. Basic results of Euclidean Jordan algebra are summarized and the Jacobian of \(\varphi \) is computed.
The proposed variant of the Newton method is accompanied with analysis of global convergence, and the authors establish the local quadratic convergence of the algorithm without the strict complementarity condition. The paper is concluded with reports on the numerical performance of the proposed method in comparison with the interior point method.
Currently, the smoothing Newton methods for second-order cone complementarity problems attract a lot of attention and there is already a considerable number of papers with similar algorithms based on another smoothings of Fisher-Burmeister NCP function, cf. eg. [X. D. Chen, D. Sun and J. Sun, Comput. Optim. Appl. 25, No. 1–3, 39–56 (2003; Zbl 1038.90084)] or [Y. Narushima, N. Sagara and H. Ogasawara, J. Optim. Theory Appl. 149, No. 1, 79–101 (2011; Zbl 1221.90085)].

MSC:
90C25 Convex programming
90C30 Nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Software:
SDPT3
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] Burke, J.; Xu, S.; Fukushima, M. (ed.); Qi, L. (ed.), A non-interior predictor-corrector path-following algorithm for LCP, 45-63, (1999), Boston · Zbl 0927.65081
[2] Burke, J.; Xu, S., A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem, Math. Program., 87, 113-130, (2000) · 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, 624-645, (1999) · Zbl 0955.90132
[4] Chen, B.; Chen, X., A global linear and local quadratic continuation smoothing method for variational inequalities with box constraints, Comput. Optim. Appl., 17, 131-158, (2000) · 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, 605-623, (1999) · 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, 167-179, (2006) · Zbl 1178.90324
[7] Chen, J.; Chen, X.; Tseng, P., Analysis of nonsmooth vector-valued functions associated with second-order cones, Math. Program., 101, 95-117, (2004) · Zbl 1065.49013
[8] Chen, J.; Tseng, P., An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Program., 104, 293-327, (2005) · 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, 39-56, (2003) · 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, 47-61, (2008) · 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, 114-123, (2009) · Zbl 1155.65045
[12] Chi, X. N.; Liu, S. Y., A non-interior continuation method for second-order cone programming, Optimization, 58, 965-979, (2009) · Zbl 1177.90318
[13] F. H. Clarke: Optimization and Nonsmooth Analysis. John Wiley & Sons, New York, 1983, reprinted by SIAM, Philadelphia, 1990. · 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, 1087-1095, (2010) · 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, 1020-1029, (2009) · Zbl 1183.65065
[16] Fukushima, M.; Luo, Z.; Tseng, P., Smoothing functions for second-order-cone complementarity problems, SIAM J. Optim., 12, 436-460, (2002) · Zbl 0995.90094
[17] Hayashi, S.; Yamashita, N.; Fukushima, M., A combined smoothing and regularized method for monotone second-order cone complementarity problems, SIAM J. Optimization, 15, 593-615, (2005) · Zbl 1114.90139
[18] Huang, Z. H.; Han, J. Y.; Xu, D. C.; Zhang, L. P., The non-interior continuation methods for solving the P0 function nonlinear complementarity problem, Sci. China, Ser. A, 44, 1107-1114, (2001) · Zbl 1002.90072
[19] Huang, Z. H.; Ni, T., Smoothing algorithms for complementarity problems over symmetric cones, Comput. Optim. Appl., 45, 557-579, (2010) · Zbl 1198.90373
[20] Ma, C.; Chen, X., The convergence of a one-step smoothing Newton method for P0-NCP based on a new smoothing NCP-function, J. Comput. Appl. Math., 216, 1-13, (2008) · Zbl 1140.65046
[21] Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SIAM J. Control. Optim., 15, 957-972, (1977) · 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, 293-318, (2009) · 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, 1173-1197, (2010) · Zbl 1229.90239
[24] Qi, L., Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res., 18, 227-244, (1993) · Zbl 0776.65037
[25] Qi, L.; Sun, J., A nonsmooth version of newton’s method, Math. Program., 58, 353-367, (1993) · Zbl 0780.90090
[26] Qi, L.; Sun, D., Improving the convergence of non-interior point algorithm for nonlinear complementarity problems, Math. Comput., 69, 283-304, (2000) · Zbl 0947.90117
[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, 1-35, (2000) · 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, 1317-1329, (2011) · Zbl 1229.65101
[29] K. C. Toh, R. H. Tütüncü, M. J. Todd: SDPT3 Version 3. 02-A MATLAB software for semidefinite-quadratic-linear programming, 2000. 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, 1129-1153, (2006) · 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, 117-128, (2005) · 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, 1-8, (2009) · Zbl 1163.65043
[33] G. Zhou, D. Sun, L. Qi: 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, eds.). Kluwer Academic Publishers, Boston, 1999, pp. 421-441. · Zbl 0928.65080
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.