Abstract:

For convex minimization problems with optimal value v_P < ∞, weak duality holds in general, i.e. the optimal value of the Lagrangian dual provides a lower bound, v_D ≤ v_P. However, strong duality (i.e. v_D = v_P and v_D is attained) requires a constraint qualification, CQ, e.g. the Slater (strict feasibility) CQ. In the absence of a CQ, the dual optimal value v_D may be unattained and/or there can be a positive duality gap v_P - v_D > 0. In addition, the (near) absence of a CQ results in numerical difficulties.

We study conditions that guarantee a finite positive duality gap ∞ > v_P - v_D > 0. 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. 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. In addition, we illustrate the close relation between strict complementarity and duality gaps.

In collaboration with Simon Schurr and Levent Tuncel.