Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 0 down vote accepted

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$?

share|improve this answer
    
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. –  Kap Apr 12 '12 at 16:54
    
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. –  Brian Borchers Apr 12 '12 at 17:03
    
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? –  Kap Apr 12 '12 at 17:12
    
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... –  Dima Pasechnik Apr 12 '12 at 17:30
    
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. –  Kap Apr 12 '12 at 17:49
show 4 more comments

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$.)

share|improve this answer
    
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. –  Kap Apr 12 '12 at 17:52
1  
This particular lower bound might be quite useful within a branch and bound algorithm for the problem. –  Brian Borchers Apr 13 '12 at 4:55
    
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. –  Dima Pasechnik Apr 13 '12 at 7:58
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.