Let \(({\bf P},{\bf D})\) be a primal-dual pair of SDPs with a nonzero finite duality gap. Under such circumstances, \({\bf P}\) and \({\bf 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({\bf P})\) and \(v({\bf D})\), where \(v({\bf P})\) and \(v({\bf D})\) are the optimal values of \({\bf P}\) and \({\bf 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({\bf P})\) and \(v({\bf D})\) with domain \([0, \pi/2]\) under the assumption that both \({\bf P}\) and \({\bf 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.
Closing Duality Gaps of SDPs through Perturbation
\(\)