Tightness of the strengthened SDP relaxation in dimension two

About 6 years old · traced to

Let F:={x∈R2:∥x∥≤1, ∥x∥≤bTx}\mathcal{F}:= \{x \in \mathbb{R}^2: \|x\| \leq 1,\ \|x\| \leq b^T x\} be the two-dimensional feasible space, where b∈R2b \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

Rshor∩Rksoc∩Rcuts\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 b∈R2b \in \mathbb{R}^2 is not established in the supplied source.

References

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.