Closing Duality Gaps of SDPs through Perturbation

Abstract

Let $(\mathbf{P},\mathbf{D})$ be a primal-dual pair of SDPs with a nonzero finite duality gap. Under such circumstances, $\mathbf{P}$ and $\mathbf{D}$ are weakly feasible and if we perturb the problem data to recover strong feasibility, the (common) optimal value function $v$ as a function of the perturbation is not well-defined at zero (unperturbed data) since there are ``two different optimal values'' $v(\mathbf{P})$ and $v(\mathbf{D})$, where $v(\mathbf{P})$ and $v(\mathbf{D})$ are the optimal values of $\mathbf{P}$ and $\mathbf{D}$ respectively. Thus, continuity of $v$ is lost at zero though $v$ is continuous elsewhere. Nevertheless, we show that a limiting version $v_a$ of $v$ is a well-defined monotone decreasing continuous bijective function connecting $v(\mathbf{P})$ and $v(\mathbf{D})$ with domain $[0,\pi /2]$ under the assumption that both $\mathbf{P}$ and $\mathbf{D}$ have singularity degree one. The domain $[0,\pi /2]$ corresponds to directions of perturbation defined in a certain manner. Thus, $v_a$ ``completely fills'' the nonzero duality gap under a mild regularity condition. Our result is tight in that there exists an instance with singularity degree two for which $v_a$ is not continuous.

26 pages. Comments welcome