Hausdorff distance between ellipsoids and related optimization

192 Views Asked by At

Consider two origin-centered ellipsoids in $\mathbb{R}^{n}$:

$$\mathcal{E}_{A} = \{x \in \mathbb{R}^{n} \mid x^{\top}A^{-1}x \leq 1\}, \quad \mathcal{E}_{B} = \{x \in \mathbb{R}^{n} \mid x^{\top}B^{-1}x \leq 1\}, \quad \mathcal{E}_{B} \subset \mathcal{E}_{A},$$

where $A,B$ are symmetric positive-definite matrices. Computing the Hausdorff distance between these ellipsoids reduces to solving the following optimization problem on unit sphere:

$$d\left(\mathcal{E}_{A},\mathcal{E}_{B}\right) = \max_{x^{\top}x \:=\: 1} \sqrt{x^{\top}Ax} - \sqrt{x^{\top}Bx}.$$

In the context of my interest, I know in addition that $A \succ B$. I am asking if $d\left(\mathcal{E}_{A},\mathcal{E}_{B}\right)$ has a known solution. If no exact analytical results are known, at least under what condition on $A,B$, is this problem convex?

To answer the convexity question, I tried to compute the Hessian, but that does not seem to yield an easy condition on matrices $A,B$.

It feels like this problem must be well-known in the literature, but the only relevant reference I could find is Theorem 2 here which shows: $k_{n}^{-1}|| A^{1/2}-B^{1/2}||_{2} \leq d\left(\mathcal{E}_{A},\mathcal{E}_{B}\right) \leq || A^{1/2}-B^{1/2}||_{2}$ for some constant $k_{n}$ that depends on dimension $n$ (the upper bound is easy, the lower bound needs some work).

P.S. I am interested in solving the generalization:

$$\max_{x^{\top}x \:=\: 1} \sqrt{x^{\top}Ax} - \sum_{i=1}^{n}\sqrt{x^{\top}B_{i}x}$$

where $A \succ \sum_{i=1}^{n} B_{i}$, and the matrices $A,B_{1},...,B_{n}$ are all symmetric positive-definite.