Augmented Lagrange Multiplier Functions and Duality in Nonconvex Programming

TLDR

Nonlinear programming typically exhibits a duality gap when using the ordinary Lagrangian unless the problem is convex. The study proposes that augmenting the Lagrangian could improve penalty methods for computing solutions. The modified dual problem maximizes a concave function of the Lagrange multipliers together with a penalty parameter. The augmented Lagrangian removes the duality gap, permits unrestricted inequality multipliers, and represents primal optimal solutions as global saddle points when the dual maximum exists.

Abstract

If a nonlinear programming problem is analyzed in terms of its ordinary Lagrangian function, there is usually a duality gap, unless the objective and constraint functions are convex. It is shown here that the gap can be removed by passing to an augmented Lagrangian which involves quadratic penalty-like terms. The modified dual problem then consists of maximizing a concave function of the Lagrange multipliers and an additional variable, which is a penalty parameter. In contrast to the classical case, the multipliers corresponding to inequality constraints in the primal are not constrained a priori to be nonnegative in the dual. If the maximum in the dual problem is attained (and conditions implying this are given), optimal solutions to the primal can be represented in terms of global saddle points of the augmented Lagrangian. This suggests possible improvements of existing penalty methods for computing solutions.