2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Which chapter of the book? $\endgroup$ Jul 23, 2022 at 11:01

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .