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.
3
-
6$\begingroup$ Minimize what? Minimize $n$-volume? $(n{-}1)$-surface area? Diameter? $\endgroup$– Joseph O'RourkeCommented Dec 15, 2011 at 1:12
-
$\begingroup$ What is hier fa.? $\endgroup$– András BátkaiCommented Dec 15, 2011 at 12:49
-
$\begingroup$ 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$. $\endgroup$– KapCommented Dec 15, 2011 at 13:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
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.
-
$\begingroup$ 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. $\endgroup$– KapCommented Dec 15, 2011 at 14:06
-
$\begingroup$ 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. $\endgroup$– mikitovCommented Dec 15, 2011 at 14:36
-
$\begingroup$ Since your domain is not convex, I m not sure how SDP can help... $\endgroup$ Commented Dec 15, 2011 at 14:49
-
$\begingroup$ 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? $\endgroup$– KapCommented Dec 15, 2011 at 15:12
-
$\begingroup$ 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. $\endgroup$– KapCommented Dec 15, 2011 at 15:27