Calculus/Multivariate optimisation: The Lagrangian

From Wikibooks, open books for an open world
Jump to navigation Jump to search

The problem[edit | edit source]

In previous sections, we've discussed how, using calculus, we can find the optimal solution of a single-variate by finding all points where . But what if we're given a bivariate function - for example, ? More importantly, what if we're given constraints to follow? The single-variate model does not scale at all.

One variable, one constraint[edit | edit source]

Consider the optimisation problem given a constraint .

First write the constraint in such a way that it's equal to 0 - so . Then the Lagrangian of the system is defined by . We have two variables to optimise - and . Then find the derivatives with respect to the variables:

Set them to 0. Then the optimal set is the solution to and .

TODO

Editor's 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[edit | edit source]

Example. Solve the optimisation problem given the constraint .

Then the Lagrangian system is . Take the respective derivatives:

Set the second to zero - we get . Substitute in first: we get , which is . Substitute in second: we get . In this case, the optimal minimum is the set (which is what we're looking for) and the optimal maximum is the set .

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[edit | edit source]

Consider the optimisation problem given a constraint .

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): . Now take the respective partial derivatives:

(the first variable x)

(the second variable y)

(the constraint)

Set them to 0 - and the optimal triplet is the solution to that.

A bivariate example[edit | edit source]

The problem, graphed. Notice the constraint "encircling" the optimisation problem - the solution must lie in that outer circle.

Example. Solve the optimisation problem given the constraint .

Solution.

Set up the Lagrangian:

Take the partial derivatives:

Setting them to 0, we have

Eliminate from the first two equations to get a relation between x and y:

From the second equation, , or . Similarly, from the first equation, , or . Combining the two results with , we get . Simplifying, this is , or , which is . This is the same as .

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

(this is about ± 4.288)

Similarly, (this is about ± 2.572).

Remember that this is a maximisation problem, and hence we find that and (the other solution is the minimum). We could have found the value of the constraint , 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: , and substituting it into the optimisation problem:

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[edit | edit source]

In this section, consider a vector x of size n: .

Definition. (The Lagrangian)

Consider the optimisation problem given a vector of m constraints .

The Lagrangian of this system is defined as .

Then take the partial derivatives with respect to the vectors x and λ: find and .

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 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[edit | edit source]

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)

Definition. (The Lagrange FONC)

Consider a minimiser of a function which is also regular. Then there exists a such that = 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.

Definition. (Regularity condition) Given a vector of constraints , 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.

Example.

Let be defined as . Determine whether these vectors are regular at the point (0,0).


Solution.

Find the gradients:

Substitute at point (0,0):

The problem now reduces to checking whether the vectors and are linearly independent. To do that, recall that linear independence requires that given two constants and , the solution to must only occur when .

This is clearly not the case: a easy example is to set and . Hence the Lagrange FONC does not apply to this problem at that point.