Tutte seminar - Henry Wolkowicz

Duality, Complementarity, and Regularization, in Conic Convex Optimization

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. 
We take a fresh look at known and new results for duality, optimality, constraint qualifications, and 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 nice and devious cones; the geometric relationships between zero duality gaps, 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 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 then discuss the surprising connections between the duality theory and complementarity. 
Our emphasis is on results that deal with Semidefinite Programming (SDP).

Joint work with Simon Schurr and Levent Tuncel.