4
$\begingroup$

Hi I have the following problem. Let the symmetric matrix M of the form: \begin{bmatrix} A & B \newline B^T & C \newline \end{bmatrix}

We have that $C$ is positive semidefinite. Is there a way to transform the constraint $A-BC^{-1}B^T \leq 0$ to a constraint using matrix $M$?

I know that in case the constraint was $A-BC^{-1}B^T \geq 0$ the answer is $M \geq 0$. But can we say something similar for the negative definite constraint? (I have already checked that $A-BC^{-1}B^T \leq 0 \Leftrightarrow M \leq 0$ Does not hold.) Is there another way to transform this constraint to a linear over the matrix B?

Thank you very much!

$\endgroup$
3
  • $\begingroup$ Just to be clear, you want to find a matrix $M$ (linearly dependent on $B$), so that $M \ge 0$ iff $A-BC^{-1}B^{T} \leq 0$, right? $\endgroup$ Aug 21, 2011 at 21:07
  • $\begingroup$ Which is the motivation of that specific constraint? $\endgroup$
    – Qfwfq
    Aug 21, 2011 at 23:17
  • $\begingroup$ The motivation is to turn this problem into a semidefinite programming problem. This is a standard construction in SDP. $\endgroup$ Aug 23, 2011 at 4:49

3 Answers 3

7
$\begingroup$

$M$ is congruent to ${\rm diag}(A-BC^{-1}B^T,C)$. Therefore the condition $A-BC^{-1}B^T\le0$ amounts to saying that the maximal dimension of positive subspace is the size $p$ of $C$.If $A-BC^{-1}B^T<0$, this is saying that the signature of $M$ is $(p,0,q)$, where $q$ is the size of $A$.

$\endgroup$
2
  • $\begingroup$ Hi Dennis, thank for the answer! I understood your answer. That is: you say that the condition $A−BC^{-1}B^T \leq 0$ is equivalent as saying that $M$ has at maximum $p$ positive eigenvalues. Yet, can I write this down as a convex constraint? My variable is matrix $B$. Thank you very much! $\endgroup$
    – Kostas
    Aug 21, 2011 at 17:18
  • 1
    $\begingroup$ @Kostas. Btw, my first name contains only one N. This is the french spelling. $\endgroup$ Feb 20, 2018 at 12:20
4
$\begingroup$

Its not completely clear what you are asking: what does it mean to "transform this constraint to a linear over the matrix B?" But perhaps it will be helpful to note that the set of matrices of your form satisfying $$C \geq 0, ~~A - B C^{-1} B^T \leq 0$$ is not convex: just consider what happens when you take the average of two $2 \times 2$ matrices, one with $A=2,C=1/2,B=1$ and the other with $A=1/2, C=2, B=1$. So it is impossible to express these two constraints in terms of linear inequalities on matrices $A,B,C,D$.

$\endgroup$
1
  • $\begingroup$ Yep, you've got to give up on $C\geq 0$. $\endgroup$ Aug 23, 2011 at 4:50
1
$\begingroup$

No, that's not quite the generalization that you'll get when you extend the Schur complement theorem for positive definite matrices to negative definite matrices. Try using the fact that a matrix $X$ is negative definite if and only if $-X$ is positive definite and then follow the sign changes through- you'll end up with a slightly different $M$ matrix.

$\endgroup$
2
  • $\begingroup$ Hi Brian, thank you for your answer! I tried to do what you proposed, but I havent managed to work it out. You say that: $A+BC^{-1}B^T \leq 0 \Leftrightarrow -A+BC^{-1}B^T \geq 0$. But then how can I continue? I want to get a matrix inequality that is linear on the matrix $B$. Even if I assume that $A \geq 0$ then I get a matrix $M$ that is not not linear on B. $\endgroup$
    – Kostas
    Aug 21, 2011 at 17:38
  • $\begingroup$ No, I didn't say that. You've made a sign change error in what you wrote: $A-BC^{-1}B^{T} \leq 0$ iff $-A+BC^{-1}B^{T} \geq 0$. The signs on both terms have to change. $\endgroup$ Aug 21, 2011 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.