3
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ Gurobi can handle non-convex quadratic constraints. Maybe worth a try. $\endgroup$ Commented Dec 16, 2020 at 15:16
  • $\begingroup$ 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? $\endgroup$
    – cfp
    Commented Dec 16, 2020 at 16:01
  • 1
    $\begingroup$ I would guess binary+linear is faster. But I am about 50% correct in my predictions.... $\endgroup$ Commented Dec 16, 2020 at 17:46

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.