SDP relaxation of mixed-integer nonlinear program

50 Views Asked by At

I am having trouble understanding the semidefinite programming (SDP) relaxation of a mixed-integer nonlinear program (MINLP) from section 3 of this paper. The optimization problem in MINLP form is

\begin{align} \min_{x, y}{x^\intercal Qx}\\ \text{s.t. } \mu^\intercal x \geq \rho,\\ e^\intercal x \leq 1,\\ e^\intercal y \geq n - \aleph,\\ x_iy_i = 0,\ \forall\ i \in [n],\\ y_i \in \{0,1\},\\ 0 \leq x_i \leq u_i,\ \forall\ i \in [n] \end{align}

where $x, \mu \in \mathbb{R}^n$, $Q \in \mathbb{R}^{n \times n}$, $e$ is an $n$-dimensional vector of all 1's, $\rho \in \mathbb{R}$, and $\aleph \in \mathbb{N}$.

The authors relax this as an SDP, where they rewrite the objective function as $x^\intercal Q x = \langle{x, Qx}\rangle = \langle{Q, xx^\intercal}\rangle$ and introduce matrices $X \succcurlyeq xx^\intercal$ and $Y \succcurlyeq yy^\intercal$. Finally, using the Schur complement, they claim

$$ X \succcurlyeq xx^\intercal, Y \succcurlyeq yy^\intercal \iff \exists\ Z \in \mathcal{S}^n \text{ s.t. } \overline{X} \succcurlyeq 0, $$

where

$$ \overline{X} = \begin{pmatrix} 1 & x^\intercal & y^\intercal\\ x & X & Z\\ y & Z^\intercal & Y \end{pmatrix} $$

This then, somehow, leads to the following SDP relaxation of the above MINLP:

\begin{align} \min_{\overline{X}}{\langle{Q, X}\rangle}\\ \text{s.t. } \mu^\intercal x \geq \rho,\\ e^\intercal x \leq 1,\\ e^\intercal y \geq n - \aleph,\\ \text{diag}(Z) = \mathbf{0},\\ \text{diag}(Y) = y\\ 0 \leq x_i \leq u_i,\ \forall\ i \in [n],\\ \overline{X} \succcurlyeq 0. \end{align}

I can reproduce this result only if we don't do the relaxation of $X \succcurlyeq xx^\intercal$ and $Y \succcurlyeq yy^\intercal$, but instead have $X = xx^\intercal, Y = yy^\intercal$, and also have $Z = xy^\intercal$, which would violate their claim of $Z$ being symmetric.

Am I missing something, or is this paper wrong?

1

There are 1 best solutions below

0
On

You are right, this is a mistake in the paper. Matrix $Z$ is not symmetric.