# Algorithm for dealing with medium-size non-convex QCQP

I have the following problem in $x \in \mathbb C^{205}$

$$\displaystyle\min_{x}x^HAx$$

subject to the following constraints

$$x^HBx = 1$$

$$x^HC_ix = 0$$

for $i \in \{0,1,\dots,203\}$, where $A$ and $B$ are complex $205 \times 205$ matrices and can be assumed to be positive definite. The $C_i$'s are rank-$1$ matrices (each $C_i$ matrix actually only has a single row which is non-zero, namely row $i$) but there are $204$ of them and they are not definite.

I know there is likely not a single best algorithm for dealing with this type of problem, but any suggestions for things to try out would be much appreciated!

• You have 205 205x205 constraint matrices of rank 1? Unless they are dependent, it seems to me they fix your solution to 0, because your solution lies in the intersection of their null spaces. Do the $C_i$ have any known properties other than their rank? Mar 1 '13 at 15:42
• Good point. I wrote that a bit incorrectly. I actually have 204 Ci matrices, not 205! Thanks for pointing that out. Mar 1 '13 at 21:50
• Doesn't this imply that the constraints give you 1-dimensional solution space? I would expect only one direction satisfies $x^HC_ix=0$. So just solve for a solution to your constraints and the rest becomes trivial. Also since $C_i=u_iv_i^H$ is rank 1, aren't your constraints technically linear instead of quadratic? Mar 4 '13 at 18:24
• I don't think it's that trivial. I don't see any reason for the solution to the constraints to be unique. Also, indeed, $C_i$ can be written as $C_i = u_iv_i^H$, but how does this imply that the constraints are linear? You still end up with constraints of the form: $C_{0,0}x_0x_0+C_{0,1}x_0x_1+...C_{0,204}x_0x_{204} = 0$. Mar 5 '13 at 12:59
• $x\ne 0$ and $x^HC_ix = 0$ if and only if $P_{u_i}x=0$ or $P_{v_i}x=0$, where $P_a$ is the projector onto $a$. This is what I meant by linear constraints. Using $S_i:=C_i/trace(C_i^HC_i)^{1/2} +C_I^H/trace(C_iC_i^H)^{1/2}$, isn't the constraint $S_ix=0$ equivalent? Mar 6 '13 at 19:29

One can approximate the quadratic constraints as a set of linear constraints. Each of those constraints corresponds to the requirement that the solution $x$ lie on an ellipsoid. You can approximate the ellipsoid by a polyhedron (a set of planes). Since you are minimizing a quadratic function, you are looking for solutions which stay outside your unit ellipsoids. So now, you can instead solve several problems subject to a single linear halfspace constraint, and if you get a bounded solution, check it against the other halfspace constraints. This will give you an approximate solution which you can refine with a nonlinear optimization method. The downside is that this scales poorly with the number of facets in your ellipsoid approximation.