Given a primal-dual pair of linear programs, it is well known that if their optimal values are viewed as lying on the extended real line, then the duality gap is zero, unless both problems are infeasible, in which case the optimal values are +infinity and -infinity. In contrast, for optimization problems over nonpolyhedral convex cones, a nonzero duality gap can exist when either the primal or dual is feasible. For a pair of dual conic convex programs, we provide simple conditions on the “constraint matrices” and cone under which the duality gap is zero for every choice of linear objective function and constraint right-hand side. We refer to this property as “universal duality”. Our conditions possess the following properties: (i) they are necessary and sufficient, in the sense that if (and only if) they do not hold, the duality gap is nonzero for some linear objective function and constraint right-hand side; (ii) they are metrically and topologically generic; and (iii) they can be verified by solving a single conic convex program. We relate to universal duality the fact that the feasible sets of a primal convex program and its dual cannot both be bounded, unless they are both empty. Finally we illustrate our theory on a class of semidefinite programs that appear in control theory applications.
Citation
Universal Duality in Conic Convex Optimization," Computer Science Department Report CS-TR-4594, Institute for Advanced Computer Studies Report UMIACS-2004-37, University of Maryland. May 2004.