2
$\begingroup$

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

  • 0
    Clancy Thanks. I have no idea :-( I hope @Daryl's comment can help you.2012-08-15

1 Answers 1

1

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.