Back to Search Start Over

Closing Duality Gaps of SDPs through Perturbation

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

Abstract

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.<br />Comment: 26 pages. Comments welcome

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2304.04433
Document Type :
Working Paper