×

zbMATH — the first resource for mathematics

The convergence of a one-step smoothing Newton method for \(P_0\)-NCP based on a new smoothing NCP-function. (English) Zbl 1140.65046
Authors’ summary: The nonlinear complementarity problem (denoted by NCP\((F))\) can be reformulated as the solution of a nonsmooth system of equations. By introducing a new smoothing NCP-function, the problem is approximated by a family of parameterized smooth equations. A one-step smoothing Newton method is proposed for solving the nonlinear complementarity problem with \(P_{0}\)-function (\(P_{0}\)-NCP) based on the new smoothing NCP-function. The proposed algorithm solves only one linear system of equations and performs only one line search per iteration. Without requiring strict complementarity assumption at the \(P_{0}\)-NCP solution, the proposed algorithm is proved to be convergent globally and superlinearly under suitable assumptions. Furthermore, the algorithm has local quadratic convergence under mild conditions.

MSC:
65K05 Numerical mathematical programming methods
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chen, B.; Harker, P.T., A non-interior-point continuation method for linear complementarity problems, SIAM J. matrix anal. appl., 14, 2, 1168-1190, (1993) · Zbl 0788.65073
[2] Chen, B.; Harker, P.T., Smoothing approximations to nonlinear complementarity problems, SIAM J. optim., 7, 1, 403-420, (1997) · Zbl 0879.90177
[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, 2, 605-623, (1999) · Zbl 1037.90052
[4] Chen, X.; Qi, L.; Sun, D., Global and superlinear convergence of the smoothing Newton method and its application to general box-constrained variational inequalities, Math. comput., 67, 1, 519-540, (1998) · Zbl 0894.90143
[5] Clarke, F.H., Optimization and nonsmooth analysis, (1983), Wiley New York · Zbl 0727.90045
[6] Facchinei, F.; Kanzow, C., Beyond monotonicity in regularization methods for nonlinear complementarity problems, SIAM J. control optim., 37, 2, 1150-1161, (1999) · Zbl 0997.90085
[7] Ferris, M.C.; Pang, J.-S., Engineering and economic applications of complementarity problems, SIAM rev., 39, 3, 669-713, (1997) · Zbl 0891.90158
[8] Fischer, A., A special Newton-type optimization method, Optimization, 24, 269-284, (1992) · Zbl 0814.65063
[9] Fischer, A., Solution of monotone complementarity problems with locally Lipschitz functions, Math. programming, 76, 2, 513-532, (1997) · Zbl 0871.90097
[10] Geiger, C.; Kanzow, C., On the solution of monotone complementarity problems, Comput. optim. appl., 5, 155-173, (1996) · Zbl 0859.90113
[11] Harker, P.T.; Pang, J.-S., Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Math. programming, 48, 1, 161-220, (1990) · Zbl 0734.90098
[12] Huang, Z.; Han, J.; Xu, D.; Zhang, L., The noninterior continuation methods for solving the \(P_0\)-function nonlinear complementarity problem, Sci. China, 44, 2, 1107-1114, (2001) · Zbl 1002.90072
[13] Z.H. Huang, L. Qi, D. Sun, Sub-quadratic convergence of a smoothing Newton algorithm for the \(P_0\) and monotone LCP, manuscript, August 17, 2001. · Zbl 1168.90646
[14] Kanzow, C., Some equation-based methods for the nonlinear complementarity problem, Optim. methods software, 3, 327-340, (1994)
[15] Kanzow, C., Global convergence properties of some interative methods for linear complementarity problems, SIAM J. optim., 6, 1, 326-341, (1996) · Zbl 0847.90132
[16] Ma, C.-F.; Nie, P.-Y.; Liang, G.-P., A new smoothing equations approach to the nonlinear complementarity problems, J. comput. math., 21, 747-758, (2003) · Zbl 1047.65043
[17] Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SIAM J. control optim., 15, 1, 957-972, (1977) · Zbl 0376.90081
[18] MorĂ©, J.J.; Rheinboldt, W.C., On \(P\)- and \(S\)-functions and related classes of \(n\)-dimensional nonlinear mappings, Linear algebra appl., 6, 1, 45-68, (1973) · Zbl 0247.65038
[19] Nie, P.-Y., A null space approach for solving nonlinear complementarity problems, Acta math. appl. sinica (English ser.), 22, 1, 9-20, (2006) · Zbl 1130.90404
[20] Pang, J.S., A B-differentiable equations based, globally and locally quadratically convergent algorithm for nonlinear programming, complementarity, and variational inequality problems, Math. programming, 51, 101-131, (1991) · Zbl 0733.90063
[21] Pang, J.S.; Gabriel, S.A., NE/SQP: A robust algorithm for nonlinear complementarity problem, Math. programming, 60, 295-337, (1993) · Zbl 0808.90123
[22] Qi, H., A regularized smoothing Newton method for box constrained variational inequality problems with P0-functions, SIAM J. optim., 10, 1, 315-330, (2000)
[23] Qi, L., Convergence analysis of some algorithms for solving nonsmooth equations, Math. oper. res., 18, 1, 227-244, (1993) · Zbl 0776.65037
[24] Qi, L.; Sun, D., Improving the convergence of non-interior point algorithm for nonlinear complementarity problems, Math. comput., 69, 1, 283-304, (2000) · Zbl 0947.90117
[25] Qi, L.; Sun, D.; Zhou, G., A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems, Math. programming, 87, 1, 1-35, (2000) · Zbl 0989.90124
[26] Qi, L.; Sun, J., A nonsmooth version of Newton’s method, Math. programming, 58, 2, 353-367, (1993) · Zbl 0780.90090
[27] Tseng, P., Error bounds and superlinear convergence analysis of some Newton-type methods in optimization, (), 445-462 · Zbl 0965.65091
[28] Zhang, L.; Han, J.; Huang, Z., Superlinear/quadratic one-step smoothing Newton method for \(P_0\)-NCP, Acta math. sinica, 26, 2, 117-128, (2005) · Zbl 1124.90037
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.