# What is the condition number of an ellipsoid?

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

• Which chapter of the book? Jul 23, 2022 at 11:01

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

You can use the alternate definition for an ellipse. $$\mathcal{E} = \{x_{0} + A^{1/2}u \,|\, \left\lVert u \right\rVert_{2} \leq 1 \}$$

Let's now focus only on $$\sup_{z \in \mathcal{E}} q^\mathsf{T}z$$.

$$\begin{split} \sup_{z \in \mathcal{E}} q^\mathsf{T}z &= \sup \{ q^\mathsf{T}(x_{0}+A^{1/2}u) \,|\, \left\lVert u \right\rVert_{2} \leq 1 \}\\ &= q^\mathsf{T}x_{0}+\sup \{ q^\mathsf{T}A^{1/2}u \,|\, \left\lVert u \right\rVert_{2} \leq 1 \}\\ &= q^\mathsf{T}x_{0}+ q^\mathsf{T}A^{1/2}\frac{(q^\mathsf{T}A^{1/2})^\mathsf{T}}{\lVert q^\mathsf{T}A^{1/2} \rVert_2} \\ &= q^\mathsf{T}x_{0}+ \frac{q^\mathsf{T}A^{1/2}A^{1/2}q^\mathsf{T}}{\lVert q^\mathsf{T}A^{1/2} \rVert_2}\\ &= q^\mathsf{T}x_{0}+ \frac{\lVert q^\mathsf{T}A^{1/2} \rVert_2^2}{\lVert q^\mathsf{T}A^{1/2} \rVert_2}\\ &= q^\mathsf{T}x_{0}+ \lVert q^\mathsf{T}A^{1/2} \rVert_2 \end{split}$$

In the 3rd step, you can see that $$u$$ is transformed into $$(q^\mathsf{T}A^{1/2})^\mathsf{T}/\lVert q^\mathsf{T}A^{1/2} \rVert_2$$. The reason this happens is because in order to get a supremum, we need $$u$$ to be in the same direction as $$q^\mathsf{T}A^{1/2}$$ and saturate to the maximum value ( $$\lVert u \rVert_2 = 1$$ ), thus $$u=(q^\mathsf{T}A^{1/2})^\mathsf{T}/\lVert q^\mathsf{T}A^{1/2} \rVert_2$$.

In the case of $$\inf_{z \in \mathcal{E}} q^T z$$, for an similar reason $$u=-(q^\mathsf{T}A^{1/2})^\mathsf{T}/\lVert q^\mathsf{T}A^{1/2} \rVert_2$$, the difference is that since it's infimum, we need to go to the direction contrary to the vector $$q^\mathsf{T}A^{1/2}$$. Therefore $$\inf_{z \in \mathcal{E}} q^Tz= q^\mathsf{T}x_{0}- \lVert q^\mathsf{T}A^{1/2} \rVert_2$$.

Thus,

$$\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}$$