ADDITIVELY SEPARABLE DUALITY-THEORY

In duality theory, there is a trade-off between generality and tractab ility. Thus, the generality of the Tind-Wolsey framework comes at the expense of an infinite-dimensional dual solution space, even if the pr imal solution space is finite dimensional. Therefore, the challenge is to impose additional structure on the dual solution space and to iden tify conditions on the primal program, such that the properties that a re typically associated with duality, like weak and strong duality, ar e preserved. In this paper, we consider real-valuedness, continuity, a nd additive separability as such additional structures. The virtue of the latter property is that it restores the one-to-one correspondence between primal constraints and dual variables as it exists in Lagrangi an duality. The main result of this paper is that, roughly speaking, t he existence of real-valued, continuous, and additively separable dual solutions that preserve strong duality is guaranteed, once the primal program satisfies a certain stability condition. The latter condition is ensured by the well-known regularity conditions that imply constra int qualification in Karush-Kuhn-Tucker points. On the other hand, if instead of additive separability, a mild tractability condition is imp osed on the dual solution space, then stability turns out to be a nece ssary condition for strong duality in a well-defined sense. This resul t, combined with the observation that stability is a fairly restrictiv e requirement, may clarify the limited applicability of some well-know n augmented Lagrangian methods to constrained optimization.