2
$\begingroup$

I'm trying to construct an SDP relaxation for a non-convex quadratic program ($x^{\intercal}\mathbf{H}x$) with the following objective function: \begin{equation} x_{11}y_{11} + x_{12}y_{12} + x_{21}y_{21} + x_{22}y_{22} \end{equation} Where $x_{ij} \in \{0, 1\}$ and $y_{\max} \leq y_{ij} \leq y_\min $ ($y_{ij}$ is a continuous\real decision variable)

The matrix $\mathbf{H}$ has the following values which makes it indefinite: \begin{equation} \mathbf{H} = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \end{equation}

By replacing the negative eigen values of matrix $\mathbf{H}$ with zeros and reconstructing it using the new eigen values, I got the following positive semidefinite matrix: \begin{equation} \mathbf{H} = \begin{bmatrix} 0.2500& 0& 0& 0&0.2500& 0& 0& 0\\ 0&0.2500& 0& 0& 0&0.2500& 0& 0\\ 0& 0&0.2500& 0& 0& 0&0.2500& 0\\ 0& 0& 0&0.2500& 0& 0& 0&0.2500\\ 0.2500& 0& 0& 0&0.2500& 0& 0& 0\\ 0&0.2500& 0& 0& 0&0.2500& 0& 0\\ 0& 0&0.2500& 0& 0& 0&0.2500& 0\\ 0& 0& 0&0.2500& 0& 0& 0&0.2500\\ \end{bmatrix} \end{equation}

Now here is my final objective function in SDP relaxed program that I figured out so far: \begin{equation} \mathbf{H\cdot X} - \mathbf{Tr(H\cdot X}) \end{equation}

Where: \begin{equation} \mathbf{x} = \begin{bmatrix} x_{11}\\x_{12}\\x_{21}\\x_{11}\\y_{11}\\y_{12}\\y_{21}\\y_{22} \end{bmatrix}, \mathbf{X} = \mathbf{xx^{\intercal}} \end{equation}

My questions are:

  1. Are these steps correct for constructing SDP relaxation for the non-convex quadratic program?.
  2. Is the objective function correct after subtracting the trace $\mathbf{Tr(H\cdot X)}$? because as far as I know the objective function must be either positive definite or positive semedefinite.
  3. I know that there is a linearization technique that can solve the problem but I'm trying to find how this can be solved using SDP.
$\endgroup$
1
2
$\begingroup$

It is not the best option to regard it as a non-convex QP. A product of a binary variable and a continuous variable is not really bilinear (or non-linear). For example, the nonlinear constraint $$ z_{ij} \geq x_{ij}y_{ij} $$ could be replaced with $$ z_{ij} \geq y_{ij} - y_{\max}(1-x_{ij})\\ z_{ij} \geq y_{\min}x_{ij} $$ (the RHS of the second line could be $0$ if $y_{\min}\geq 0$).

$\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.