View source for Calculus/Multivariate optimisation: The Lagrangian

=== The problem ===
In previous sections, we've discussed how, using calculus, we can find the optimal solution of a single-variate <math>y = f(x)</math> by finding all points where <math>f'(x)=0</math>. But what if we're given a bivariate function - for example, <math>z = f(x, y)</math>? More importantly, what if we're given ''constraints'' to follow? The single-variate model does not scale at all. 

=== One variable, one constraint ===
Consider the optimisation problem <math>\min{f(x)}</math> given a constraint <math>g(x) = h</math>. 

First write the constraint in such a way that it's equal to 0 - so <math>g(x) - h = 0</math>. Then the '''Lagrangian''' of the system is defined by <math>L(x, \lambda) = f(x) + \lambda (g(x) - h)</math>. We have two variables to optimise - <math>x</math> and <math>\lambda</math>. Then find the derivatives with respect to the variables:

<math>\frac{\partial L}{\partial x} = f'(x) + \lambda g'(x)</math>

<math>\frac{\partial L}{\partial \lambda} = g(x) - h</math>

Set them to 0. Then the optimal set <math>\{x, \lambda\}</math> is the solution to <math>f'(x) + \lambda g'(x) = 0</math> and <math>g(x) = h</math>. 

{{Editor note|Some authors will only formally take the partial derivatives of the variable and just set the constraints to 0; this is completely fine and it's easy to show that the two approaches are equivalent.

The reason this matters is when doing constrained optimisation with inequality constraints using KKT conditions (which isn't covered in this section), taking the partial derivatives of the constraints will change this to a Lagrangian equality problem - which isn't the same. It's easy to get the two mixed up.}}

=== A simple univariate example ===
{{Calculus/Def|text=
{{font color|red|'''Example.'''}}
Solve the optimisation problem <math>\min{5x + 3}</math> given the constraint <math>x^2 = 25</math>. }}

Then the Lagrangian system is <math>L(x, \lambda) = 5x + 3 + \lambda (x^2 - 25)</math>. Take the respective derivatives:

<math>\frac{\partial L}{\partial x} = 5 + \lambda (2x)</math>

<math>\frac{\partial L}{\partial \lambda} = x^2 - 25</math>

Set the second to zero - we get <math>x = \plusmn 5</math>. Substitute in first: we get <math>5+10\lambda = 0</math>, which is <math>\lambda = -\frac{1}{2}</math>. Substitute in second: we get <math>\lambda = \frac{1}{2}</math>. In this case, the optimal '''minimum''' is the set <math>\{x, \lambda\} = \{-5, \frac{1}{2}\}</math> (which is what we're looking for) and the optimal '''maximum''' is the set <math>\{x, \lambda\} = \{5, \frac{-1}{2}\}</math>.

It is important to realise that the Lagrangian does not guarantee that a particular solution is a minimum - we need to test the solution ourselves - as in one case the solution was actually the ''maximum''. 

This is actually a pretty crappy example as you may have seen - it would have been perfectly appropriate in this case to simply test the optimisation problem with the only two valid values given the constraint! It gets more useful when we have multiple variables and constraints to consider.

=== Two variables, one constraint ===
Consider the optimisation problem <math>\min{f(x, y)}</math> given a constraint <math>g(x, y) = h</math>.

The Lagrangian system is almost identical to the single-variable case discussed above, except that we have a system of '''three''' partial derivatives to consider (2 variables + 1 constraint): <math>L(x, y, \lambda) = f(x, y) + \lambda (g(x, y) - h)</math>. Now take the respective partial derivatives:

<math>\frac{\partial L}{\partial x} = f'_x(x, y) + \lambda g'_x(x, y)</math> (the first variable ''x'')

<math>\frac{\partial L}{\partial y} = f'_y(x, y) + \lambda g'_y(x, y)</math> (the second variable ''y'')

<math>\frac{\partial L}{\partial \lambda} = g(x, y) - h</math> (the constraint)

Set them to 0 - and the optimal triplet <math>\{x, y, \lambda\}</math> is the solution to that. 

=== A bivariate example ===
[[File:3D graphing problem.png|none|frame|The problem, graphed. Notice the constraint "encircling" the optimisation problem - the solution must lie in that outer circle. ]]
{{Calculus/Def|text=
{{font color|red|'''Example.'''}}
Solve the optimisation problem <math>\max{5x+3y}</math> given the constraint <math>x^2 + y^2 = 25</math>. }}
{{hide|'''Solution.'''|
Set up the Lagrangian:

<math>L(x, y, \lambda) = (5x + 3y) + \lambda (x^2 + y^2 - 25)</math>

Take the partial derivatives:

<math>\frac{\partial L}{\partial x} = 5 + \lambda (2x)</math>

<math>\frac{\partial L}{\partial y} = 3 + \lambda (2y)</math>

<math>\frac{\partial L}{\partial \lambda} = x^2 + y^2 - 25</math>

Setting them to 0, we have

<math>5+2\lambda x = 0</math>

<math>3+2\lambda y = 0</math>

<math>x^2 + y^2 = 25</math>

Eliminate <math>\lambda</math> from the first two equations to get a relation between ''x'' and ''y'':

From the second equation, <math>2\lambda y = -3</math>, or <math>\lambda = \frac{-3}{2y}</math>. Similarly, from the first equation, <math>2\lambda x = -5</math>, or <math>\lambda = \frac{-5}{2x}</math>. Combining the two results with <math>\lambda</math>, we get <math>{\frac {-3}{2y}} =  \frac{-5}{2x}</math>. Simplifying, this is <math>{\frac {-3}{y}} =  \frac{-5}{x}</math>, or <math>{\frac {-3x}{y}} = -5</math>, which is <math>{\frac {-3x}{-5}} = y</math>. This is the same as <math>y = \frac{3x}{5}</math>.

Now substitute in the third equation to find ''x'' and ''y'':

<math>x^2 + y^2 = 25</math>

<math>x^2 + \frac{9x^2}{25} = 25</math>

<math>\frac{34x^2}{25} = 25</math>

<math>x = \plusmn \sqrt{\frac{625}{34}}</math> (this is about ± 4.288)

Similarly, <math>y = \frac{3x}{5} = \plusmn \frac{3}{5} \frac{25}{\sqrt{34}}</math> (this is about ± 2.572).

Remember that this is a '''maximisation''' problem, and hence we find that <math>x = \sqrt{\frac{625}{34}}</math> and <math>y = \frac{3}{5} \sqrt{\frac{625}{34}}</math> (the other solution is the minimum). We could have found the value of the constraint <math>\lambda</math>, but that isn't necessary here given that the problem only wants us to find the maximum value. Notice that, as above, the Lagrangian likes to give the ''boundary'' solutions and it's our job to find out which of them is the actual solution (if there is one, that is). }} 

Did we '''have''' to use the Lagrangian? Actually no. The problem could have been reduced to a univariate form by writing one variable of the constraint in terms of the other: <math>y = \plusmn{\sqrt{25 - x^2}}</math>, and substituting it into the optimisation problem: 

<math>\max{(5x + 3y)} = \max{(5x \plusmn 3 ({\sqrt{25 - x^2})})}</math>

and use single-variable calculus techniques to solve the problem! But could you do this when there are '''three''' variables instead? No, because you will most likely only be able to reduce the problem to two variables. 

=== The general form ===
In this section, consider a vector '''x''' of size ''n'': <math>\textbf{x} = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ ... \\ x_n \end{pmatrix}</math>.  

{{Calculus/Def|text=
{{font color|darkblue|'''Definition.'''}} (The Lagrangian)

Consider the optimisation problem <math>\min{f(\textbf{x})}</math> given a vector of ''m'' constraints <math>\textbf{g}(x) = \begin{pmatrix} g_1(\textbf{x}) \\ g_2(\textbf{x}) \\ g_3(\textbf{x}) \\ ... \\ g_m(\textbf{x}) \end{pmatrix} = 0</math>.

The Lagrangian of this system is defined as <math>L(\textbf{x}, \lambda) = f(\textbf{x}) + \lambda (\textbf{g}(x))</math>.}}

Then take the partial derivatives with respect to the vectors '''x''' and '''λ:''' find<math>\frac{\partial L}{\partial \textbf{x}}</math> and <math>\frac{\partial L}{\partial \lambda}</math>.

Notice that this system has ''m'' + ''n'' variables, and you'll need to take ''m'' + ''n'' partial derivatives as well. This can get quite messy. A solution is to use [[Calculus/Calculus on matrices|matrix calculus]].

This may scare you, and you shouldn't be concerned. The average Calculus 3 course will only consider 2 to three variables. 

=== The regularity condition ===
''Knowledge of linear algebra is expected for this section; this is unlikely to be covered in an average Calculus 3 course as a result.'' 

The regularity condition applies when considering the Lagrange FONC (first order necessary condition) 
{{Calculus/Def|text=
{{font color|darkblue|'''Definition.'''}} (The Lagrange FONC)

Consider a minimiser <math>\textbf{x}</math> of a function <math>f</math> which is also regular. Then there exists a <math>\lambda</math> such that <math>\nabla L(\textbf{x}, \lambda)</math> = 0.  }}Remember that it's a '''necessary''' condition. This means that

* just because a point does satisfies the Lagrange FONC does ''not'' mean that it is a minimiser or a maximiser.
* a point that does ''not'' satisfy the Lagrange FONC cannot be a minimiser or maximiser. 
{{Calculus/Def|text=
{{font color|darkblue|'''Definition.'''}} (Regularity condition)
Given a vector of constraints <math>\textbf{g}(x) =  0</math>, the regularity condition says that the gradient of each constraint at a particular point must be '''linearly independent'''.  }}

If this condition is not satisfied, the Lagrange FONC does ''not'' apply at that point. The reason this does not matter with one constraint is because a single vector is linearly independent by definition.
{{Calculus/Def|text=
{{font color|red|'''Example.'''}}

Let <math>\textbf{g}(x, y)</math> be defined as <math>\textbf{g}(x) = \binom{(x + 1)^2 + y^2 - 1}{(x - 2)^2 + y^2 - 4}</math>. Determine whether these vectors are regular at the point (0,0).
}}

{{hide|'''Solution.'''|
Find the gradients:

<math>\nabla g_1(x, y) = \binom{2(x + 1)}{2y}, \nabla g_2(x, y) = \binom{2(x - 2)}{2y}</math>

Substitute at point (0,0):

<math>\nabla g_1(0, 0) = \binom{2}{0}, \nabla g_2(0, 0) = \binom{-4}{0}</math>

The problem now reduces to checking whether the vectors <math>\binom{2}{0}</math> and <math>\binom{-4}{0}</math> are linearly independent. To do that, recall that linear independence requires that given two constants <math>\alpha_1</math> and <math>\alpha_2</math>, the solution to <math>\alpha_1 \binom{2}{0} + \alpha_2 \binom{-4}{0} = \binom{0}{0}</math> 
'''must''' only occur when <math>\alpha_1 = \alpha_2 = 0</math>. 

This is clearly '''not''' the case: a easy example is to set <math>\alpha_1 = 2</math> and <math>\alpha_2 = 1</math>. Hence the Lagrange FONC does not apply to this problem at that point.}}

{{BookCat}}