Separation of Ellipsoids

We consider the following geometrical problem: find a hyperplane that separates two ellipsoids in $mathbf{R}^n$ , or determine there is none.

Putting a sphere in a half-space

We first seek a condition that determines wether the sphere of radius centered at is entirely contained in the half-space

$mathbf{H} := left{ x ~:~ a^Tx le b right} ,$

where $a in mathbf{R}^n$ , b in mathbf{R} are given.

The condition is equivalent to the fact that

$b ge max_{x ::: |x|_2 le 1} : a^Tx .$

In view of the Cauchy-Schwartz inequality, we have

Clearly, the right-hand side is attained by some vector on the unit circle, namely x = a/|a|_2 . Thus, the condition we seek is

Now consider the case with an ellipsoid instead of a sphere. An ellipsoid mathbf{E} can be described as an affine transformation of the unit sphere:

$mathbf{E} = left{ hat{x} + R u ~:~ |u|_2 le 1 right},$

where $hat{x} in mathbf{R}^n$ is the ‘‘center’’, and is a matrix that determines the ‘‘shape’’ of the ellipsoid.

The containement condition mathbf{H} supseteq mathbf{E} is equivalent to

$b ge max_{u ::: |u|_2 le 1} : a^T(hat{x} + R u).$

Using the same argument as before, we obtain the condition

$b ge a^That{x} + |R^Ta|_2.$

Note that the condition that mathbf{E} should be on the other side of the hyperplane is readily obtained by changing a,b in -a,-b , that is:

$b le a^That{x} - |R^Ta|_2.$

Now consider two ellipsoids

$mathbf{E}_i = left{ hat{x}_i + R_i u ~:~ |u|_2 le 1 right}, ;; i=1,2,$

where $hat{x}_i in mathbf{R}^n$ are the centers, and R_i the shape matrices, i=1,2 .

The hyperplane $left{ x ~:~ a^Tx = b right}$ separates the two ellipsoids if and only if

$b_1 := a^That{x}_1 + |R_1^Ta|_2 le b le a^That{x}_2 - |R_2^Ta| := b_2 .$

Thus, the existence of such a separating hyperplane is equivalent to the existence of $a in mathbf{R}^n$ such that

$a^T(hat{x}_2 - hat{x}_1) ge |R_1^Ta|_2 + |R_2^Ta|_2 .$

Exploiting the homogeneity with respect to , we can always normalize the condition so that $a^That{x}_2 - a^That{x}_1=1$ . The SOCP

$p^ast = min_a : |R_1^Ta|_2 + |R_2^Ta|_2 ~:~ a^That{x}_2 - a^That{x}_1 = 1.$

allows to determine if the ellipsoids are separable: they are if and only if p^ast le 1 . In this case, an appropriate value of is

$b = frac{b_1+b_2}{2} .$

Separating two ellipsoids by a hyperplane.