Long step homogeneous interior point algorithm for the p* nonlinear complementarity problems
DOI:
https://doi.org/10.2298/YJOR0201017LKeywords:
P*-nonlinear complementarity problem, homogeneous interior-point algorithm, wide neighborhood of the central path, polynomial complexity, quadratic convergence.Abstract
A P*-Nonlinear Complementarity Problem as a generalization of the P*-Linear Complementarity Problem is considered. We show that the long-step version of the homogeneous self-dual interior-point algorithm could be used to solve such a problem. The algorithm achieves linear global convergence and quadratic local convergence under the following assumptions: the function satisfies a modified scaled Lipschitz condition, the problem has a strictly complementary solution, and certain submatrix of the Jacobian is nonsingular on some compact set.References
Andersen, E., Ye, Y., "On a homogeneous algorithm for the monotone complementarity problem", Mathematical Programming, 84 (1999) 375-399.
Anitescu, M., Lesaja, G., and Potra, F.A., "Equivalence between different formulations of the linear complementarity problem", Optimization Methods and Software, 7 (1997) 265-290.
Anitescu, M., Lesaja, G., and Potra, F.A., "An infeasible interior-point predictor-corrector algorithm for the * p-geometric LCP", Applied Mathematics and Optimization, 36 (1997) 203-228.
Cottle, R.W., Pang, J.-S., and Stone, R.E., The Linear Complementarity Problem, Academic Press, Boston, MA, 1992.
Dikin, I.I., "Iterative solution of problems of linear and quadratic programming", Soviet Mathematics Doklady, 8 (1967) 674-675.
Ferris, M.C., and Pang, J.-S., (eds.), Complementarity and Variational Problems: State of the Art, SIAM Publishing, Philadelphia, Pennsylvania, 1997.
Güler, O., "Existence of interior points and interior paths in nonlinear monotone complementarity problems", Mathematics of Operations Research, 18 (1993) 148-162.
Jansen, B., Roos, K., Terlaky, T., and Yoshise, A., "Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems", Mathematical Programming, 78 (1997) 315-345.
Jarre, F., "Interior-point methods via self-concordance or relative Lipschitz condition", Optimization Methods and Software, 5 (1995) 75-104.
Ji, J., Potra, F.A., and Sheng, R., "A predictor-corrector method for solving the * LCP from infeasible starting points", Optimization Methods and Software, 6 (1995) 109-126.
Kojima, M., Megiddo, N., and Mizuno, S., "A general framework of continuation methods for complementarity problems", Mathematics of Operations Research, 18 (4) (1993) 945-963.
Kojima, M., Megiddo, N., Noma, T., and Yoshise, A., "A unified approach to interior point algorithms for linear complementarity problems", Lecture Notes in Comput. Scie., 538, 1991.
Kojima, M., Megiddo, N., and Noma, T., "Homotopy continuation method for nonlinear complementarity problems", Mathematics of Operations Research, 16 (1991) 754-774.
Kojima, M., Mizuno, S., and Noma, T., "A new continuation method for complementarity problems with uniform P-function", Mathematical Programming, 43 (1989) 107-113.
Kojima, M., Mizuno, S., and Noma, T., "Limiting behaviour of trajectories by a continuation method for monotone complementarity problems", Mathematics of Operations Research, 15 (1990) 662-675.
Kojima, M., Mizuno, S., and Yoshise, A., "A convex property of monotone complementarity problems", Research Reports on Information Sciences B-267, department of Information Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152, Japan, March 1993.
Kojima, M., Noma, T., and Yoshise, A., "Global convergence in infeasible-interior-point algorithms", Mathematical Programming, 65 (1994) 43-72.
Lesaja, G., "Interior point methods for * P-complementarity problems", PhD Thesis, University of Iowa, Iowa City, IA, USA, 1996.
McLinden, L., "The analogue of Moreau's proximation theorem, with applications to the nonlinear complementarity problem", Pacific Journal of Mathematics, 88 (1980) 101-161.
Miao, J., "A quadratically convergent 1 + κ (( ) ) O nL-iteration algorithm for the *( ) P-matrix linear complementarity problem", Research Report RRR 93, RUTCOR-Rutgers Center for Operations Research, Rutgers University, P.O. Box 5063, New Brunswick, NJ USA, 1993.
Monteiro, R.D.C., Pang, J.-S., and Wang, T., "A positive algorithm for the nonlinear complementarity problem", SIAM Journal on Optimization, 5 (1995) 129-148.
Monteiro, R.D.C., and Wright, S.J., "Local convergence of interior-point algorithms for degenerate monotone LCP", Computational Optimization and Applications, 3 (1994) 131-155.
Nesterov, Y.E., "Long-step strategies in interior point potential-reduction methods", Working paper, Department SES COMIN, Geneva University, 1993. (to appear in Mathematical Programming).
Nesterov, Y.E., and Nemirovsky, A.S., Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms, SIAM Publications, SIAM, Philadelphia, USA, 1994.
Peng, J., Roos, C., and Terlaky, T., "New complexity analysis of primal-dual Newton methods for *( ) linear complementarity problems", in: H. Frenk, C. Roos, T. Terlaky, and S. Zhang (eds.), High Performance Optimization, Kluwer Academic Publishers, Boston, USA, 1999, 245-265.
Peng, J., Roos, C., Terlaky, T., and Yoshise, A., "Self-regular proximities and new search directions for nonlinear P κ *( ) complementarity problems", Preprint, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada, December 2000.
Potra, F.A., "On Q-order and R-order of convergence", Journal of Optimization Theory and Applications, 63 (1989) 415-431.
Potra, F.A., and Sheng, R., "A large-step infeasible interior point method for the * LCP", SIAM Journal on Optimization, 7 (1997) 318-335.
Potra, F.A., and Sheng, R., "Homogeneous interior-point algorithms for semidefinite programming", Optimization Methods and Software, 9 (1998) 161-184.
Potra, F.A., and Ye, Y., "Interior point methods for nonlinear complementarity problems", Journal on Optimization Theory and Applications, 88 (1996) 617-647.
Sun, J., and Yhao, G., "A quadratically convergent polynomial long-step algorithm for a class of nonlinear complementarity problems", Working paper, National University of Singapore, Republic of Singapore 119260, December 1995.
Tseng, P., "Analysis of an infeasible interior path-following method for complementarity problems", Report, Department of Mathematics, University of Washington, Seattle, Washington, USA, September 1997.
Tseng, P., "An infeasible path-following method for monotone complementarity problems", SIAM Journal on Optimization, 7 (1997) 386-402.
Väliaho, H., " * P-matrices are just sufficient", Linear Algebra and its Applications, 239 (1996) 103-108.
Wright, S., and Ralph, D., "Superlinear convergence of an interior-point method for monotone variational inequalities", Mathematics of Operations Research, 21 (1996) 815-838.
Ye, Y., "On homogeneous and self-dual algorithm for LCP", Mathematical Programming, 76 (1997) 211-222.
Ye, Y., and Anstreicher, K., "On quadratic and O nL convergence of predictor-corrector algorithm for LCP", Mathematical Programming, 62 (3) (1993) 537-551.
Ye, Y., Todd, M., and Mizuno, S., "An O nL-iteration homogeneous and self-dual linear programming algorithm", Mathematics of Operations Research, 19 (1994) 53-67.
Downloads
Published
Issue
Section
License
Copyright (c) 2002 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
