The Lagrange method and SAO with bounds on the dual variables

MJD Powell (mjdpcam.ac.uk)

Abstract: We consider the general nonlinear programming problem with equality and inequality constraints when the variables x are confined to a compact set. We regard the Lagrange multipliers as dual variables lambda, those of the inequalities being nonnegative. For each lambda, we let phi(lambda) be the least value of the Lagrange function, which occurs at x=x(lambda), say. It is known that phi(.) is continuous and concave. It is also differentiable if x(lambda) is unique, which is proved using only continuity of the objective and constraint functions. If lambda maximizes phi(.), and if x(lambda) is unique, then x(lambda) solves the original problem. Bounds may be imposed on the dual variables. Then a unique x(lambda) where phi(.) is greatest minimizes the objective function plus a weighted sum of moduli of constraint violations. SAO algorithms are useful for huge numbers of variables. They generate sequences of simple nonlinear programming problems, each one being solved by the Lagrange method. The usefulness of our theory to the construction of these sequences is discussed.

Keywords: Bounded dual method; Constrained optimization; Derivatives of dual function; L_1 penalty terms; Lagrange method; Sequential approximate optimization.

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Report No. DAMTP 2011/NA16, CMS, University of Cambridge, UK, December/2011.

Download: [PDF]

Entry Submitted: 12/26/2011
Entry Accepted: 12/27/2011
Entry Last Modified: 03/27/2012

Modify/Update this entry