Lagrangian Transformation and Interior Ellipsoid Methods in Convex Optimization

Roman Polyak ()
Additional contact information
Roman Polyak: The Technion - Israel Institute of Technology

Journal of Optimization Theory and Applications, 2015, vol. 164, issue 3, No 12, 966-992

Abstract: Abstract The rediscovery of the affine scaling method in the late 1980s was one of the turning points which led to a new chapter in Modern Optimization—the interior point methods (IPMs). Simultaneously and independently, the theory of exterior point methods for convex optimization arose. The two seemingly unconnected fields turned out to be intrinsically connected. The purpose of this paper is to show the connections between primal exterior and dual IPMs. Our main tool is the Lagrangian transformation (LT), which for inequality constrained has the best features of the classical augmented Lagrangian. We show that the primal exterior LT method is equivalent to the dual interior ellipsoid method (IEM). Using the equivalence we prove convergence, estimate the convergence rate, and establish the complexity bound for the IEM assuming boundedness of both the primal and the dual optimal sets. We show that application of the LT method with modified barrier transformation for linear programming (LP) leads to Dikin’s affine scaling method for the dual LP.

Keywords: Lagrangian transformation; Interior point methods; Duality; Bregman distance; Augmented lagrangian; Interior ellipsoid method; 90C25; 90C26 (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-014-0527-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:164:y:2015:i:3:d:10.1007_s10957-014-0527-5

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-014-0527-5

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().