On Augmented Lagrangeans in Linear Programming (LP) Phase I

Abstract

The concept of linking constraints to an objective in optimization problems was found due to Lagrange in the 19th century. The so-called Lagrange multipliers were related to duality theory in the 20th century. At the same time, ideas from penalty methods were linked with ideas of the Lagrangean called Augmented Lagrangean (AL) methods. The concepts have been applied to Nonlinear Optimization, Global Optimization and also even recent to Linear Programming (LP) [1]. This paper focuses on the latter question of how AL methods can be applied efficiently to find initial feasible solutions as a starting point in scarce LP procedures. In this contribution, we will expose our findings of applying methods to Linear Programming methods. [1] Ivet L. Galabova and Julian A. J. Hall. The ‘idiot’ crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems. Optimization Methods and Software, 35(3):488–501, May 2020.