# "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