1
$\begingroup$

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

  • 0
    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.2012-06-25

1 Answers 1

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.

  • 0
    Thanks for the link. But I still didn't get it. Could you please elaborate a bit more.2012-06-25