Summary:

This video explains how to compute the distance between two ellipses (minimum distance between any pair of points in them), by optimizing a function subject to linear matrix inequalities (LMI), that is, semidefinite programming (SDP).

The basic idea is to express the ellipses ${(x_i-c_i)}^T{Q}_i^{-1}(x_i-c_i)\le 1$, $i\in \{1,2\}$, as LMI sets, using Schur’s formula. Also a distance bound ${(x_1-x_2)}^T(x_1-x_2)\le d^2$ will be expressed as an LMI on decision variables $x_1$ and $x_2$ using the Schur formula, and $\xi \equiv d^2$ will be minimized, as the overall semidefinite programming setting is a particular case of convex optimization.

Results are checked numerically and plotted for three examples, including an example where the ellipses do intersect and, therefore, the distance is zero (although the numerical solver does not yield exactly zero as a result, due to the tolerances and finite precision of the code). The actual software used in this video is Matlab, jointly with the free SDP toolboxes YALMIP and SeDuMi.

*Link to my [whole collection] of videos in English. Link to larger [Colección completa] in Spanish.