Maximum inscribed sphere inside ellipse and minimum circumscribed sphere containing ellipse

Question

Consider the following function $$ f(x) = \frac{1}{2}x^{\text{T}}Qx + c^{\text{T}}x, $$ where $Q$ is a real symmetric positive definite $n \times n$ matrix and $c \in \mathbb{R}^{n}$. The ellipse contour of $f$ with level $a \in \mathbb{R}$ can be expressed as $$ E(a) := \{x \in \mathbb{R}^{n} \mid f(x) = a\}. $$ The center of $E(a)$ is given by $\hat{x} = -Q^{-1}c$. The function can be now rewritten as

$$ f(x) = \frac{1}{2}(x - \hat{x})^{\text{T}}Q(x - \hat{x}) - \frac{1}{2}c^{\text{T}}Q^{-1}c. $$

Denote by $S_{\text{ins}}$ the maximum inscribed sphere inside $E(a)$ and $S_{\text{circ}}$ the minimum circumscribed sphere containing $E(a)$. I want to determine the radii $r_{\text{ins}}$ and $r_{\text{circ}}$ of $S_{\text{ins}}$ and $S_{\text{circ}}$, respectively.

Suppose the eigenvalues of $Q$ are ranked in an ascending order, i.e., $$ 0 < \lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n. $$

In the paper, they said the radius are given by $$ r_{\text{ins}} = \sqrt{\frac{2(a-t)}{\lambda_n}} $$ and $$ r_{\text{circ}} = \sqrt{\frac{2(a-t)}{\lambda_1}}, $$ where $t = - \frac{1}{2}c^{\text{T}}Q^{-1}c$. But they give no proof. Can someone please explain why this is true? Here is the link of the paper: https://link.springer.com/article/10.1007/s10898-011-9713-2

Answer 1

If $u=x-\hat x$, then we must find maximum and minimum of the function $\sqrt{u^Tu}$, subject to the constraint $${1\over2}u^TQu=a-t.$$ If $\alpha$ is a Lagrange multiplier, we must then find the stationary points of $$ F(u)=u^Tu+{1\over2}\alpha u^TQu, $$ i.e. the values of $u$ which make the gradient of $F$ vanish: $$ {\partial F\over \partial u}=2u+\alpha Qu=0, $$ which is the same as $$ Qu=-{2\over\alpha}u. $$ Hence the stationary points are eigenvectors $u_i$ of $Q$ and $\alpha=-2/\lambda_i$. The norm of $u_i$ can be found from the constraint equation: inserting there $u=u_i$ we obtain $${1\over2}u_i^TQu_i=a-t, \quad\text{that is:}\quad u_i^Tu_i={2(a-t)\over\lambda_i}. $$ Maximum and minimum of $\sqrt{u^Tu}$ are then $$ \sqrt{2(a-t)\over\lambda_\min}\quad\text{and}\quad\sqrt{2(a-t)\over\lambda_\max}. $$

Answer 2

Change coordinates by defining $y = x - \hat{x}$. Now your function is $$ g(y) = \frac12 y^t Q y + t, $$ where $t = -\frac12 c^t Q^{-1} c$.

The level set for $g(y) = a$ is then all points $y$ with $$ y^t Q y = 2(a - t) $$

Because $Q$ is symmetric positive definite matrix, there's an orthogonal matrix $R$ whose rows are the (unit) eigenvectors of $Q$, such that $$ Q = R^t D R $$ where $D = diag(\lambda_1, \ldots, \lambda_n)$. So we can rewrite $g$ as $$ g(y) = y^t R^t D R y + t. $$ Once again changing coordinates to $z = Ry$, we have $$ h(z) = z^t D z + t $$ whose level-set, for $a$, is $$ \{z \mid z^t D z = 2(a-t) \} $$ Writing that out, we have $$ z_1^2 \lambda_1 + \ldots + z_n^2 \lambda_n = 2(a-t) $$ Now because of the ordering of the $\lambda_i$, we can say $$ z_1^2 \lambda_1 + \ldots + z_n^2 \lambda_n \ge z_1^2 \lambda_1 + \ldots + z_n^2 \lambda_1 = \lambda_1 (z_1^2 + z_n^2) \tag{1} $$ so $$ \lambda_1 \|z\|^2 \ge 2(a-t) $$ hence $$ \|z\|^2 \ge \frac{2(a-t)}{\lambda_1 } $$ so $$ |z| \ge \sqrt{\frac{2(a-t)}{\lambda_1 }}. $$ which says that every point on the ellipsoid is at least that far from the origin (with $(1,0,\ldots, 0)$ being exactly that far from the origin), hence the radius of the inscribed sphere must be that number.

I'll bet that you can take equation 1 and write a less-than-or-equal version involving $\lambda_n$, and derive the other half of the result for yourself.