# Software to optimize a quadratic program with quadratic constraints

I'm working in eight dimensions and want to minimize $x^TAx$ under the constraints $x^TBx \geq c$. Unfortunately, A is not positive semidefinite. Worse, I am almost positive that my domain is not convex. Is there a good software suite to do this? Since $A$ has some nice properties (it has only two unique entries on the diagonal, it only has nonzero off-diagonal entries symmetrically in one super-/sub-diagonal, the entries of which are all the same) I don't want to use a genetic algorithm. Googling reveals nothing that handles quadratic constraints.

Edit: $A$ is this matrix (where $N_1$ and $N_2$ are positive reals and $I \in M_4(\mathbb{R}$):

$\frac{1}{\sqrt{N_1 + N_2}} \left[ \begin{array}{ccc} (N_1-\sqrt{N_1}\sqrt{N_1 + N_2}) \cdot I & \frac{1}{2}(N_1 +N_2) \cdot I \\ \frac{1}{2}(N_1 +N_2) \cdot I & (N_2-\sqrt{N_2}\sqrt{N_1 + N_2}) \cdot I \end{array}\right]$

The restrictions are these:

$\left[ \begin{array}{ccc} 1 \dots 1 \\ 1 \dots 1 \end{array}\right] \cdot x = \left( \begin{array}{ccc} 1 \\ 1 \end{array}\right) \\ x_i \geq 0 \\ x_i \leq 1, 1 \leq i \leq 8$

where $x$ $\in \mathbb{R}^8$. Letting $x = \left[ \begin{array}{ccc} s_1 \\ s_2 \end{array}\right]$, and given $a, b, c, d \in \mathbb{R}$, I also have the constraints:

$\epsilon_1 \geq a - b \\ \epsilon_2 \geq c - d$

where

$\epsilon_1 = s_1 \cdot (\frac{N_1s_1 + N_2s_2}{N_1 + N_2}) * \sqrt{N_1 + N_2} - s_1 \cdot s_1 * \sqrt{N_1} \\ \epsilon_2 = s_2 \cdot (\frac{N_1s_1 + N_2s_2}{N_1 + N_2}) * \sqrt{N_1 + N_2} - s_2 \cdot s_2 * \sqrt{N_2}$

-
@Clancy your question is too general. Please give $A$ and $B$. –  vesszabo Aug 15 '12 at 8:47
Not sure if it will help, but lehigh.edu/ise/documents/04t_006.pdf describes a solution technique for quadratically constrained quadratic programming problems. –  Daryl Aug 15 '12 at 9:53
@vesszabo Done. Sorry for not putting the second constraint set in matrix form, it's easier to write this way. –  Julien Clancy Aug 15 '12 at 10:37
Clancy Thanks. I have no idea :-( I hope @Daryl's comment can help you. –  vesszabo Aug 15 '12 at 14:40

As $A$ is not positive semidefinite and you have (convex) linear equality and inequality constraints, your problem seems to be NP-hard. There is unfortunatly no quick and easy way to solve your problem. I'm not sure if there is commercial software available to solve non-convex quadratic problems yet.
One way to go is doing grid search on all possible values of $\mathbf{x}$. As the dimension of your problem is only 8, this method could deliver the global optimium in reasonable time.