Long-step strategies in interior-point primal-dual methods
Nesterov, Yu.

Fecha: 1997
Resumen: In this paper we analyze from a unique point of view the behavior of path-following and primal-dual potential reduction methods on nonlinear conic problems. We demonstrate that most interior-point methods with O(V~n ln(1/(Epsilon))) efficiency estimate can be considered as different strategies of minimizing a convex primal-dual potential function in an extended primal-dual space. Their efficiency estimate is a direct consequence of large local norm of the gradient of the potential function along a central path. It is shown that the neighborhood of this path is a region of the fastest decrease of the potential. Therefore the long-step path-following methods are, in a sense, the best potential-reduction strategies. We present three examples of such long-step strategies. We prove also an efficiency estimate for a pure primal-dual potential reduction method, which can be considered as an implementation of a penalty strategy based on a functional proximity measure. Using the convex primal dual potential, we prove efficiency estimates for Karmarkar-type and Dikin-type methods as applied to a homogeneous reformulation of the initial primal-dual problem.
Derechos: Aquest material està protegit per drets d'autor i/o drets afins. Podeu utilitzar aquest material en funció del que permet la legislació de drets d'autor i drets afins d'aplicació al vostre cas. Per a d'altres usos heu d'obtenir permís del(s) titular(s) de drets.
Lengua: Anglès
Documento: Article ; recerca ; Versió publicada
Materia: Nonlinear programming ; Conic problem ; Interior-point methods ; Self-concordant barrier ; Path-following methods ; Potential-reduction methods
Publicado en: Mathematical Programming, vol. 76 n. 1 (1997) p. 47-94, ISSN 0025-5610



48 p, 1.8 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 2024-12-07



   Favorit i Compartir