Conjecture on active complementarity in the Beta relaxation

At least 2 years old · documented by

Let \scBeta\text{\sc Beta} denote the convex relaxation of the ball-constrained nonconvex quadratic program defined in the paper, with matrix variable WW and vectors ℓ1,ℓ2\ell_1,\ell_2 as above. The relaxation includes the constraint ℓ1TWℓ2≥0\ell_1^T W\ell_2\geq 0. Active-complementarity conjecture. There exists an optimal solution W∗W^* of \scBeta\text{\sc Beta} with

ℓ1TW∗ℓ2=0.\ell_1^T W^*\ell_2=0.

The conjecture is motivated by extensive computational experiments in which the constraint was active at optimality for every tested instance. It would explain why the strengthened relaxation with ℓ1TWℓ2=0\ell_1^T W\ell_2=0 continues to solve the tested instances, although no general proof is given here.

References

Primary source

Samuel Burer, “A Slightly Lifted Convex Relaxation for Nonconvex Quadratic Programming with Ball Constraints”, arXiv:2303.01624 (2023).

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.