Finding smallest ellipsoid that circumscribes over intersection of two ellipsoids that do not have common center - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T06:33:50Z http://mathoverflow.net/feeds/question/75730 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75730/finding-smallest-ellipsoid-that-circumscribes-over-intersection-of-two-ellipsoids Finding smallest ellipsoid that circumscribes over intersection of two ellipsoids that do not have common center I J 2011-09-18T05:46:58Z 2012-11-11T10:32:25Z <p>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).</p> <p>I am looking for a method to circumscribe an ellipsoid over the intersection of two ellipsoids. The ellipsoid do not have a common center.<br> 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).</p> http://mathoverflow.net/questions/75730/finding-smallest-ellipsoid-that-circumscribes-over-intersection-of-two-ellipsoids/75772#75772 Answer by Agol for Finding smallest ellipsoid that circumscribes over intersection of two ellipsoids that do not have common center Agol 2011-09-18T17:34:31Z 2011-09-18T17:34:31Z <p>According to <a href="http://books.google.com/books?id=DUcmcXCI4U4C&amp;lpg=PA437&amp;ots=9BXE3meLd5&amp;dq=kahan%2520ellipsoid%2520circumscribe&amp;lr&amp;pg=PA437#v=onepage&amp;q&amp;f=false" rel="nofollow">Kahan's definition</a>, 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. </p> <p>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? </p> http://mathoverflow.net/questions/75730/finding-smallest-ellipsoid-that-circumscribes-over-intersection-of-two-ellipsoids/112016#112016 Answer by Rudi Pendavingh for Finding smallest ellipsoid that circumscribes over intersection of two ellipsoids that do not have common center Rudi Pendavingh 2012-11-10T19:39:51Z 2012-11-11T10:32:25Z <p>You could use semidefinite optimization to find that small enclosing ellipsoid. </p> <p>Let <code>$E(W,c):=\{x\mid (x-c)^TW(x-c)\leq 1\}$</code>. 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. </p> <p>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<br> $$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$. </p> <p>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$. </p> <p>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. </p> <p>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 <code>$E:=\{(x,y)\mid p(x,y)\geq 0\}$</code> 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 <code>$\{x\mid (x,1)\in E\}$</code>.</p> <p>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$. </p>