Mixed complementary problems: regularity, estimates of the distance to the solution, and Newton's Methods

A. N. Daryina   ; A. F. Izmailov   ; M. V. Solodov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 44 (2004) no. 1, pp. 51-69

Bibliographie

[1] Harker P. T., Pang J.-S., “Finite-dimensional variational inequality problems: A survey of theory, algorithms and applications”, Math. Program., 48 (1990), 161–220 | DOI | MR | Zbl

[2] Ferris M. C., Pang J.-S., “Engineering and economic applications of complementarity problems”, SIAM Rev., 39 (1997), 669–713 | DOI | MR | Zbl

[3] Facchinei F., Pang J.-S., Finite-dimensional variational inequalities and complementarity problems, Springer, New York, 2003

[4] Pang J.-S., “Error bounds in mathematical programming”, Math. Program., 79 (1997), 299–332 | MR | Zbl

[5] Facchinei F., Fischer A., Kanzow C., “On the accurate identification of active constraints”, SIAM J. Optimizat., 9 (1999), 14–32 | DOI | MR

[6] Izmailov A. F., Solodov M. V., “Karush-Kuhn-Tucker systems: regularity conditions, error bounds and a class of Newton-type methods”, Math. Program., 95 (2003), 631–650 | DOI | MR | Zbl

[7] Klark F., Optimizatsiya i negladkii analiz, Nauka, M., 1988 | MR | Zbl

[8] Fischer A., “A special Newton-type optimization method”, Optimization, 24 (1992), 269–284 | DOI | MR | Zbl

[9] Facchinei F., Soares J., “A new merit function for nonlinear complementarity problems and a related algorithm”, SIAM J. Optimizat., 7 (1997), 225–247 | DOI | MR | Zbl

[10] Evtushenko Yu. G., Purtov V. A., “Dostatochnye usloviya dlya minimuma v zadachakh nelineinogo programmirovaniya”, Dokl. AN SSSR, 278:1 (1984), 24–26 | MR

[11] Kanzow C., “Some equation-based methods for the nonlinear complementarity problem”, Optimizat. Methods and Software, 3 (1994), 327–340 | DOI

[12] Tseng P., “Growth behavior of a class of merit functions for the nonlinear complementarity problem”, J. Optimizat. Theory and Applic., 89 (1996), 17–37 | DOI | MR | Zbl

[13] Ferris M. C., Kanzow C., Munson T. S., “Feasible descent algorithms for mixed complementarity problems”, Math. Program., 86 (1999), 475–497 | DOI | MR | Zbl

[14] Bonnans J. F., “Local analysis of Newton-type methods for variational inequalities and nonlinear programming”, Appl. Math. Optimizat., 29 (1994), 161–186 | DOI | MR | Zbl

[15] De Luca T., Facchinei F., Kanzow C., “A theoretical and numerical comparison of some semismooth algorithms for complementarity problems”, Comput. Optimizat. Appl., 16 (2000), 173–205 | DOI | MR | Zbl

[16] Kanzow C., Fukushima M., “Solving box constrained variational inequality problems by using the natural residual with $D$-gap function globalization”, Operat. Res. Letts., 23 (1998), 45–51 | DOI | MR | Zbl

[17] Pang J. S., Gabriel S. A., “NE/SQP: a robust algorithm for the nonlinear complementarity problem”, Math. Program., 60 (1993), 295–337 | DOI | MR | Zbl

[18] Robinson S. M., “Strongly regular generalized equations”, Math. Operat. Res., 5 (1980), 43–62 | DOI | MR | Zbl

[19] Kojima M., “Strongly stable stationary solutions in nonlinear programs”, Analys. and Comput. of Fixed Points, Acad. Press, New York, 1980, 93–138 | MR

[20] Izmailov A. F., Solodov M. V., “Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications”, Math. Program., 89 (2001), 413–435 | DOI | MR | Zbl

