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.

Just had an optimization lecture. I understand unconstrained methods like Newton and Gradient descent just fine, as well as the ideas that give rise to them. I don't really understand the ideas that give rise to the constrained optimization case, for some function $f(x)$.

I get there is an inclusion function, that encodes the domain, call it $g(x)$ Which is defined as 1 when a point is in the domain, and 0 otherwise.

And I understand the that

$$\min[f(x) - \lambda{g(x)}]$$

Is the equivalent problem, which now includes the constraint.

What I want to understand is why this works? To me it doesn't seem that a constant $\lambda$ by a (differentiable approximation to a) square-wave inclusion function, will be a very viable way to find the minimum of $f(x)$. If $f(x)$ has values outside of the constraint domain that are smaller than $\lambda$${g(x)}$ then these will be found as the minimum?

Also, I recall much being made in the lecture about the connection between the gradient's of $f$ and $g$ and an explanation along the lines of: since the gradient is the direction of greatest change, and perpendicular to it, locally, has no change, and since $g$ gradient will have no change, then the minimum will occur at $g$ when the gradient of $f$ is perpendicular to it.

Hopefully someone can give me a reference or an explanation where I can get this sorted out. Also, why are all these $\lambda$ symbols called Lagrangian's, did Lagrange invent a whole class of methods that we now use?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

Lagrange was the one who was first involved in calculus of variations and therefore people tend to call many things in calculus of variations after Lagrange (such as Lagrangian dynamics, Lagrange-Euler equations, Lagrange multipliers, etc...).

In unconstrained optimization the rate of change of f in any direction must be zero. In constrained optimization rate of change of f must be zero in any direction along constraint. In simple case where we have to variables and one constraint $$max_{x,y} f(x,y) \quad s.t.\quad g(x,y)=c$$ The direction along the constraint can be found by total derivative such as $$\frac{\partial g}{\partial x}dx+\frac{\partial g}{\partial y}dy=0$$ Above equation states that if we want to align with the direction of $g(x,y)=c$, dx and dy are related in a way that $$dy=-\frac{\frac{\partial g}{\partial x}}{\frac{\partial g}{\partial y}}dx$$ To maximize f we again use total derivative and replace dy with above equation $$df=\frac{\partial f}{\partial x}dx+\frac{\partial f}{\partial y}dy=0$$ $$df=\frac{\partial f}{\partial x}dx-\frac{\partial f}{\partial y}\frac{\frac{\partial g}{\partial x}}{\frac{\partial g}{\partial y}}dx=0$$ So the equation (1) assures that the function f is maximized along any direction allowed by the constarint and equation (2) assures that we stay on the constraint $$(1) \quad \frac{\partial f}{\partial x}-\frac{\partial f}{\partial y}\frac{\frac{\partial g}{\partial x}}{\frac{\partial g}{\partial y}}=0$$ $$(2) \quad g(x,y)=0$$ Let's see what will be the result with Lagrangian multipliers. The Lagrangian of the system is $$L=f(x,y)+\lambda g(x,y)$$ which results in below equation set $$(1.1*)\quad \frac{\partial L}{\partial x}=\frac{\partial f}{\partial x}+\lambda \frac{\partial g}{\partial x}=0$$ $$(1.2*)\quad \frac{\partial L}{\partial y}=\frac{\partial f}{\partial y}+\lambda \frac{\partial g}{\partial y}=0$$ $$(2*)\quad \frac{\partial L}{\partial \lambda}=g(x,y)=0$$ To eliminate $\lambda$ we can use (1.2*) $$\frac{\partial L}{\partial y}=\frac{\partial f}{\partial y}+\lambda \frac{\partial g}{\partial y}=0\Rightarrow \lambda=-\frac{\frac{\partial f}{\partial y}}{\frac{\partial g}{\partial y}}$$ And replacing in (1.1*) we have below equation set $$(1*)\quad \frac{\partial f}{\partial x}-\frac{\partial f}{\partial y}\frac{\frac{\partial g}{\partial x}}{\frac{\partial g}{\partial y}}=0$$ $$(2*)\quad g(x,y)=0$$

You can see both equation sets (1,2) and(1*,2*) are identical. As you can see using Lagrangian multiplier is a generalization of above case.

PS: You can also use directional derivatives for derivation of general case but above method is easiest one.

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.