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$ – Erwin Kalvelagen 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$ – Erwin Kalvelagen Dec 16 '20 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.