I have the following quadratic optimization problem: $\min_{\vec{x}} |\vec{x}|^2$ subject to $\vec{x}^T G_j \vec{x} \geq 1$, $j = 1 \ldots m$, where the $G_j$ are positive semidefinite. $|\vec{x}|$ is the norm of the vector $\vec{x}$ and $T$ denotes transpose. Since the $G_j$ are positive semidefinite, and we have $\geq$ in the constraints, the constraint region is non-convex. I am wondering if there are any theoretical results about the solution to this problem (except KKT conditions)? Also, are there any algorithms that can give the optimal value, and not only a local optima? Thanks.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
9
Branch-and-Bound can be used to solve problems like this, but it's an exponential time algorithm that is not practical for large instances of the problem. What is $n$, the dimension of the $x$ vector? How big is your $m$?
answered Apr 12, 2012 at 15:49
-
$\begingroup$ 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. $\endgroup$– KapApr 12, 2012 at 16:54
-
$\begingroup$ 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. $\endgroup$ Apr 12, 2012 at 17:03
-
$\begingroup$ 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? $\endgroup$– KapApr 12, 2012 at 17:12
-
$\begingroup$ 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... $\endgroup$ Apr 12, 2012 at 17:30
-
$\begingroup$ 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. $\endgroup$– KapApr 12, 2012 at 17:49
$\begingroup$
$\endgroup$
3
In theory, there is a polynomial-time algorithm (follows from results of my joint paper with Dima Grigoriev) when $m$ is fixed, but this is not a practical one, and moreover I see from comments above that your $m$ is large compared to $n$.
You can efficiently compute a semidefinite programming relaxation: $$ \min Tr(X)\ \ \text{subject to $X\succeq 0$ (i.e. $X$ being p.s.d.) and } Tr(XG_j)\geq 1,\ 1\leq j\leq m.$$ (To see that this is a relaxation, think of $X=xx^\top$.)
answered Apr 12, 2012 at 17:26
-
$\begingroup$ Yes, thanks for that advice. I have alreday tried a convex relaxation of the problem, and the optimal $X$ is not rank 1, instead it is of full rank. So this is then a lower bound to the optimal value, but I am interested in actually finding the optimal solution. $\endgroup$– KapApr 12, 2012 at 17:52
-
1$\begingroup$ This particular lower bound might be quite useful within a branch and bound algorithm for the problem. $\endgroup$ Apr 13, 2012 at 4:55
-
$\begingroup$ there are also moment matrices approaches due to J.Lasserre et al. Tools like YALMIP users.isy.liu.se/johanl/yalmip implement parts of this. $\endgroup$ Apr 13, 2012 at 7:58
$\begingroup$
$\endgroup$
Your non-convex constraint is that $x$ lies on the outside of the intersection of some set of ellipsoids, which is a convex region $S$. You can try to randomly sample the surface of this set for random directions $u$, to determine the shortest vector in that direction which lies outside $S$. You can then do this repeatedly for random $u$ directions to try to approximate the answer. You might be able to get an idea of the maximum sampling density required based on the minimum angle between principal axes of $G$. This could lead to an ultimate refinement process once you have enough samples.
