Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems
Jansen, Benjamin
Roos, Kees
Terlaky, Tamás
Yoshise, Akiko

Fecha: 1997
Resumen: 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 (Epsilon)) of the nonlinear complementarity problem in a finite number of iterations whose order is a polynomial of n, ln(1/(Epsilon)) 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. .
Derechos: Tots els drets reservats.
Lengua: Anglès
Documento: Article ; recerca ; Versió publicada
Materia: Complementarity problems ; Interior point methods ; Primal-dual affine scaling methods ; Smoothness conditions ; Polynomial-time convergence ; Global convergence
Publicado en: Mathematical Programming, vol. 78 n. 3 (1997) p. 315-345, ISSN 0025-5610



31 p, 1.3 MB
 Acceso restringido a la UAB

El registro aparece en las colecciones:
Artículos > Artículos de investigación
Artículos > Artículos publicados

 Registro creado el 2006-03-13, última modificación el 2023-06-03



   Favorit i Compartir