← All problems

Conjecture on active complementarity in the Beta relaxation

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
  1. 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.