Long-step strategies in interior-point primal-dual methods
(1996) Mathematical Programming — Vol. 76, p. 47-94 (1996)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- 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(√nln(1/∈))efficiency estimate can be considered as different strategies of minimizing aconvex 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 apenalty 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.
- Affiliations
Citations
Nesterov, Y. (1996). Long-step strategies in interior-point primal-dual methods. Mathematical Programming, 76, 47-94. https://hdl.handle.net/2078.5/174279 (Original work published 1996)