Distance between two ellipsoids via Lagrange multipliers

Question

I want to use Lagrange multipliers to find the minimum separating distance between two ellipsoids, both centered at the origin.

To illustrate, we start with both ellipsoids sharing the same center:

And want to finish with the closest point that the two ellipsoids may be separated:

Answer 1

• We want to minimize the distance between two ellipsoids, defined $(X-C)^{T}A(X-C)$ and $X^{T}BX^{T}$.
• This means we want to minimize the squared displacement of $C$, $|C|^{2}$ under certain conditions:

1. $X$ is on the surface of the ellipsoid defined by $A$, i.e $(X-C)^{T}A(X-C) - 1 = 0$
2. $X$ is on the surface of the ellipsoid defined by $B$, i.e $(X)^{T}B(X) - 1 = 0$
3. According to [this paper][3], the gradients of the two points at the point of contact should be equal and of opposite sign.

We therefore let

$2A(X-C) = -2s^{2}BX$

where $s^2$ is some positive scalar to be minimized.

Rearranging, we get: $(X-C) = -s^{2}A^{-1}BX$

Substituting $X = rV$, where $r$ is a distance absorbed into $s^{2}$ and $V$ is a unit vector:

Let $X-C = -s^{2} \alpha V$, such that $(X-C) = s^{2}(I - \alpha)V = s^{2}\beta V$

This yields the additional constraint:

$V^{T}V - 1 = 0$

Using the above, we may build the Lagrangian Multiplier:

$\mathcal{L} = s^{4}V^{T} \beta^{T} \beta V - \lambda_{0}s^{4}(V^{T} \alpha^{T} A \alpha V - 1) - \lambda_{1}s^{4}(V^{T}BV - 1) - \lambda_{2}(V^{T}V - 1)$

From this we derive a set of 5 differential equations to solve:

$\frac{\partial L}{\partial s} = 4s^{3}V^{T}(\beta^{T}\beta - \lambda_{0}\alpha^{T}A\alpha - \lambda_{1}B)V$

$\frac{\partial L}{\partial V} = 2s^{4}(\beta^{T}\beta - \lambda_{0}\alpha^{T}A\alpha - \lambda_{1}B - \lambda_{2}s^{-4}I)V$

$\frac{\partial L}{\partial \lambda_{0}} = -s^{4}(V^{T} \alpha^{T} A \alpha V - 1)$

$\frac{\partial L}{\partial \lambda_{1}} = -s^{4}(V^{T} B V - 1)$

$\frac{\partial L}{\partial \lambda_{2}} = -(V^{T}V - 1)$

Solving numerically gives a nice result:

Answer 2

Given symmetric and positive definite matrices $\rm A$ and $\rm B$ and vector $c$,

$$\begin{array}{ll} \text{minimize} & \| \mathrm x - \mathrm y \|_2^2\\ \text{subject to} & (\mathrm x - \mathrm c)^\top \mathrm A \, (\mathrm x - \mathrm c) = 1\\ & \mathrm y^\top \mathrm B \, \mathrm y = 1\end{array}$$

---

optimization qcqp lagrange-multiplier