What is the condition number of an ellipsoid?

260 Views Asked by At

I would like to know how to calculate the condition number of an ellipsoid. In Boyd & Vandenberghe's Convex Optimization, it is calculated as follows.

$$ \mathcal{E} = \left\{ x \mid (x-x_0)^T A^{-1} (x-x_0) \leq 1 \right\} $$

where $ A \in \mathbf{S}^n_{++}$. The width of $q$ is

$$ \begin{split} \sup_{z \in \mathcal{E}} q^Tz - \inf_{z \in \mathcal{E}} q^T z &= \left(\lVert A^{1/2}q\rVert_2 + q^T x_0\right) - \left(-\lVert A^{1/2}q\rVert_2 + q^T x_0\right)\\ &= 2\lVert A^{1/2}q\rVert_2 \end{split} $$

but I don't quite understand how I can express the $\sup_{z \in \mathcal{E}} q^Tz$ like the upper equation.

and because I don't quite undestand the above equation I can not understand the rest of that $$ W_{\min} = 2\lambda_{\min}(A)^{1/2}, \quad W_{\max}=2 \lambda(A)^{1/2} \Rightarrow \mathbf{cond}(\mathcal{E}) = \frac{\lambda_{\max}}{\lambda_{\min}}= \kappa(A) $$ where $\kappa(A)$ denotes the condition number of the matrix $A$.

1

There are 1 best solutions below

0
On

This question is about Example 9.1 in Chapter 9 (page 461).

The idea here is something like the following:

Using an alternate parameterization of the ellipse, $ \mathcal{\epsilon} = \{x_{0} + A^{1/2}u | \left\lVert u \right\rVert_{2} \leq 1 \}$ (page 30), $\text{sup}_{z \in \mathcal{\epsilon}} q^{T}z$ can be expressed as \begin{align} &\max_{u} q^{T}x_{0} + q^{T}A^{1/2}u \\ &\text{ subject to } \left\lVert u \right\rVert_{2} \leq 1 \end{align}

Observe that $q^{T}x_{0}$ is a constant so we just need to compute

\begin{align} &\max_{u} (A^{1/2}q)^{T}u \\ &\text{ subject to } \left\lVert u \right\rVert_{2} \leq 1 \end{align}

where we used that $(A^{1/2})^{T} = A^{1/2}$ for $A \in \mathbf{S}^{n}_{++}$.

Next, let $c = A^{1/2}q$ so we are left with:

\begin{align} &\max_{u} c^{T}u \\ &\text{ subject to } \left\lVert u \right\rVert_{2} \leq 1 \end{align}

which is just maximizing a linear function over the unit ball. In particular the maximum is $\left\lVert A^{1/2}u \right\rVert_{2}$ (see here).

Thus, $\text{sup}_{z \in \mathcal{\epsilon}} q^{T}z = q^{T}x_{0} + \left\lVert A^{1/2}u \right\rVert_{2}$.