Surrogate Constraint Duality in Mathematical Programming

This paper presents a unified development of a surrogate duality theory that is applicable to problems in which Lagrangean duality gaps limit the usefulness of standard duality approaches. A surrogate dual is created by generating a single constraint to replace the original problem constraints, rather than by absorbing these constraints into the objective function as in the Lagrangean. We give necessary and sufficient conditions for optimality both with and without the imposition of complementary slackness, and also consider a related “overestimating” surrogate that may be used in a strategy to bracket the optimal value of the primal. The optimality conditions invite direct comparison with those for Lagrangean duality, demonstrating not only that the surrogate approach yields smaller duality gaps than the Lagrangean (as first observed by Greenberg and Pierskalla), but also giving a precise characterization of the manner and extent to which this occurs. Concepts of parametric and relative subgradients, paralleling (and generalizing) the concept of the subgradient of ordinary duality theory, lead to easily stated results that encompass both surrogate and Lagrangean duality, as well as their composite, in a single framework.