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

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.

• Gurobi can handle non-convex quadratic constraints. Maybe worth a try. Dec 16 '20 at 15:16
• Wow. I'm out of date with their features. Do you have any practical experience with it? Will the non-binary problem be easier or harder than the binary one?
– cfp
Dec 16 '20 at 16:01
• I would guess binary+linear is faster. But I am about 50% correct in my predictions.... Dec 16 '20 at 17:46

## 1 Answer

Rank-one constraints are unfortunately not mixed-integer convex representable, as shown in this paper: https://arxiv.org/abs/1706.05135, 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 https://arxiv.org/abs/2009.10395). 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 https://arxiv.org/abs/2009.10395), so it maybe shouldn't be too surprising that introducing binaries makes the problem easier.