Timeline for Solving a non-convex quadratically-constrained quadratic program
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 25, 2012 at 1:06 | comment | added | Brian Borchers | BARON is described at: archimedes.cheme.cmu.edu/baron/baron.html | |
| Apr 13, 2012 at 9:39 | vote | accept | Kap | ||
| Apr 13, 2012 at 9:39 | vote | accept | Kap | ||
| Apr 13, 2012 at 9:39 | |||||
| Apr 13, 2012 at 9:38 | comment | added | Kap | Do you have any links on a B&B method solving this problem Brian? You are right, I did not express the problem in a correct way with that comment. I meant that the solution is at the point outside the convex intersection that is closest to the origin. I was thinking about looking at the coordinates $y_j = x_j^2$, for which the objective function becomes linear (the loss in sign is compensated by changing the sign of the different cross terms $\sqrt{y_jy_k}$ in the constraint region). What do you think about this idea, could it help to analytically show where the solution must occur? | |
| Apr 13, 2012 at 5:03 | comment | added | Brian Borchers | The MATLAB toolbox is finding a local minimum solution- these will occur at points where several of the ellipsoids intersect. However, there's no way to be sure that the local minimum it finds will be a global minimum. The comment about "smallest sphere touching the intersection" is inconsistent with the original statement of the problem. | |
| Apr 13, 2012 at 0:02 | comment | added | Dima Pasechnik | What you wrote in the comment above: "find the smallest sphere touching the intersection of some ellipsoids" is a not a description of the problem in your question. The latter is not convex, the former is. Which of the two are you trying to solve? | |
| Apr 12, 2012 at 17:49 | comment | added | Kap | Thank you for your answer Dima. The thing is, since we have $\geq$ in our constraints and the different $G_j$ are PSD, then that actually defines a non-convex region. So geometrically, the constraints define a region \emph{outside} the intersection of $m$ ellipsoids. The objective function is simply the norm of a vector, so the problem is to find the shortest vector outside this region. | |
| Apr 12, 2012 at 17:30 | comment | added | Dima Pasechnik | Intersection of ellipsoids is convex. What exactly do you mean by "the smallest sphere"? Do you mean to look for a point of minimal norm in the intersection? If yes, this is a convex problem, and your formulation has a bug, it appears... | |
| Apr 12, 2012 at 17:12 | comment | added | Kap | Oh OK, thx for the tips. Geometrically, this problem looks simple: find the smallest sphere touching the intersection of some ellipsoids. What MATLABs toolbox gives me is that the solution is always at the unique intersection points of these ellipsoids. Is there any result about this type of problem? | |
| Apr 12, 2012 at 17:03 | comment | added | Brian Borchers | I don't know of any code for this specialized problem. You could certainly give it to a more general purpose branch and bound code for non-convex (MI)NLP problems like BARON. Using such a solver (or a custom program written by you), it should be possible to get reasonably good solutions with bounds (e.g. "Here's a solution with objective value 21.72, and our best bound on the optimal value is 21.45.") within a few minutes of computation. The process will be much faster if you have a reasonably good (in objective value) feasible solution to start with. | |
| Apr 12, 2012 at 16:54 | comment | added | Kap | Well in my case it's rather small. I have around 400 different $G_j$, i.e., $m = 400$, and the dimensionality of the problem is at most dimension $N = 6$, i.e., $\vec{x}$ is at most a 6 dimensional real vector, and $G_j$ 6 dimensional positive semidefinite matrices. It isn't so big or? Also, these algorithms that can give the optimal solution, where can they be found? Do you know if Matlab has any such algorithm maybe? Thanks. | |
| Apr 12, 2012 at 16:09 | history | edited | Brian Borchers | CC BY-SA 3.0 |
Made N lower case.
|
| Apr 12, 2012 at 15:49 | history | answered | Brian Borchers | CC BY-SA 3.0 |