SIAM Optimization

Boston Park Plaza Hotel and Towers, May 10-13, 2008.

Title of presentation:

Strong duality and stability in conic convex programming
(with Simon Schurr and Levent Tuncel)

talk (pdf file)


For nonlinear (minimization) optimization problems with optimal value $v_P$, {\em weak duality} holds in general, i.e. the optimal value of the Lagrangian dual provides a lower bound, $v_D \leq v_P$. However, {\em strong duality} (i.e. $v_D = v_P$ and $v_D$ is attained) requires a {\em 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 $\infty > 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. Numerical tests are included. 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.

Related References: