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 $


$ \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} $

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

Note: Without the linear constraints, the minimization of a non-convex quadratic form subject to one quadratic constraints could be easily solved.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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