# Subtracting Values from a Positive semidefinite Matrix in a Semidefinite Program

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.

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