In page 6 of the paper A semidefinite programming method for integer convex quadratic minimization, it is stated that the following maximization problem

\begin{align} \text{maximize} & \quad -\left(q + \frac{1}{2}\lambda \right)^\top \left(P - \text{diag}(\lambda)\right)^\dagger \left(q + \frac{1}{2}\lambda \right)\\ \text{subject to} & \quad P - \text{diag}(\lambda) \succeq 0 , \\ & \quad q + \frac{1}{2}\lambda \in \mathcal{R}(P - \text{diag}(\lambda)) \\ & \quad \lambda \geq 0 \end{align} is equivalent to \begin{align} \text{maximize} & \quad -\gamma \\ \text{subject to} & \quad \begin{bmatrix} P - \text{diag}(\lambda) & q + \frac{1}{2}\lambda \\ \left(q + \frac{1}{2}\lambda \right)^\top & \gamma \end{bmatrix} \succeq 0 \\ & \quad \lambda \geq 0, \end{align} where $P \in \mathbb{R}^{n\times n}$ symmetric, $q \in \mathbb{R}^n$, $\lambda \in \mathbb{R}^n$, $\gamma \in \mathbb{R}$, $A^\dagger$ is the Moore-Penrose inverse of the matrix $A$, diag($\lambda$) is the diagonal matrix with $\lambda$ in the main diagonal, $A\succeq 0$ means that $A$ is positive semi-definite, $\lambda \geq 0$ means that all the components of $\lambda$ are non-negative and $b \in \mathcal{R}(A)$ means that $b$ is in the range space of $A$.

I understand how we can use Schur complements to reformulate the SDP. However, the point I do not understand is why we can drop the range space constraint $q + \frac{1}{2}\lambda \in \mathcal{R}(P - \text{diag}(\lambda))$? I do not see how this constraint is enforced in the reformulation.

  • $\begingroup$ Do you understand how $\gamma$ ties into the second equation, making it equivalent to the original objective? It looks like the (2,2) element should be just (incorrectly) $0$, not $0 + \gamma$, but I don't understand why yet. I've asked a similar question here math.stackexchange.com/questions/4836819/… $\endgroup$ Jan 2 at 12:17

1 Answer 1


It has not been dropped. It is implicit in the Schur complement being applicable here in this non-strict case. If the condition does not hold, the lower matrix inequality cannot hold.


You must log in to answer this question.

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