Machine Learning – Understanding the Role of the Constraint Sign in Lagrangian Multiplier

lagrange multipliersmachine learningoptimization

I am beginner learning Lagrange multipliers with wiki article.

Consider:

maximize $f(x,y)$ subject to $g(x,y) = 0$

I understand that to maximize I must follow the gradient $\nabla {_{x, y}}^{}f$. I also understand that gradient of the constraint $\nabla{_{x, y}}^{}g$ must be collinear to $\nabla {_{x, y}}^{}f$ (to check whether $\nabla {_{x, y}}^{}f$ projection to the constraint line equal to 0).

But I totally misunderstood role of the sign in the equality.

$\nabla {_{x, y}}f = -\lambda \nabla {_{x, y}}g$

where $\lambda > 0$ and we maximizing $f(x,y)$

See picture from wiki:

enter image description here

I could imagine $g'(x,y) = 0$ which give same set of points ${x,y}$ (red line) as $g(x,y) = 0$ but have just the opposite gradient (opposite red arrows direction) and in this case my maximum of $f$ will become minimum?!

Best Answer

There is no sign restriction for the Lagrange multiplier of an equality constraint. Lagrange multipliers of inequality constraints do have a sign restriction.

You should really look at the Karush-Kuhn-tucker conditions if you want to understand Lagrange multipliers https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions . Realistically, you will need to study a book or course notes. Here is a high quality book available as a free pdf from the author's website http://stanford.edu/~boyd/cvxbook/ . If you can make it through chapter 5, you'll be in good shape.

Related Question