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

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

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.