[21] Izmailov A. F., Solodov M. V., “The theory of 2-regularity for mappings with Lipschitzian derivatives and its applications to optimality conditions”, Math. Operat. Res., 27 (2002), 614–635 | DOI | MR | Zbl

[22] Bertsekas D., Uslovnaya optimizatsiya i metody mnozhitelei Lagranzha, Radio i svyaz, M., 1987 | MR | Zbl

[23] Bertsekas D. P., Nonlinear programming, Sec. Ed., Athena Scient, Belmont, 1999 | Zbl

[24] Kanzow C., “Stricly feasible equation-based methods for mixed complementarity problems”, Numer. Math., 89 (2001), 135–160 | DOI | MR | Zbl

[25] De Luca T., Facchinei F., Kanzow C., “A semismooth equation approach to the solution of nonlinear complementarity problems”, Math. Program., 75 (1996), 407–439 | DOI | MR | Zbl

[26] Solodov M. V., Svaiter B. F., “A truly globally convergent Newton-type method for the monotone nonlinear complementarity problem”, SIAM J. Optimizat., 10 (2000), 605–625 | DOI | MR | Zbl

[27] Vasilev F. P., Metody optimizatsii, Faktorial Press, M., 2002

[28] Kummer B., “Newton's method for nondifferentiable functions”, Advances in Math. Optimizat., 45, Akad. Verlag, Berlin, 1988, 114–125 | MR

[29] Kummer B., “Newton's method based on generalized derivatives for nonsmooth functions”, Advances in Optimizat., Springer, Berlin, 1992, 171–194 | MR

[30] Qi L., “Convergence analysis of some algorithms for solving nonsmooth equations”, Math. Operat. Res., 18 (1993), 227–244 | DOI | MR | Zbl

[31] Qi L., Sun J., “A nonsmooth version of Newton's method”, Math. Program., 58 (1993), 353–367 | DOI | MR | Zbl

[32] Billups S. C., Algorithms for complementarity problems and generalized equations, PhD thesis, Madison, 1995, 159 pp. | MR

[33] Qi L., Jiang H., “Semismooth Karush-Kuhn-Tucker equations and convergence analysis of Newton and quasi-Newton methods for solving these equations”, Math. Operat. Res., 22 (1997), 301–325 | DOI | MR | Zbl

[34] Jiang H., Ralph D., “Global and local superlinear convergence analysis of Newton-type methods for semismooth equations with smooth least squares”, Reformulation - Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Acad. Publs, Amsterdam, 1999, 181–210 | MR

[35] Jiang H., “Global convergence analysis of the generalized Newton and Gauss-Newton methods of the Fischer-Burmeister equation for the complementarity problem”, Math. Operat. Res., 24 (1999), 529–543 | DOI | MR | Zbl

[36] Sun D., Womersley R. S., Qi H., “A feasible semismooth asymptotically Newton method for mixed complementarity problems”, Math. Program., 94 (2002), 167–187 | DOI | MR | Zbl

[37] Fischer A., “Local behaviour of an iterative framework for generalized equations with nonisolated solutions”, Math. Program., 94 (2002), 91–124 | DOI | MR | Zbl

[38] Bonnans J. F., “Asymptotic admissibility of the unit stepsize in exact penalty methods”, SIAM J. Control Optimizat., 27:3 (1989), 631–641 | DOI | MR | Zbl

[39] Izmailov A. F., Solodov M. V., “Superlinearly convergent algorithms for solving singular equations and smooth reformulations of complementarity problems”, SIAM J. Optimizat., 13:2 (2002), 386–405 | DOI | MR | Zbl

[40] Dan H., Yamashita N., Fukushima M., “A superlinearly convergent algorithm for the monotone nonlinear complementarity problem without uniqueness and nondegeneracy conditions”, Math. Operat. Res., 27:4 (2002), 743–753 | DOI | MR

[41] Hintermüller M., Ito K., Kunisch K., “The primal-dual active set strategy as a semismooth Newton method”, SIAM J. Optimizat., 13:3 (2003), 865–888 | DOI | MR