3
$\begingroup$

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.

  • 0
    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.2011-03-12

1 Answers 1

4

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$.

  • 0
    Is there a way to check if $\mathcal{E}_A \subseteq \mathcal{E}_B$ when $\mathcal{E}_A, \mathcal{E}_B$ are not centered at the origin?2018-08-14