Timeline for Minimizing ellipsoid over intersection of ellipsoids
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 16, 2011 at 18:46 | comment | added | Kap | Yeah ok. However, I am actually interested in the optimal solution. It turns out only finitely many optimal $x$ occur. I wonder whether similar problems have been studied before. | |
| Dec 16, 2011 at 8:35 | comment | added | mikitov | Yes, use $\X \approx \lambda_{\text{max}}uu^T$ where $\lambda_{\text{max}}$ is the maximum eigenvalue with u eigenvector. There are other approximations but I barely remenber them... | |
| Dec 15, 2011 at 17:04 | comment | added | Kap | Ok, so I relaxed the rank 1 constraint and used sedumi (a Matlab semidefinite programming package) to search for the optimal $X$ for different values on $c_j$. It always gives me the same matrix that is not rank 1. So this is unfortunate then for theoretical analysis? The fact that it is the same matrix, can that be used somehow? Maybe to try and find the best rank 1 matrix that is somehow "closest" to this higher rank matrix (that would probably also just be an approximation I guess)? | |
| Dec 15, 2011 at 15:35 | comment | added | mikitov | Yes: i) Your problem as it is, is non-convex ii) Semidefinite programming relaxation can give you an approximate solution of the problem (since you are dropping the rank-one constraint). iii) There might be the case where ALWAYS the semidefinite relaxation gives a rank-one solution. In that case, the solution to the semidefinite relaxation is the optimal value of your problem. Results about this are derived via studying the dual problem of the semidefinite relaxation. | |
| Dec 15, 2011 at 15:27 | comment | added | Kap | 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. | |
| Dec 15, 2011 at 15:12 | comment | added | Kap | 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? | |
| Dec 15, 2011 at 14:49 | comment | added | Igor Rivin | Since your domain is not convex, I m not sure how SDP can help... | |
| Dec 15, 2011 at 14:37 | history | edited | mikitov | CC BY-SA 3.0 |
added 154 characters in body
|
| Dec 15, 2011 at 14:36 | comment | added | mikitov | 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. | |
| Dec 15, 2011 at 14:06 | comment | added | Kap | 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. | |
| Dec 15, 2011 at 13:12 | history | answered | mikitov | CC BY-SA 3.0 |