Optimization Online


Lagrangian Transformation and Interior Ellipsoid Methods in Convex Optimization

Roman Polyak(rpolyak***at***gmu.edu)

Abstract: The rediscovery of the affine scaling method in the late 80s 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 interior point methods. 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. Using the equivalence we prove convergence, estimate the convergence rate and establish the complexity bound for the interior ellipsoid method under minimum assumptions on the input data. We show that application of the LT method with modi ed barrier (MBF) 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

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Technical Report 11_01_2010, SEOR/Math, George Mason University, Fairfax, VA, USA

Download: [PDF]

Entry Submitted: 05/08/2013
Entry Accepted: 05/08/2013
Entry Last Modified: 05/08/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society