Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading Boyd's Convex Optimization book and I am stuck on the reasoning behind one of the statements. Specifically, I am looking at page 45, line 3 from the bottom. The statement is:

$A \preceq B \iff \mathcal{E}_A \subseteq \mathcal{E}_B$.

Note that I interpret $A \preceq B$ to mean $B-A \subset \mathbf{S}^n_+$.

Here is my attempt at going from left to right:

$B-A \subset \mathbf{S}^n_+ \Rightarrow x^T (B - A) x \geq 0$

$x^T (B - A) x \geq 0 \Rightarrow x^T B x - x^T A x \geq 0$

$x^T B x - x^T A x \geq 0 \Rightarrow x^T B B^{-1} B x - x^T A A^{-1} A x \geq 0$

$x^T B B^{-1} B x - x^T A A^{-1} A x \geq 0 \Rightarrow z^T B^{-1} z - y^T A^{-1} y \geq 0$ (eq: 1)

So here I get stuck because I'm not exactly sure how this implies ellipsoid A is a subset of ellipsoid B.

My attempt from going right to left got stuck because

$\mathcal{E}_A \subseteq \mathcal{E}_B \iff (x \in \{y \mid y^T A^{-1} y \leq 1\} \Rightarrow x \in \{y \mid y^T B^{-1} y \leq 1\})$

I made the assumption the following was true (for circles this makes some sense):

$(x \in \{y \mid y^T A^{-1} y \leq 1 \} \Rightarrow x \in \{y \mid y^T B^{-1} y \leq 1\}) \Rightarrow x^T A^{-1} x \leq x^T B^{-1} x$

Note that after some algebraic manipulations, I reach point (eq: 1).

Any help on how to represent ellipsoid A is a subset of ellipsoid B in matrix form? And also how do I work past (eq: 1)?

Thanks.

share|improve this question
    
What is your definition of the "ellipsoid of A"? What you wrote above is missing something, do you mean $\{y|y^TA^{-1}y = 1\}$ instead? –  Willie Wong Mar 12 '11 at 2:21
    
The ellipsoids involved in this problem are defined as: $\mathcal{E}_A = \{y \mid y^T A^{-1} y \leq 1\}$. So the ellipsoid will contain all points on the boundary as well as the interior. –  jrand Mar 12 '11 at 2:28

1 Answer 1

up vote 2 down vote accepted

I'm going to assume that $0 \preceq A$, that is, that $A$ is itself positive semidefinite, as the result fails for more general $A$ (and the thing defined as the "ellipsoid" of $A$ is not a geometrical ellipsoid; e.g. if $A$ is the diagonal $2 \times 2$ matrix with diagonal $(-1, 0)$ and $B$ is the $2 \times 2$ identity matrix, we do have $A \preceq B$ in the sense that $B - A$ is positive semidefinite, but the "ellipsoid" of $A$ is an unbounded set whose boundary is the hyperbola $\{(x,y) \in \mathbb{R}^2: y^2 - x^2 = 1\}$ and this is not contained in the ellipsoid of $B$, aka the unit disc in $\mathbb{R}^2$).

Once we assume that $A$ is positive semidefinite it follows from $A \preceq B$ that $B = (B-A) + A$ is also positive semidefinite (since a sum of PSD matrices is PSD).

Since the definition of ellipsoid involves the inverse we should also assume that $A$ is invertible (and this implies that $B$ is--- e.g. because it implies the existence of a positive number $c$ with $cI \preceq A$ and transitivity of $\preceq$ implies then that $cI \preceq B$).

Now it is well known (but nontrivial) that $0 \preceq A \preceq B$ and $A$ invertible together imply that $0 \preceq B^{-1} \preceq A^{-1}$. [The easiest way to prove this depends sensitively on how "positive semidefinite" is defined, and there are various approaches to this. A functional analysis book, for example, would define the concept in a way that does not reference eigenvalues, since the notion makes perfectly good sense for operators that don't have any.] Look it up your favorite reference or find a proof that you like online.

Anyhow: once you know the given hypotheses imply that $B^{-1} \preceq A^{-1}$ it is simple. For any vector $x$ you have from this operator relation that $x^t (A^{-1} - B^{-1}) x \geq 0$, which implies (by expanding the matrix product and moving one term over to the other side) that for any $x$ $$ x^t A^{-1} x \geq x^t B^{-1} x; $$ thus if the left hand side is $\leq 1$, so is the right hand side, thus the ellipsoid of $A$ is contained in that of $B$.

For the converse: if it is not the case that $A \preceq B$ (under the standing hypotheses that $A, B$ are both PSD and invertible) then it cannot be the case that $B^{-1} \preceq A^{-1}$ (or we could deduce from this that $A \preceq B$ by the well known but nontrivial fact I mentioned earlier, with the roles of $A$ and $B$ now played by $B^{-1}$ and $A^{-1}$), so there must be a vector $x_0$ with $x_0^t(A^{-1} - B^{-1}) x_0 < 0$, and for this vector we have $$ x_0^t B^{-1} x_0 > x_0^t A^{-1} x_0. $$ Since $A^{-1}$ is invertible, the right hand side must be positive, so by scaling $x_0$ as necessary we can make the right hand side equal to $1$. The inequality then shows us that the vector $x_0$ is in the ellipsoid of $A$, but not in that of $B$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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