Finding smallest ellipsoid that circumscribes over intersection of two ellipsoids that do not have common center - MathOverflow

Finding smallest ellipsoid that circumscribes over intersection of two ellipsoids that do not have common center

2011-09-18T05:46:58Z

Does this already exist in literature? The closest Ive been able to find is circumscribe intersection of two ellipsoids with a common center by W. Kahan (http://www.cs.berkeley.edu/~wkahan/Ellipint.pdf).

I am looking for a method to circumscribe an ellipsoid over the intersection of two ellipsoids. The ellipsoid do not have a common center.
PS: We can assume that the ellipsoids always intersect and they are full dimensional ellipsoids (not enclosed in a subspace). However, the ellipsoids can be infinite cylinders (if the matrix W for (x-c)^TW(x-c) is not invertible).

Answer by Agol for Finding smallest ellipsoid that circumscribes over intersection of two ellipsoids that do not have common center

2011-09-18T17:34:31Z

According to Kahan's definition, an ellipsoid $H$ is "tight" about a convex set $C$ if it does not contain any other ellipsoid $H\supseteq M \supseteq C$. Under this definition, if your ellipsoids are not nested or intersecting in a point, then either ellipsoid will be tight about their intersection. So it seems to me that the answer to your question is trivial.

Maybe you intend a different meaning for the term "circumscribe"? Do you want a simple description of all of the ellipsoids circumscribing the convex set?

Answer by Rudi Pendavingh for Finding smallest ellipsoid that circumscribes over intersection of two ellipsoids that do not have common center

2012-11-10T19:39:51Z

You could use semidefinite optimization to find that small enclosing ellipsoid.

Let $E(W,c):=\{x\mid (x-c)^TW(x-c)\leq 1\}$ . Your problem is to find, given the ellipsoids $E(W_1,c_1)$ and $E(W_2, c_2)$, a positive definite matrix $A$ and a vector $z$ such that $E(W_1,c_1)\cap E(W_2, c_2)\subseteq E(A,z)$ and $Vol(E(A,z))$ as small as possible.

Minimizing the volume amounts to maximizing the concave function $\log(\det(A))$. By the positivstellensatz, the polynomial inequality $p(x):=1-(x-z)^TA(x-z)\geq 0$ holds true for all $x$ such that $q_i(x):= 1- (x-c_i)^TW_i(x-c_i)\geq 0$ for $i=1,2$ if and only if
$$p=s_1q_1+s_2q_2+t,$$ where $s_1,s_2,t$ are some polynomials that are sums of squares (SOS) (there are some technical conditions for the 'only if'). Now a polynomial $u$ of degree $2d$ is a SOS if and only if $u(x)= \tilde{x}^TU\tilde{x}$ for some positive semidefinite matrix $U$, there $\tilde{x}$ is a vector whose entries are the monomials of degree $\leq d$ in the $x_i$.

All together this gives, fixing a max. degree $d$, an optimization problem over positive semidefinite matrices $A, S_1, S_2, T$ and a vector $z$, where the entries of these matrices are restricted by linear equations that depend on the input ellipsoids. The higher $d$, the better an approximation of the optimal enclosing ellipsoid you will get. However the sizes of the SOS matrices are exponential in $d$.

Edit: Markus notes below that $p$ depends on the entries of $A, z$ in a cubic way, and I agree that that is a problem. So I guess the method above works only if we fix $z$, which is not as nice.

So here is a way out. Introduce a new variable $y$ and a new equation $y-1=0$ to the system, and put $p(x,y):=1-(x-zy)^TA(x-zy)=1-w^tBw$, where $w=(x,y)$. Then $E:=\{(x,y)\mid p(x,y)\geq 0\}$ is an ellipsoid centered at the origin when $B$ is positive semidefinite, and we can minimize the volume of $E$ as before by maximizing $\log(\det(B))$. As $E$ is constrained only to contain some stuff at $y=1$, minimizing the volume of $E$ is equivalent to minimizing the volume of $\{x\mid (x,1)\in E\}$ .

To take the new equation $y=1$ into account, we optimize over all $p$ such that $$p=s_1q_1+s_2q_2+t +(y-1)u,$$ where $s_1,s_2,t$ are SOS polnomials and $u$ is any polynomial. The variables of this problem are positive semidefinite matrices $B, S_1, S_2, T$ and the free coefficients of $u$.