Optimization Online


Strong Duality and Minimal Representations for Cone Optimization

Levent Tuncel (ltuncel***at***math.uwaterloo.ca)
Henry Wolkowicz (hwolkowicz***at***uwaterloo.ca)

Abstract: The elegant results for strong duality and strict complementarity for linear programming, \LP, can fail for cone programming over nonpolyhedral cones. One can have: unattained optimal values; nonzero duality gaps; and no primal-dual optimal pair that satisfies strict complementarity. This failure is tied to the nonclosure of sums of nonpolyhedral closed cones. We take a fresh look at known and new results for duality, optimality, constraint qualifications, and strict complementarity, for linear cone optimization problems in finite dimensions. These results include: weakest and universal constraint qualifications, \CQs; duality and characterizations of optimality that hold without any \CQ; geometry of {\em nice and devious} cones; the geometric relationships between zero duality gaps, strict complementarity, and the facial structure of cones; and, the connection between theory and empirical evidence for lack of a \CQ and failure of strict complementarity. One theme is the notion of {\em minimal representation} of the cone and the constraints in order to regularize the problem and avoid both the theoretical and numerical difficulties that arise due to (near) loss of a \CQ. We include a discussion on obtaining these representations efficiently. A parallel theme is the loss of strict complementarity and the corresponding theoretical and numerical difficulties that arise; a discussion on avoiding these difficulties is included. We include results and examples on the surprising theoretical connection between duality and complementarity and nonclosure of sums of closed cones. Our emphasis is on results that deal with Semidefinite Programming, \SDP.

Keywords: Cone Optimization, Duality, Constraint Qualification, Semidefinite

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: CORR 2008-07, University of Waterloo, Canada, August/08.

Download: [Postscript][PDF]

Entry Submitted: 08/07/2008
Entry Accepted: 08/07/2008
Entry Last Modified: 04/11/2011

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