Co-authors:
Simon Schurr and Levent Tuncel
(Department of Combinatorics and Optimization, University of Waterloo)
Abstract
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.