"Rank 1" type constraint $X=vw^\top$: MILP representation? Convex relaxation? Other tractable approach?

Question

Suppose $X\in\mathbb{R}^{m\times n}$, $v\in\mathbb{R}^m$, $w\in\mathbb{R}^n$ are variables from an optimization problem, which also includes the constraints: $$0\le v\le a$$ $$0\le w\le 1$$ $$w_1+\dots+w_n=b$$ $$X=vw^\top$$ where $a$ and $b$ are known constants with $0\le a$ and $0\le b\le n$.

The final constraint is non-linear, and non-convex.

Does it have a MILP (or similar) representation?

If not, what is the tightest relaxation of this constraint that is globally solvable by standard methods (SDP, SOCP, MIQP, etc.)?

Note 1: The LMIRANK solver can find solutions to rank constrained feasibility problems, but it requires the matrix with the rank constraint to be symmetric and positive definite. My matrix $X$ is not even square.

Note 2: If $b$ is integer and we add the additional constraint that $w_1,\dots,w_n\in\{0,1\}$, then the problem has a MILP representation (given by replacing the final constraint with the constraints: $0\le X_{i,j}\le v_i$, $0\le X_{i,j}\le a w_j$, $X_{i,1}+\dots+X_{i,n}=v_i b$ for $i\in\{1,\dots,m\},j\in\{1,\dots,n\}$).

It seems strange that adding binary constraints could actually make this problem easier, which is what leads me to suspect there must be a tractable approach to the original problem.

Answer 1

Rank-one constraints are unfortunately not mixed-integer convex representable, as shown in this paper: Mixed Integer Convex Representability, although they are quadratically-constrained quadratic representable.

If the problem size is not too large, you can try solving it using Gurobi, either directly (for n<=10) or via branch-and-cut (for say n<=50; see Mixed Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints). At a larger size, your best bet would be to either solve the semidefinite (actually, completely positive which relaxes to doubly non-negative in this case) relaxation and round, or use a heuristic such as alternating minimization.

I agree that at first glance introducing binaries should make the problem harder rather than easier, but we have actually recently shown that low-rank problems belong to a different (and probably harder) complexity class than MIO (see section 2 of Mixed Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints), so it maybe shouldn't be too surprising that introducing binaries makes the problem easier.