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)
Abstract
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: