Width of an ellipsoid

Question

This is from chapter 9 of Convex Optimization by Boyd & Vandenberghe. They have $$\mathcal E = \left\{ x \mid (x-x_0)^T A^{-1} (x-x_0) \le 1 \right\}$$ and they define the width in the direction $q$ as $$ \sup q^T z - \inf q^T z = (\|A^{1/2} q\|_2 + q^T x_0) - (-\|A^{1/2} q\|_2 +q^T x_0)$$ Where the sup and inf are taken over $z \in \mathcal E$. How did they establish those expressions for the supremum and the infimum?

Answer 1

$q^Tz=\text{const}$ is a hyperplane with the vector $q$ being a normal. Then $\sup q^Tz$ corresponds to the largest possible constant, that is the largest possible move of the hyperplane along $q$ so that it still has a contact with $\cal E$. What you get is a maximal supporting hyperplane. Similraly, $\inf q^Tz$ corresponds to the minimal supporting hyperplane. Thus, the difference can be quantified as a measure for the width of the ellipoid in this direction.

P.S. I guess that the direction $q$ should be normalized.

P.P.S. I think I misunderstood the question. To get the expression for the $\sup$ and $\inf$ you just have to optimize $q^Tx$ over $x\in\cal{E}$. The optimum is where the gradient of the function $q^Tx$ is parallel to the gradient of the equality constraint (the boundary of the ellipsoid), i.e. $$ A^{-1}(x-x_0)=\lambda q\quad\Leftrightarrow\quad x-x_0=\lambda Aq. $$ Substitute to the constraint $$ 1=(x-x_0)^TA^{-1}(x-x_0)=\lambda^2q^TAq=\lambda^2\|A^{1/2}q\|^2\quad\Leftrightarrow\quad\lambda=\pm\frac{1}{\|A^{1/2}q\|}. $$ Now calculate the optimum $$ q^Tx_{opt}=q^T(x_0\pm\frac{1}{\|A^{1/2}q\|}Aq)=q^Tx_0\pm\frac{\|A^{1/2}q\|^2}{\|A^{1/2}q\|}=q^Tx_0\pm\|A^{1/2}q\|. $$ The plus sign corresponds to $\sup$ and the minus to $\inf$.