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 am writing a program minimizing a real-valued non-linear function of around 90 real variables subject to around 30 non-linear constraints. I found handy explanation in CERN's Data Analysis BriefBook. I've implemented it and it works, but I am not able to derive how they obtained the equations at the bottom. Could anyone please explain how it can be achieved?

Copied from the link:

Trying to minimize $f(x_1,...,x_n)$ subject to $c_1(x_1,...,x_n) = ... = c_m(x_1,...,x_n) = 0$.

Reformulate as $$\partial F/\partial x_1 = \dots = \partial F/\partial x_n = \partial F/\partial\lambda_1 = \dots = \partial F/\partial\lambda_m = 0$$ for $$ F(x_1,\dots,x_n,\lambda_1,\dots,\lambda_m) = f(x_1,\dots,x_n) - \lambda^T c(x_1,\dots,x_n) $$

Using Lagrange multipliers $\lambda$ and Newton-Raphson, they arrive at (1): $$ A\Delta x - B^T\lambda = -a\\ B\Delta x = -c, $$ where $A$ is Hessian of $f$, $a = (\nabla f)^T$ is gradient of $f$ and $B=\nabla c$ is Jacobian of the constraints.

I can't seem to follow them. The way I understand it, they're applying Newton-Raphson to solve $\nabla F = 0$. I believe that $$ \nabla F = \left(a - B^T \lambda \atop -c \right) $$ Then, we need to take derivative of $\nabla F$ for Newton-Raphson. First off, it seems to me they're only taking the derivative w.r.t. $x$ and not to $\lambda$. Why is that?

Even so, this would lead to (1) if the derivative of $\nabla F$ was $\left(A \atop -B\right)$. However, while it's true that $\nabla a = A$ and $\nabla c = B$, I can't understand where the term $-B^T\lambda$ vanished to.

Many thanks to anyone who could shed some light on this.

share|improve this question
add comment

1 Answer

I also was interested in a proof of the Newton-Raphson+Lagrange multiplier result from the CERN page. Here is my derivation:

enter image description here

enter image description here

share|improve this answer
    
See the editing help on how to type in answers. Images should be avoided for formulas. –  Mårten W Dec 18 '13 at 18:39
    
+1. Thank you very much, I'm finally beginning to understand it. Could you please clarify why it's safe to neglect the second derivative of the constraints (which happens twice in your derivation, if I understand correctly)? –  Angew Dec 20 '13 at 16:33
add comment

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.