# good approach to solving this nonconvex quadratically-constrained program

I want to find a (local) minimizer $x, y$ to the following optimization problem:

$$\min_{x,y}\ x^T x + a^T x \qquad \mathrm{s.t.} \qquad \begin{array}{r}x^T M_i y + c_i = 0 \\ y \geq 0\end{array}.$$

Is sequential quadratic programming my only recourse, or are there specialized techniques that might be more efficient? Although the problem is clearly non-convex, the special features (the constraint is quadratic, and the inequality-constrained variables appear only linearly in the constraints and not at all in the objective) give me some hope.

-
Unfortunately your constraints are nonconvex equality constraints, making the problem entirely nonconvex. I'm not aware of any special method applicable here and I'm afraid the classics are your friends: SQP, augmented lagrangian, ... –  Dominique Oct 30 '11 at 4:38

Not sure what you had in mind for sequential quadratic programming, did you try the following?

Rewriting the problem with $b=-\frac{1}{2}a$ and $L(y)^T=-[M_1 y, M_2 y, \ldots ]$ and solving for fixed y gives: $$\min_{x,y}\ \frac{1}{2} \|x-b\|^2 \qquad \mathrm{s.t.} \qquad \begin{array}{r} L(y)x = c \\ y \geq 0\end{array}.$$

$$x^* = b + L(y)^T(L(y)L(y)^T)^{-1}(c-L(y)b)$$

So then the problem for y alone is:

$$\min_{y}\ \frac{1}{2} \|c-L(y)b\|_{H^{-1}}^2 \qquad \mathrm{s.t.} \qquad \begin{array}{r} H = L(y)L(y)^T \\ y \geq 0\end{array}.$$

Where $\|z\|_{H^{-1}}^2=z^TH^{-1}z$. So initially take $H_{0}=I$, and then iterate:

$$y_{k+1} = \mbox{arg }\min_{y\ge 0 }\ \frac{1}{2} \|c-L(y)b\|_{H_{k}^{-1}}^2$$

$$H_{k+1} = L(y_{k+1})L(y_{k+1})^T$$

If $c=L(y_1)b$, then $x^*=b$.

-