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$ Dec 16 '20 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
    Dec 16 '20 at 16:01
  • 1
    $\begingroup$ I would guess binary+linear is faster. But I am about 50% correct in my predictions.... $\endgroup$ Dec 16 '20 at 17:46
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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.