How to prove $B-A \succeq 0 \Leftrightarrow$ ellipsoid $x^TBx \leq 1$ contains $x^TAx \leq 1$?

299 Views Asked by At

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

1

There are 1 best solutions below

7
On

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.