×

zbMATH — the first resource for mathematics

A damped Gauss-Newton method for the second-order cone complementarity problem. (English) Zbl 1169.49031
Summary: We investigate some properties related to the generalized Newton method for the Fischer-Burmeister (FB) function over second-order cones, which allows us to reformulate the second-order cone complementarity problem as a semismooth system of equations. Specifically, we characterize the \(B\)-subdifferential of the FB function at a general point and study the condition for every element of the \(B\)-subdifferential at a solution being nonsingular. In addition, for the induced FB merit function, we establish its coerciveness and provide a weaker condition than J.-S. Chen and P. Tseng [Math. Program. 104, No. 2–3 (B), 293–327 (2005; Zbl 1093.90063)] for each stationary point to be a solution, under suitable Cartesian \(P\)-properties of the involved mapping. By this, a damped Gauss-Newton method is proposed, and global and superlinear convergence results are obtained. Numerical results are reported for the second-order cone programs from the DIMACS library, which verify the good theoretical properties of the method.

MSC:
49M15 Newton-type methods
49J52 Nonsmooth analysis
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Citations:
Zbl 1093.90063
Software:
SeDuMi
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95, 3–51 (2003) · Zbl 1153.90522
[2] Andersen, E.D., Roos, C., Terlaky, T.: On implementing a primal-dual interior-point method for conic quadratic optimization. Math. Program. 95, 249–277 (2003) · Zbl 1030.90137
[3] Chen, J.-S., Chen, X., Tseng, P.: Analysis of nonsmooth vector-valued functions associated with second-order cones. Math. Program. 101, 95–117 (2004) · Zbl 1065.49013
[4] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983). Reprinted by SIAM, Philadelphia (1990) · Zbl 0582.49001
[5] Chen, X., Qi, H.: Cartesian P-property and its applications to the semidefinite linear complementarity problem. Math. Program. 106, 177–201 (2006) · Zbl 1134.90508
[6] Chen, J.-S., Tseng, P.: An unconstrained smooth minimization reformulation of the second-order cone complementarity problem. Math. Program. 104, 293–327 (2005) · Zbl 1093.90063
[7] Chen, X.-D., Sun, D., Sun, J.: Complementarity functions and numerical experiments for second-order cone complementarity problems. Comput. Optim. Appl. 25, 39–56 (2003) · Zbl 1038.90084
[8] Fischer, A.: Solution of the monotone complementarity problem with locally Lipschitzian functions. Math. Program. 76, 513–532 (1997) · Zbl 0871.90097
[9] Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Oxford Mathematical Monographs, Oxford University Press, New York (1994) · Zbl 0841.43002
[10] Facchinei, F., Kanzow, C.: A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems. Math. Program. 76, 493–512 (1997) · Zbl 0871.90096
[11] Fukushima, M., Luo, Z.-Q., Tseng, P.: Smoothing functions for second-order cone complementarity problems. SIAM J. Optim. 12, 436–460 (2002) · Zbl 0995.90094
[12] Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problem and a related algorithm. SIAM J. Optim. 7, 225–247 (1997) · Zbl 0873.90096
[13] Hayashi, S., Yamashita, N., Fukushima, M.: A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J. Optim. 15, 593–615 (2005) · Zbl 1114.90139
[14] Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Application of second-order cone programming. Linear Algebra Appl. 284, 193–228 (1998) · Zbl 0946.90050
[15] Mifflin, M.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15, 957–972 (1977) · Zbl 0376.90081
[16] Monteiro, R.D.C., Tsuchiya, T.: Polynomial convergence of primal-dual algorithms for the second-order cone programs based on the MZ-family of directions. Math. Program. 88, 61–83 (2000) · Zbl 0967.65077
[17] Pan, S.-H., Chen, J.-S.: A regularization method for the second-order cone complementarity problems with Cartesian P 0-property, Nonlinear Analysis (to appear)
[18] Pataki, G., Schmieta, S.: The DIMACS library of semidefinite-quadratic-linear programs. Preliminary draft, Computational Optimization Research Center, Columbia University, New York. http://dimacs.rutgers.edu/Challenges/Seventh/Instances/
[19] Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–244 (1993) · Zbl 0776.65037
[20] Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993) · Zbl 0780.90090
[21] Sun, D., Sun, J.: Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions. Math. Program. 103, 575–581 (2005) · Zbl 1099.90062
[22] Sun, D., Womersley, R.S.: A new unconstrained differential merit function for box constrained variational inequality problems and a damped Gauss-Newton method. SIAM J. Optim. 9, 388–413 (1999) · Zbl 0960.90086
[23] Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Software 11&12, 625–653 (1999) · Zbl 0973.90526
[24] Tsuchiya, T.: A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming. Optim. Methods Softw. 11, 141–182 (1999) · Zbl 0957.90129
[25] Zhang, H.-C., Hager, W.W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14, 1043–1056 (2004) · Zbl 1073.90024
[26] 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
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.