Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
@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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.