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 have certain confusion regarding lagrange multiplier for inequality constraints. I was going through this book by Bishop (Pattern Recognition and Machine Learning) and it says that if I have a function f to be maximized and constraint $g \leq c$ . Then if the maxima is at the boundary that means $g=c$, then the gradient of $f$ at the maxima point at the boundary should point opposite to that of the gradient of $g$. $$ \text{gradient}(f) = -\lambda \times \text{gradient}(g)$$ where $\lambda \geq 0$.

However, while referring to this tutorial http://www.youtube.com/watch?v=3VQBVf6Tr3Y, it says that they should point to the same direction. I am a bit confused and need some clarification.

I am basically confused regarding the direction of gradient(f) and gradient(g). I am not sure why the direction of gradient matters in the inequality constraints except that they should be parallel

share|improve this question
    
The sign of the multiplier DOES matter for inequality constraints. However, your formula above has the wrong sign. If the gradient of $f$ is opposite that of $ g$, then clearly you can increase $f$ and decrease $g$ (thus remaining feasible) at the same time, ie. it is not optimal. In fact, this illustrates why the sign (meaning direction) matters. –  copper.hat Jun 25 '12 at 4:11
add comment

1 Answer 1

Indeed, they can point in the same or opposite directions for equality. The point is that the direction of the two gradients is the same up to some scalar, so since $\lambda$ can be either negative or positive, it follows that the gradients can point both ways.

I.e.

----> $\bar{\nabla}f$

<---- $\bar{\nabla}(g)$

Then $\bar{\nabla}(f) = -1(\bar{\nabla}(g))$ is valid or if,

----> $\bar{\nabla}f$

----> $\bar{\nabla}(g)$

Then also $\bar{\nabla}(f) = 1(\bar{\nabla}(g))$ is valid in optimizing the equation. Note that of course the scalar needn't be 1.

share|improve this answer
    
So you mean what is given in the Bishop's book Pattern Recognition and Machine Learning is wrong? I am not sure about that. I just need some clarifications. –  user31820 Jun 25 '12 at 2:41
    
No, I'm saying that it could be either. You could think of it as the two vectors must "lie on the same line". So they must point in either exactly the same direction, or exactly opposite. Either is fine, because you can multiply by a positive or negative scalar. –  MGN Jun 25 '12 at 2:43
    
For example, say the gradient of f was the vector (1,1). Then the gradient of g could be (2,2) or (3,3) OR (-1,-1), but not (1,3) or something else not lying on the line y=x. –  MGN Jun 25 '12 at 2:45
    
No the books says gradient(f) = -lambda*gradient(g) and lambda >=0. Therefore, the direction is opposite.@MGNewman, I am referring to the case of inequality constraints. In the case of equality constraints what you said is fine. But in the case of inequality, the book explicitly states so. So, I am a bit confused –  user31820 Jun 25 '12 at 2:45
    
On page 708 it seems to suggest: "∇f and ∇g are parallel (or anti-parallel) vectors, and so there must exist a parameter λ such that ∇f + λ∇g = 0 (E.3) where λ = 0 is known as a Lagrange multiplier. Note that λ can have either sign." This would be consistent with what I said earlier. –  MGN Jun 25 '12 at 2:59
show 3 more comments

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.