Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
6  
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
add comment

1 Answer

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.

share|improve this answer
    
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
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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