Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems |
| |
Authors: | Benjamin Jansen Kees Roos Tamás Terlaky Akiko Yoshise |
| |
Institution: | (1) Faculty of Technical Mathematics and Informatics, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands;(2) Institute of Socio Economic Planning, University of Tsukuba, 305 Tsukuba, Ibaraki, Japan |
| |
Abstract: | This paper provides an analysis of the polynomiality of primal-dual interior point algorithms for nonlinear complementarity
problems using a wide neighborhood. A condition for the smoothness of the mapping is used, which is related to Zhu’s scaled
Lipschitz condition, but is also applicable to mappings that are not monotone. We show that a family of primal-dual affine
scaling algorithms generates an approximate solution (given a precision ε) of the nonlinear complementarity problem in a finite
number of iterations whose order is a polynomial ofn, ln(1/ε) and a condition number. If the mapping is linear then the results in this paper coincide with the ones in Jansen
et al., SIAM Journal on Optimization 7 (1997) 126–140.
Research supported in part by Grant-in-Aids for Encouragement of Young Scientists (06750066) from the Ministry of Education,
Science and Culture, Japan.
Research supported by Dutch Organization for Scientific Research (NWO), grant 611-304-028 |
| |
Keywords: | Complementarity problems Interior point methods Primal-dual affine scaling methods Smoothness conditions Polynomial-time convergence Global convergence |
本文献已被 SpringerLink 等数据库收录! |
|