Strong Duality and Stability in Conic Convex Optimization

Henry Wolkowicz
(Department of Combinatorics and Optimization, University of Waterloo)

Co-authors: Simon Schurr and Levent Tuncel
(Department of Combinatorics and Optimization, University of Waterloo)

For nonlinear convex optimization problems, in the absence of a constraint qualification strong duality need not hold. Moreover, constraint qualifications are closely tied to numerical stability and well posedness. The Extended Lagrange Slater dual of Ramana is a Semidefinite Programming, SDP, dual for which strong duality holds without a constraint qualification. We explain when an extension of Ramana's algorithm to general conic convex problems efficiently computes a strong dual. We also give other strong duals that do not require a constraint qualification, and that are defined solely in terms of the data of the given problem.

We then present an algorithm that solves in an efficient and stable way feasible conic convex optimization problems, including those for which the Slater constraint qualification fails. Necessary and sufficient conditions for a finite nonzero duality gap are given, and it is shown how these can be used to generate instances satisfying this property. Numerical tests are included.

at: Erice Sicily Optimization July 31- Aug. 9, 2007.