Optimization Online


Universal Duality in Conic Convex Optimization

Simon P. Schurr (spschurr***at***math.umd.edu)
Andr\'e Tits (andre***at***umd.edu)
Dianne P. O'Leary (oleary***at***cs.umd.edu)

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

Keywords: Conic convex optimization, constraint qualification, duality gap, universal duality, generic property

Category 1: Linear, Cone and Semidefinite Programming

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.

Download: [Postscript][PDF]

Entry Submitted: 05/28/2004
Entry Accepted: 06/01/2004
Entry Last Modified: 10/04/2005

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society