0
$\begingroup$

Assume $A \in \textbf{S}^n_{++}$, an ellipsoid centered at the origin given by

$$\mathcal{E}_A = \{x\mid x^TA^{-1}x \leq 1\}$$

Then we have $\mathcal{E}_A \subseteq \mathcal{E}_B $ if and only if $B-A \succeq 0$.

This is the proposition in the Boyd & Vandenberghe's Convex Optimization (pages 45-46). The authors gave only the result, without proof. How to prove it?

Boyd and Vandenberghe, Convex Optimization, Page 45-46

$\endgroup$
2

1 Answer 1

2
$\begingroup$

Assume $\varepsilon_A = \{ x \mid x^T A^{-1}x \le 1 \} $ is the set of points that comprise the inner ellipsoid and $\varepsilon_B = \{ x |\; x^T B^{-1}x \le 1 \} $ be the set of points comprising the outer ellipsoid and the two ellipsoid are distinct. Since $B-A \succeq 0$ is a PSD and since both $A,B$ have inverses $A^{-1}$ and $B^{-1}$ (the inverses exist) we can say

$$B-A \succeq 0 \Rightarrow I-B^{-1}A\succeq 0 \Rightarrow A^{-1}-B^{-1}\succeq 0$$

therefore $A^{-1}-B^{-1}$ is PSD and we can conclude that for every $x$ we have $x^T(A^{-1}-B^{-1})x\ge 0 \Rightarrow x^TA^{-1}x\ge x^TB^{-1}x $. This means that $\forall x\in \varepsilon_A : 1\ge x^TA^{-1}x \ge x^TB^{-1}x \Rightarrow x\in \varepsilon_B$.

Conversely assume $\forall x\in \varepsilon_A \Rightarrow x\in \varepsilon_B$ and assume that instead $A-B \succeq 0$ (contradiction assumption), which with a similar reasoning gives us $\forall x\in \varepsilon_B \Rightarrow x\in \varepsilon_A$ which states that both ellipsoids are the same and equivalent which is a contradiction (since we assumed they are distinct) and therefore the result follows.

$\endgroup$
7
  • $\begingroup$ Thanks for answer. I can't understand why $B-A \succeq 0 \Rightarrow I-B^{-1}A\succeq 0 \Rightarrow A^{-1}-B^{-1}\succeq 0$. Can you give detailed proof about it? Since the multiplication of two PSD matrix isn't PSD all the time. $\endgroup$
    – wz0919
    Commented Aug 1, 2020 at 2:06
  • $\begingroup$ Why positive semi-definite, $A,B \in \textbf{S}^n_{++}$, they are positive-definite and the product of two positive-definite is positive-definite (using Cholesky, $A = LL^H$ thus $AB = LL^HB = L (L^HBL)L^{-1}$ and therefore $AB$ is similar to $L^HBL$ and positive definite). Also if $A$ is PD then $A^{-1}$ is also PD. $$B \succeq A \Rightarrow I \succeq B^{-1}A \Rightarrow A^{-1} \succeq B^{-1}$$ $\endgroup$ Commented Aug 1, 2020 at 8:04
  • $\begingroup$ I get your point. But since $I - B^{-1}A$ isn't symmetric, maybe using eigenvalues is more rigid? $ B-A \succeq 0$ and $ B \succ 0 $ we can get eigenvalues of $ I - B^{-1}A $ are nonnegative, Similarly eigenvalues of $ A^{-1} - B^{-1} $ are nonnegative. Combine with $ A^{-1} - B^{-1} $ is Hermitian then PSD. $\endgroup$
    – wz0919
    Commented Aug 2, 2020 at 2:36
  • $\begingroup$ Yes you are right, I did not notice $B^{-1}A$ is not symmetric therefore we can't conclude the result. It's actually the generalization of simple inequality $a>b>0 \Rightarrow \frac{1}{b}>\frac{1}{a}>0$ to generalized matrix inequality but it's not a trivial task at all and you need solid functional analysis which is above my pay grade, but if you get that result as a prove fact, then the rest follows. If you want I delete the answer and all comments will be removed too, just tell me to remove it and sorry for disappointment. $\endgroup$ Commented Aug 2, 2020 at 17:26
  • 1
    $\begingroup$ No your answer is very inspiring and this fact is completely right. I found the proof here. By this I believe the answer can be perfect. If you like you can add this to your answer and I will accept it. $\endgroup$
    – wz0919
    Commented Aug 3, 2020 at 3:29

You must log in to answer this question.

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