4
$\begingroup$

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.

  • 0
    U$n$fortunately 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, ...2011-10-30

1 Answers 1

1

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