Surrogate Constraint Duality in Mathematical Programming

Fred Glover
Additional contact information
Fred Glover: University of Colorado, Boulder, Colorado

Operations Research, 1975, vol. 23, issue 3, 434-451

Abstract: 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.

Date: 1975
References: Add references at CitEc
Citations: View citations in EconPapers (31)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.23.3.434 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:23:y:1975:i:3:p:434-451

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().