Closing Duality Gaps of SDPs through Perturbation

arXiv2304.04433MaRDI QIDQ6432604FDOQ6432604

Authors: Takashi Tsuchiya, Bruno F. Lourenço, Masakazu Muramatsu, Takayuki Okuno

Publication date: 10 April 2023

Abstract: Let

be a primal-dual pair of SDPs with a nonzero finite duality gap. Under such circumstances,

and

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 and , where and are the optimal values of and 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 and with domain $[0, p i / 2]$ under the assumption that both and have singularity degree one. The domain $[0, p i / 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.

This page was built for publication: Closing Duality Gaps of SDPs through Perturbation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6432604)