0
$\begingroup$

I am working on a binary optimization problem. So far I have derived the following constraint functions. \begin{align} \begin{bmatrix} \left( P + \sum_{i=1}^n (\sum_{j=1}^n x_{i, j} \alpha_j) e_i e_i^T \right) A \left( P + \sum_{i=1}^n (\sum_{j=1}^n x_{i, j} \alpha_j) e_i e_i^T \right) & v \\ v^T & t \end{bmatrix} \succeq 0 \end{align} , where the optimization variables are $x_{i, j} \in \{0, 1\}$. $P$ and $A$ are given positive definite symmetric matrices, $v$ is a vector, and $\alpha$, $t$ are constants.

The quadratic matrix inequality seems to be non-convex in general, so cvx solvers cannot directly accept it. I am not sure whether it is still non-convex when the domain is real numbers between 0 and 1. I have attempted to solve the problem through semidefinite relaxation. However, since the problem is not homogeneous quadratic (there are linear terms), the solution quality turned out to be poor. I am looking for any optimization techniques that may help solving this problem. Thanks for any suggestion in advance.

Improve this question
$\endgroup$
4
  • $\begingroup$ This appears to be a binary Bilinear Matrix Inequality. The biliinear terms can be "linearized" because all product terms must be 0 or 1 Therefore, this can be converted to a binary Linear Semidefinite (Matrix Inequality) constraint. Presuming the objective is linear or convex quadratic, that can be (attempted to be) solved with a Mixed-Integer Linear SDP solver, such as SCIP-MISDP, or under YALMIP (using BNB + Mosek (or other Lineasr SDP solver), ,or cutsdp + MILP solver). Whether it can actually be solved within a time and memory budget is another matter. $\endgroup$
    – Mark L. Stone
    Commented Oct 28 at 12:18
  • $\begingroup$ Thanks. I will survey the above-mentioned solvers and see if there are further questions. $\endgroup$
    – zycai
    Commented Oct 29 at 3:56
  • $\begingroup$ Hi Mark, if the problem is in the complex positive semidefinite Hermitian matrix domain, can these integer solvers still accept it? Thanks. $\endgroup$
    – zycai
    Commented Nov 12 at 5:46
  • $\begingroup$ Most solvers work in the real domain. However, a problem in the complex domain can be converted to real. Modeling fron ends to (convex optimization tools such as CVX, CVXPY, CVXR, Mosek and others accept problems in the complex domain and do the necessary conversion to real under the hood before calling the solver. These tools allow declaration of a matrix as hermitian, or hermitian semidefinite. $\endgroup$
    – Mark L. Stone
    Commented Nov 12 at 13:21

1 Answer 1

Reset to default
0
$\begingroup$

As is, this is a binary Bilinear Matrix Inequality (BMI), which can be very difficult to solve to global optimality.

However, he bilinear (quadratic) terms can be linearized. The resulting Binary (Mixed-Integer) Linear Semidefinite Programming (MISDP) problem can be solved using a Linear MISDP solver (which still might be difficult to solve, depending on the problem dimension, among other things).

Details (for notational simplicity, shown with single rather than double indices):

Each square term, $x_i^2$ can be replaced by $x_i$ due to $x_i$ being 0 or 1.

Each bilinear term $x_ix_j$ can be replaced by a new binary (zero or one) variable $b_{ij}$, with the addition of the constraints $b_{ij} \le x_i, b_{ij} \le x_j, b_{ij} \ge x_i + x_j -1$, which together ensure $b_{ij} = 1$ iff $x_i = x_j = 1$.

That converts this to a Mixed-Integer Linear SDP (presuming objective and any other constraints are compatible with an MISDP, such as convex quadratic objective, and linear, convex quadratic, Second Order Cone, and Linear SDP constraints).

SCIP-SDP will accept such a problem, and can solve it given enough time and memory.

YALMIP can accept such a problem, and can solve it given enough time and memory, using either:

  1. BNB + (continuous) Linear SDP solver (such as Mosek, SeDuMi, SDPT3
  2. CUTSDP + MILP solver (such as Gurobi, Xpress, INTLINPROG, SCIP, and many others).
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .