# Minimizing ellipsoid over intersection of ellipsoids

Let's say I want to minimize a quadratic form $\sum_{j=1}^n c_jx_j^2$ (all $c_j$ are positive constants), which corresponds to an $n$ dimensional ellipsoid, over the outer part of the intersection of some given ellipsoids, i.e., minimize subject to the constraints $x^TA_jx \geq 1$, $j=1\ldots m$, where $A_j$ are given positive semidefinite matrices (thus making our region an intersection of ellipsoids). Are there any analytical results for these type of problems? Maybe not for general $A_j$, but at least for some? By analytical I mean "not numerical solutions". Thanks in advance.

-
Minimize what? Minimize $n$-volume? $(n{-}1)$-surface area? Diameter? – Joseph O'Rourke Dec 15 '11 at 1:12
What is hier fa.? – András Bátkai Dec 15 '11 at 12:49
I want to minimize the weighted sum of squares subject to those constraints. Geometrically, it corresponds to finding the smallest ellipsoid where each axis is scaled by $c_j$. – Kap Dec 15 '11 at 13:01

There are, you should look at 'Semidefinite Programming':

http://en.wikipedia.org/wiki/Semidefinite_programming

EDIT:

See Pag 58 of L. Vandenberghe and S. Boyd, “Semidefinite programming,” SIAM Rev., vol. 38, pp. 49–95, 1996. regarding results about the problem.

-
Yes I'm aware of sdp, but as far as I see, there are not many exact results for sdp, or I'm wrong? Couldn't find many in the literature. – Kap Dec 15 '11 at 14:06
You should try to define more 'exact results'. From my point of view you might need to consider whether or not the semidifinite relaxation of your problem leads to a rank-one solution of the problem (otherwise, you will just get a lower bound of the solution). See L. Vandenberghe and S. Boyd, “Semidefinite programming,” SIAM Rev., vol. 38, pp. 49–95, 1996." for more info. – mikitov Dec 15 '11 at 14:36
Since your domain is not convex, I m not sure how SDP can help... – Igor Rivin Dec 15 '11 at 14:49
Thank you very much for the reference mikitov. I have seen this paper before. So basically you say I should solve an sdp over the matrix $X = xx^T$, but relax $X$ so that it can be any positive semidefinite matrix of rank at least 1? So if the solution is an $X$ of higher rank, then the best thing I can do is to give a lower bound? – Kap Dec 15 '11 at 15:12
Yes Igor, the constraint region is highly non-convex. However, my simulations show that for certain structured $A_j$, there are finitely many $x$ appearing when the $c_i$ are varied. This somehow seems possible if we think about the geometry in the problem. The optimal $x$ is obtained by looking at all points $kx$, $k>0$, on the ellipsoid $\sum_j c_jx_j^2 = 1$ and choosing the $x$ in our region with largest such number $k$. In a way, the optimal $x$ should then be located on as many ellipsoids as possible. – Kap Dec 15 '11 at 15:27