Minimal outer ellipsoid

Given a basic semi-algebraic set (namely a set defined by polynomial inequalities and equalities) $\mathcal{K} = {x |p_i(x)\le 0, i=0,...,N, q_j(x)=0, j=0,...,M}$ (where $p_i(x), q_j(x)$ are polynomial functions of $x$), together with some points $v_1, v_2, ..., v_n$, we aim at finding the minimal outer ellipsoid that covers both this basic semi-algebraic set $\mathcal{K}$ and points $v_i, i=1,...,n$ through convex optimization.

For example, here we show the minimal outer ellipsoid that covers the inner shape (black)

$$ x_0^4 + x_1^4 - 1.925x_0^2x_1^2 \le 1, x_1 \le 1.25 $$

and here is an example in 3D that our ellipsoid (green) covers the inner shape (blue)

$$ x_0^4 + x_1^4 - 1.925x_0^2x_1^2+x_2\le 1, x_2 \ge 0 $$

Here is another example, that we show the minimal outer ellipsoid that covers many points

Getting started

You can install the package and the dependencies through

pip install -e .

Using Drake

We use Drake to write our optimization program. If you are unfamiliar with Drake, you can checkout its tutorials.

Examples

You can check the jupyter notebook examples in examples folder. For a mathematical explanation on our optimization program, check our doc