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. (1999) On a homogeneous algorithm for the monotone complementarity problem. Mathematical Programming Series A, 84, 2, 375-399
Anitescu, M., Lesaja, G., Potra, F.A. (1997) Equivalence between different formulations of the linear complementarity problem. Optimization Methods and Software, 7, 4, 265-290
Anitescu, M., Lesaja, G., Potra, F.A. (1997) An infeasible-interior-point predictor-corrector algorithm for the $Psb *$-geometric LCP. Applied Mathematics and Optimization, 36, 2, 203-228
Cottle, R.W., Pang, J.S., Stone, R.E. (1992) The linear complementarity problem. New York-San Diego, itd: Academic Press
Dikin, I.I. (1967) Iterative solution of problems of linear and quadratic programming. Doklady Akademii Nauk SSSR, 174, 747-748
Ferris, M.C., Pang, J.S., ur. (1997) Complementarity and variational problems: State of the art. Philadelphia: Society for Industrial and Applied Mathematics Publications
Geler, O. (1993) Existence of interior points and interior paths in nonlinear monotone complementarity problems. Mathematics of Operations Research, 18, 1, 128-147
Jansen, B., Roos, K., Terlaky, T., Yoshise, A. (1997) Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems. Mathematical Programming Series A, 78, 3, 315-345
Jarre, F. (1995) Interior-point methods via self-concordance or relative Lipschitz condition. Optimization Methods and Software, 5, 75-104
Ji, J., Potra, F.A., Sheng, R. (1995) A predictor-corrector method for solving the P*-matrix LCP from infeasible starting points. Optimization Methods and Software, 6, 109-126
Kojima, M., Megiddo, N., Mizuno, S. (1993) A general framework of continuation methods for complementarity problems. Mathematics of Operations Research, 18, 4, 945-963
Kojima, M., Megiddo, N., Noma, T., Yoshise, A. (1991) A unified approach to interior point algorithms for linear complementarity problems. Lecture Notes in Computer Science, 538
Kojima, M., Megiddo, N., Noma, T. (1991) Homotopy continuation methods for nonlinear complementarity problems. Mathematics of Operations Research, 16, 4, 754-774
Kojima, M., Mizuno, S., Noma, T. (1989) A new continuation method for complementarity problems with uniform P-function. Mathematical Programming Series A, 43, 107-113
Kojima, M., Mizuno, S., Noma, T. (1990) Limiting behavior of trajectories generated by a continuation method for monotone complementarity problems. Mathematics of Operations Research, 15, 4, 662-675
Kojima, M., Mizuno, S., Yoshise, A. (1993) A convex property of monotone complementarity problems. u: Research Reports on Information Sciences B-267, Tokyo: Institute of Technology - Department of Information Sciences, March
Kojima, M., Noma, T., Yoshise, A. (1994) Global convergence in infeasible-interior-point algorithms. Mathematical Programming Series A, 65, 1, 43-72
Lesaja, G. (1996) Interior point methods for P*-complementarity problems. Iowa City, IA: University of Iowa, doktorska disertacija
Mclinden, L. (1980) An analogue of Moreau's proximation theorem, with application to the nonlinear complementarity problem. Pacific Journal of Mathematics, 88, 1, 101-161
Miao, J. (1993) A quadratically convergent O((1+k)sqrt(nL))-iteration algorithm for the P*(k)-matrix linear complementarity problem. New Brunswick, NJ: Rutgers University - Rutgers Center for Operations Research, RUTCOR Research Report RRR 93
Monteiro, R.D.C., Pang, J.S., Wang, T. (1995) A positive algorithm for the nonlinear complementarity problem. SIAM Journal on Optimization, 5, 1, 129-148
Monteiro, R.D.C., Wright, S.J. (1994) Local convergence of interior-point algorithms for degenerate monotone LCP. Computational Optimization and Applications, 3, 2, 131-155
Nesterov, Y.E. (1993) Long-step strategies in interior point potential-reduction methods. Geneva University - Department SES COMIN, Working paper
Nesterov, Y.E., Nemirovsky, A.S. (1994) Interior point polynomial methods in convex programming: Theory and algorithms. Philadelphia: Society for Industrial and Applied Mathematics Publications / SIAM Publications
Peng, J., Roos, C., Terlaky, T. (1999) New complexity analysis of primal-dual Newton methods for P*(k) linear complementarity problems. u: Frenk H., Roos C., Terlaky T., Zhang S. [ur.] High Performance Optimization, Dordrecht, itd: Kluwer, 245-265
Peng, J., Roos, C., Terlaky, T., Yoshise, A. (2000) Self-regular proximities and new search directions for nonlinear P*(k) complementarity problems. Hamilton, Ontario: McMaster University, December
Potra, F.A. (1989) On $Q$-order and $R$-order of convergence. Journal of Optimization Theory and Applications, 63, 3, 415-431
Potra, F.A., Sheng, R. (1997) A large-step infeasible-interior-point method for the $Psb *$-matrix LCP. SIAM Journal on Optimization, 7, 2, 318-335
Potra, F.A., Sheng, R. (1998) On homogeneous interior-point algorithms for semidefinite programming. Optimization Methods and Software, 9, 3, 161-184
Potra, F.A., Ye, Y. (1996) Interior-point methods for nonlinear complementarity problems. Journal of Optimization Theory and Applications, 88, 3, 617-642
Sun, J., Yhao, G. (1995) A quadratically convergent polynomial long-step algorithm for a class of nonlinear complementarity problems. Singapore: National University of Singapore, Working paper, December
Tseng, P. (1997) Analysis of an infeasible interior path-following method for complementarity problems: Report. Seattle: Department of Mathematics - University of Washington, September
Tseng, P. (1997) An infeasible path-following method for monotone complementarity problems. SIAM Journal on Optimization, 7, 2, 386-402
Valiaho, H. (1996) ${bf P}sb *$-matrices are just sufficient. Linear Algebra and its Applications, 239, 103-108
Wright, S., Ralph, D. (1996) Superlinear convergence of an interior-point method for 391 monotone variational inequalities. Mathematics of Operations Research, 21, 815-838
Ye, Y. (1997) On homogeneous and self-dual algorithm for LCP. Mathematical Programming Series A, 76, 211-222
Ye, Y., Anstreicher, K. (1993) On quadratic and O(sqrt(nL)) convergence of predictor-corrector algorithm for LCP. Mathematical Programming Series A, 62,(3) 537-551
Ye, Y., Todd, M., Mizuno, S. (1994) An O(sqrt(nL))-iteration homogeneous and self-dual linear programming algorithm. Mathematics of Operations Research, 19, 53-67
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
