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).

  • $\begingroup$ so what happens when the ellipsoids don't intersect? $\endgroup$ – Suvrit Sep 18 '11 at 10:00
  • $\begingroup$ I don't expect there will be a method that improves over finding the minimum enclosing ellipsoid for an arbitrary convex set. In practice, one uses points on the boundary of the set. See, e.g., "Approximate Minimum Volume Enclosing Ellipsoids Using Core Sets" and citations therein. $\endgroup$ – Joseph O'Rourke Sep 18 '11 at 11:39
  • $\begingroup$ @Joseph: At first shot, I also thought that this will be just MVCE (or MVEE), but wasn't sure, because the OP is asking about intersections...; but perhaps you are right, that in general, MVCE might be the best that one can do. $\endgroup$ – Suvrit Sep 18 '11 at 12:47
  • $\begingroup$ @Suvrit: Ah, we can assume that the ellipsoids intersect and they are "full" ellipsoids (not embedded in a subspace). @Joseph: But I do not want to compute the intersection itself which would be quite expensive. Also, this is the link to the W. Kahan paper I talked about in my question: cs.berkeley.edu/~wkahan/Ellipint.pdf $\endgroup$ – I J Sep 18 '11 at 17:11

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?

  • $\begingroup$ Ah, that's a good point. I'll change tight to mean the smallest $\endgroup$ – I J Sep 18 '11 at 17:46

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$.

  • $\begingroup$ Hi Rudi. To get {..} in math mode surround your dollar signs with these guys ``. I edited your post. $\endgroup$ – Tony Huynh Nov 10 '12 at 19:47
  • $\begingroup$ @Rudi: This won't give a semidefinite program (at least not in an obvious way) since $p$ depends in a cubic way on the entries of $A$ and $z$. To have a semidefinite program you can only afford linear dependence. The other problem is that the "technical condition" for the "only if" part is not so clear. This would be worth investigating. What I know immediately is that if the two original ellipsoids are compact (which is not always the case in the problem as it is posed), then it is true that $p+\varepsilon$ for each $\varepsilon>0$ (instead of $p$) has such a sums of squares representation. $\endgroup$ – Markus Schweighofer Nov 10 '12 at 20:56
  • $\begingroup$ @Marcus: you're right of course. Edited my answer a bit.. $\endgroup$ – Rudi Pendavingh Nov 10 '12 at 23:49
  • $\begingroup$ @Rudi: Can you explain further. You want p to be of a certain shape, right? On the other hand, this shape seems to contradict the positive semidefiniteness constraint you put on $B$, doesn't it? By the way there seems to be a little typo in the shape you specify for $p$. Anyway, I guess something must be wrong for in the equation $p=s_1q_1+s_2q_2+t+(y-1)u$ you could always choose $s_1=s_2=u=0$ so that $p$ can be any positive semidefinite quadratic form in $x$ and $y$. So maximizing $\log(\det(B))$ is un unbounded problem. $\endgroup$ – Markus Schweighofer Nov 11 '12 at 10:12
  • $\begingroup$ @Markus: Thanks. I should not post here before morning coffee, I guess. Fixed. $\endgroup$ – Rudi Pendavingh Nov 11 '12 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.