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.
Citation
Technical Report 11_01_2010, SEOR/Math, George Mason University, Fairfax, VA, USA