3
$\begingroup$

Suppose we are trying to solve the following problem:

\begin{align} \text{minimize} & \hspace{8pt} f(x) \\ \text{subject to} & \hspace{8pt} g(x) = 0, \end{align} where $f$ and $g$ are both differentiable.

The method of Lagrange multipliers says that we should solve the following system of equations: \begin{align} \nabla f(x) &= \lambda \nabla g(x) \\ g(x) &= 0. \end{align}

If I form the Lagrangian, then I get this equation: $$L(x,\lambda) = f(x) - \lambda g(x).$$

If I take the gradient of the Lagrangian $L$ and set it equal to $0$, I find that I get the system of equations that I must solve for the method of Lagrange multipliers. The derivative with respect to $x$ gives me the first equation, and the derivative with respect to $\lambda$ gives me the second equation.

Why is this the case?

$\endgroup$
5
  • $\begingroup$ Are you asking if there is a connection between the derivatives of the Lagrangian function and the equations in the method of Lagrange multipliers? Definitely yes. $\endgroup$ – Matthew Leingang May 8 '18 at 2:18
  • 2
    $\begingroup$ I think you want $L(x, \lambda) = f(x) - \lambda g(x)$ in this formulation; with $L(x, \lambda) = f(x) + \lambda g(x)$ one gets $\nabla f = -\lambda \nabla g$, which works, but is not what is stated in the problem. Cheers! $\endgroup$ – Robert Lewis May 8 '18 at 2:32
  • $\begingroup$ @MatthewLeingang Excellent. Would you explain what the connection is and why? $\endgroup$ – NicNic8 May 8 '18 at 2:41
  • $\begingroup$ What is the problem here? It seems that you are fine with the statement "The method of Lagrange multipliers says that we should solve the following system of equations: \begin{align} \nabla f(x) &= \lambda \nabla g(x) \\ g(x) &= 0." \end{align} Now this statement is obviously equivalent with the quoted statement about the Lagrangian $L(x,\lambda)$. $\endgroup$ – Christian Blatter May 8 '18 at 19:21
  • $\begingroup$ @ChristianBlatter In introductory calculus books, they develop and prove the two equations you listed. I'd like a way to get to the equations from the Lagrangian, but I don't see an intuitive way to understand why the solution would be a saddle point of the Lagrangian. $\endgroup$ – NicNic8 May 9 '18 at 0:05
1
$\begingroup$

The connection comes from calculus.

Consider the problem:

\begin{align} \text{minimize} \quad & f(x) \\ x \in \quad & [a,b] \end{align}

If the point where $f$ attains its minimum is $x^*$, then from the extreme value theorem, $$\frac{\mathrm{d}f}{\mathrm{d}x}(x^*) = 0$$

Now add some equality constraints to this problem to get a general constrained problem.

\begin{align} \text{minimize} \quad & f(x) \\ \text{subject to} \quad & g(x) = 0 \\ x \in \quad & X \end{align}

The method of Lagrange multipliers forms a new function called the Lagrangian: $$\mathcal{L}(x, \lambda) = f(x) \ +\ \lambda g(x) $$

Under some assumptions, it can be proved that if $x^*$ is the point where the equality constrained problem above is minimised, then there is a unique $\lambda^*$ such that

$$\nabla \mathcal{L}(x^*, \lambda^*) = 0$$

This along with the original equality constraint simplifies to the system of equations in your question.

$\endgroup$
3
  • $\begingroup$ Why is a critical point of $\mathcal{L}$ the solution? Is the proof complicated? Is there some intuitive way to understand this? $\endgroup$ – NicNic8 May 8 '18 at 18:05
  • 1
    $\begingroup$ To put it very roughly, if $x^*$ is an optimal solution for $(3)$, then it is also feasible, which means that $g(x^*) =0$, i.e., the Lagrangian is just the calculus problem in disguise. Now the reason why we bother forming the Lagrangian at all is because the domain $X$ need not be as simple as in the case of the calculus problem or the constraints may be inequalities or non-linear and then, the theory of Lagrange multipliers gives us important information on the solutions. $\endgroup$ – Hikaru May 8 '18 at 18:37
  • 1
    $\begingroup$ For a proof refer to the book by Bertsekas $\endgroup$ – Hikaru May 8 '18 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.