Welcome to MathOverflow

Question

1

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.

edited Dec 15 2011 at 14:10

asked Dec 15 2011 at 0:46

Kap
109●4

6

Minimize what? Minimize $n$-volume? $(n{-}1)$-surface area? Diameter? – Joseph O'Rourke Dec 15 2011 at 1:12

What is hier fa.? – András Bátkai Dec 15 2011 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 2011 at 13:01

mikitov · Answer 1 · 2011-12-15 14:37:20Z UTC

1

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.

edited Dec 15 2011 at 14:37

answered Dec 15 2011 at 13:12

mikitov
105●7

	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 2011 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 2011 at 14:36
	Since your domain is not convex, I m not sure how SDP can help... – Igor Rivin Dec 15 2011 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 2011 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 2011 at 15:27

show 4 more comments

Minimizing ellipsoid over intersection of ellipsoids

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.