Tightness of the strengthened SDP relaxation in dimension two

Let F:={xR2:x1, xbTx}\mathcal{F}:= \{x \in \mathbb{R}^2: \|x\| \leq 1,\ \|x\| \leq b^T x\} be the two-dimensional feasible space, where bR2b \in \mathbb{R}^2 is arbitrary. Let G\mathcal{G} denote the convex hull defined in the source, and let Rshor\mathcal{R}_{\mathrm{shor}}, Rksoc\mathcal{R}_{\mathrm{ksoc}}, and Rcuts\mathcal{R}_{\mathrm{cuts}} denote the stated relaxations and cuts.

Tightness conjecture. The intersection

RshorRksocRcuts\mathcal{R}_{\mathrm{shor}} \cap \mathcal{R}_{\mathrm{ksoc}} \cap \mathcal{R}_{\mathrm{cuts}}

equals G\mathcal{G}.

The conjecture is motivated by computational experiments in dimension two, in which the relaxation was exact on nearly all tested instances and the added cuts closed the remaining gaps. Its general validity for arbitrary bR2b \in \mathbb{R}^2 is not established in the supplied source.

Sources & referencesView supporting material

Primary source

Anders Eltved and Samuel Burer, “Strengthened SDP Relaxation for an Extended Trust Region Subproblem with an Application to Optimal Power Flow”, arXiv:2009.12704 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.