×

Predictor-corrector smoothing Newton method, based on a new smoothing function, for solving the nonlinear complementarity problem with a \(P_0\) function. (English) Zbl 1044.90081

Summary: By smoothing a perturbed minimum function, we propose in this paper a new smoothing function. The existence and continuity of a smooth path for solving the nonlinear complementarity problem (NCP) with a \(P_0\) function are discussed. We investigate the boundedness of the iteration sequence generated by noninterior continuation/smoothing methods under the assumption that the solution set of the NCP is nonempty and bounded. Based on the new smoothing function, we present a predictor-corrector smoothing Newton algorithm for solving the NCP with a \(P_0\) function, which is shown to be globally linearly and locally superlinearly convergent under suitable assumptions. Some preliminary computational results are reported.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
49M15 Newton-type methods
90C53 Methods of quasi-Newton type
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] CHEN, B., and CHEN, X., A Global and Local Superlinear Continuation-Smoothing Method for P 0CR0 and Monotone NCP, SIAM Journal on Optimization, Vol. 9, pp. 624-645, 1999. · Zbl 0955.90132
[2] CHEN, X., and YE, Y., On Smoothing Methods for the P 0 Matrix Linear Complementarity Problem, SIAM Journal on Optimization, Vol. 11, pp. 341-363, 2000. · Zbl 0994.65077
[3] FACCHINEI, F., and KANZOW, C., Beyond Monotonicity in Regularization Methods for Nonlinear Complementarity Problems, SIAM Journal on Control and Optimization, Vol. 37, pp. 1150-1161, 1999. · Zbl 0997.90085
[4] GOWDA, M. S., and TAWHID, M.A., Existence and Limiting Behavior of Trajectories Associated with P 0 -Equations, Computational Optimization and Applications, Vol. 12, pp. 229-251, 1999. · Zbl 1040.90563
[5] HOTTA, K., and YOSHISE, A., Global Convergence of a Noninterior-Point Algorithms Using Chen-Harker-Kanzow Functions for Nonlinear Complementarity Problems, Mathematical Programming, Vol. 86, pp. 105-133, 1999. · Zbl 0978.90095
[6] RAVINDRAN, G., and GOWDA, M. S., Regularization of P 0 -Functions in Box Variational Inequality Problems, SIAM Journal on Optimization, Vol. 11, pp. 748-760, 2000. · Zbl 1010.90083
[7] SUN, D., A Regularization Newton Method for Solving Nonlinear Complementarity Problems, Applied Mathematics and Optimization, Vol. 36, pp. 315-339, 1999. · Zbl 0937.90110
[8] SUN, D., and QI, L., Solving Variational Inequality Problems via Smoothing-Nonsmooth Reformulations, Journal of Computational and Applied Mathematics, Vol. 129, pp. 37-62, 2001. · Zbl 0987.65059
[9] HARKER, P. T., and PANG, J.S., Finite-Dimensional Variational Inequality and Nonlinear Complementarity Problems: A Survey of Theory, Algorithms, and Applications, Mathematical Programming, Vol. 48, pp. 339-357, 1990. · Zbl 0724.90071
[10] PANG, J. S., Complemntarity Problems, Handbook of Global Optimization, Edited by R. Horst and P. Pardalos, Kluwer Academic Publishers, Boston, Massachusetts, pp. 271-338, 1995.
[11] KANZOW, C., Some Noninterior Continuation Methods for Linear Complementarity Problems, SIAM Journal on Matrix Analysis and Applications, Vol. 17, pp. 851-868, 1996. · Zbl 0868.90123
[12] ENGELKE, S., and KANZOW, C., Predictor-Corrector Smoothing Methods for the Solution of Linear Programming, Preprint, Department of Mathematics, University of Hamburg, Hamburg, Germany, 2000. · Zbl 1028.90026
[13] CHEN, B., and HARKER, P.T., A Noninterior-Point Continuation Method for Linear Complementarity Problems, SIAM Journal on Matrix Analysis and Applications, Vol. 14, pp. 1168-1190, 1993. · Zbl 0788.65073
[14] SMALE, S., Algorithms for Solving Equations, Proceeding of the International Congress of Mathematicians, Edited by A. M. Gleason, American Mathematics Society, Providence, Rhode Island, pp. 172-195, 1987. · Zbl 0665.65058
[15] CHEN, X., and QI, L., A Parametrized Newton Method and a Broyden-Like Method for Solving Nonsmooth Equations, Computational Optimization and Applications, Vol. 3, pp. 157-179, 1994. · Zbl 0821.65029
[16] CHEN, C., and MANGASARIAN, O.L., A Class of Smoothing Functions for Nonlinear and Mixed Complementarity Problems, Computational Optimization and Applications, Vol. 5, pp. 97-138, 1996. · Zbl 0859.90112
[17] TSENG, P., Analysis of a Noninterior Continuation Method Based on Chen-Mangasarian Smoothing Functions for Complementarity Problems, Reformulation: Nonsmooth, Piecewise-Smooth, Semismooth, and Smoothing Methods, Edited by M. Fukushima and L. Qi, Kluwer Academic Publishers, Boston, Massachusetts, pp. 381-404, 1998.
[18] GABRIEL, S. A., and MORÉ, J. J., Smoothing of Mixed Complementarity Problems, Complementarity and Variational Problems: State of the Art, Edited by M. C. Ferris and J. S. Pang, SIAM Publications, Philadelphia, Pennsylvania, pp. 105-116, 1997. · Zbl 0886.90154
[19] BURKE, J., and XU, S., The Global Linear Convergence of a Noninterior Path-Following Algorithm for Linear Complementarity Problems, Mathematics of Operations Research, Vol. 23, pp. 719-734, 1998. · Zbl 0977.90056
[20] BURKE, J., and XU, S., A Noninterior Predictor-Corrector Path-Following Algorithm for LCP, Reformulation: Nonsmooth, Piecewise-Smooth, Semismooth, and Smoothing Methods, Edited by M. Fukushima and L. Qi, Kluwer Academic Publishers, Boston, Massachusetts, pp. 45-64, 1998.
[21] CHEN, B., and XIU, N., A Global Linear and Local Quadratic Noninterior Continuation Method for Nonlinear Complementarity Problems Based on Chen-Mangasarian Smoothing Functions, SIAM Journal on Optimization, Vol. 9, pp. 605-623, 1999. · Zbl 1037.90052
[22] KANZOW, C., A New Approach to Continuation Methods for Complementarity Problem with Uniform P-Functions, Operations Research Letters, Vol. 20, pp. 85-92, 1997. · Zbl 0890.90169
[23] QI, L., SUN, D., and ZHOU, G., A New Look at Smoothing Newton Methods for Nonlinear Complementarity Problems and Box-Constrained Variational Inequalities, Mathematical Programming, Vol. 87, pp. 1-35, 2000. · Zbl 0989.90124
[24] XU, S., The Global Linear Convergence of an Infeasible Noninterior Path-Following Algorithm for Complementarity Problems with Uniform P-Functions, Mathematical Programming, Vol. 87, pp. 501-517, 2000. · Zbl 0989.90125
[25] KARAMARDIAN, S., Complementarity Problems over Cones with Monotone and Pseudomonotone Maps, Journal of Optimization Theory and Applications, Vol. 18, pp. 445-454, 1976. · Zbl 0304.49026
[26] MCLINDEN, L., Stable Monotone Variational Inequalities, Mathematical Programming, Vol. 48, pp. 303-338, 1990. · Zbl 0726.90093
[27] QI, H.D., A Regularization Smoothing Newton Method for Box-Constrained Variational Inequality Problems with P 0 -Functions, SIAM Journal on Optimization, Vol. 10, pp. 315-330, 1999. · Zbl 0955.90136
[28] BURKE, J., and XU, S., A Noninterior Predictor-Corrector Path-Following Algorithm for the Monotone Linear Complementarily Problem, Mathematical Programming, Vol. 87, pp. 113-130, 2000. · Zbl 1081.90603
[29] CHEN, B., and CHEN, X., A Global Linear and Local Quadratic Continuation Smoothing Method for Variational Inequalities with Box Constraints, Computational Optimization and Applications, Vol. 13, pp. 131-158, 2000. · Zbl 0987.90079
[30] QI, L., and SUN, D., Improving the Convergence of a Noninterior-Point Algorithm for Nonlinear Complementarity Problems, Mathematics of Computation, Vol. 69, pp. 283-304, 2000. · Zbl 0947.90117
[31] GOWDA, M. S., and SZNAJDER, J. J., Weak Univalence and Connectedness of Inverse Images of Continuous Functions, Mathematics of Operations Research, Vol. 24, pp. 255-261, 1999. · Zbl 0977.90060
[32] KOJIMA, M., MEGIDDO, N., and NOMA, T., Homotopy Continuation Methods for Nonlinear Complementarity Problems, Mathematics of Operations Research, Vol. 16, pp. 754-774, 1991. · Zbl 0744.90087
[33] KOJIMA, M., MEGIDDO, N., NOMA, T., and YOSHISE, A., A Unified Approach to Interior-Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science, Springer Verlag, Berlin, Germany, Vol. 538, 1991. · Zbl 0745.90069
[34] FISCHER, A., and KANZOW, C., On Finite Termination of an Iterative Method for Linear Complementarity Problems, Mathematical Programming, Vol. 74, pp. 279-292, 1996. · Zbl 0855.90125
[35] MIFFLIN, R., Semismooth and Semiconvex Functions in Constrained Optimization, SIAM Journal on Control and Optimization, Vol. 15, pp. 957-972, 1977. · Zbl 0376.90081
[36] QI, L., and SUN, J., A Nonsmooth Version of Newton’s Method, Mathematical Programming, Vol. 58, pp. 353-367, 1993. · Zbl 0780.90090
[37] DE LUCA, FACCHINEI, T., and KANZOW, C., A Semismooth Equation Approach to the Solution of Nonlinear Complementarity Problems, Mathematical Programming, Vol. 75, pp. 407-439, 1996. · Zbl 0874.90185
[38] FISCHER, A., Solution of Monotone Complementarity Problems with Locally Lipschitzian Functions, Mathematical Programming, Vol. 76, pp. 513-532, 1997. · Zbl 0871.90097
[39] JIANG, H., and QI, L., A New Nonsmooth Eqations Approach to Nonlinear Complementarity Problems, SIAM Journal on Control and Optimization, Vol. 35, pp. 178-193, 1997. · Zbl 0872.90097
[40] CLARKE, F.H., Optimization and Nonsmooth Analysis, Wiley, New York, NY, 1983. · Zbl 0582.49001
[41] PANG, J. S., and GABRIEL, S.A., NE/SQP: A Robust Algorithm for the Nonlinear Complementarity Problem, Mathematical Programming, Vol. 60, pp. 295-337, 1993. · Zbl 0808.90123
[42] MANGASARIAN, O. L., and SOLODOV, M.V., Nonlinear Complementarity as Unconstrained and Constrained Minimization, Mathematical Programming, Vol. 62B, pp. 277-297, 1993. · Zbl 0813.90117
[43] KANZOW, C., Some Equation-Based Methods for Nonlinear Complementarity Problems, Optimization Methods and Software, Vol. 3, pp. 327-340, 1994.
[44] GEIGER, C., and KANZOW, C., On the Resolution of Monotone Complementarity Problems, Computational Optimization and Applications, Vol. 5, pp. 155-173, 1996. · Zbl 0859.90113
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.