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?

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.

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.

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?

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.

No I don't, so I'm just trying to find things online. Do you know any good paper online describing this? As far as I see it, the contiguous forms of a perfect form (vertex) $Q$ are vertices of the Ryshkov polyhedron that are neighbours to $Q$. Is that correct?

Forgot to mention that what I know is that the forms $Q$ must always be uniquely determined by some of the inequalities of $e_j^T Q e_j \geq 1$, so basically I want to enumerate the perfect forms on that polyhedron given by those finite number of inequalities.

However, what I essentially need for one of my lattice problems is to enumerate all positive definite forms $Q$ such that $e_j^T Q e_j \geq 1$, $j = 1 to k$, where each element in the $N$-dimensional integer vector $e_j$ is between $-M$ and $M$, where $M$ is some finite integer (i.e. the integer vectors are only inside a finite box). So I'm wondering for how large integers $M$, dimensions $N$ and number of constraints $k$, can I expect to manage this enumeration? Thanks.

Oh thanks a lot for this explanation. I am wondering what exactly are "comtiguous forms"? As I understood it from the thesis, they are neighbouring vertices (neighbouring perfect forms) to a certain vertex in the Ryshkov polyhedron. Since there are infinitely many vertices in the Ryshkov polyhedron, I thought that the algorithm would continue forever if there isn't a bound on the quadratic forms? So I'm wondering what I misunderstand here about the contiguous forms? Thanks.

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.