  


Universal Duality in Conic Convex Optimization
Simon P. Schurr (spschurrmath.umd.edu) Abstract: Given a primaldual 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 righthand 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 righthand 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 CSTR4594, Institute for Advanced Computer Studies Report UMIACS200437, University of Maryland. May 2004. Download: [Postscript][PDF] Entry Submitted: 05/28/2004 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  