Subtracting Values from a Positive semidefinite Matrix in a Semidefinite Program

Question

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.

Answer 1

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