2
$\begingroup$

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.

$\endgroup$
1
  • $\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

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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