Główna zawartość

Analiza matematyczna funkcji wielu zmiennych

Kurs: Analiza matematyczna funkcji wielu zmiennych > Rozdział 3

Lekcja 5: Constrained optimization (articles)

Lagrange multipliers, introduction

Google Classroom

The "Lagrange multipliers" technique is a way to solve constrained optimization problems. Super useful!

Kontekst

What we're building to:

The Lagrange multiplier technique lets you find the maximum or minimum of a multivariable function start color #0c7f99, f, left parenthesis, x, comma, y, comma, dots, right parenthesis, end color #0c7f99 when there is some constraint on the input values you are allowed to use.
This technique only applies to constraints that look something like this:
start color #bc2612, g, left parenthesis, x, comma, y, comma, dots, right parenthesis, equals, c, end color #bc2612
Here, start color #bc2612, g, end color #bc2612 is another multivariable function with the same input space as start color #0c7f99, f, end color #0c7f99, and start color #bc2612, c, end color #bc2612 is some constant.
[Obrazek]
The core idea is to look for points where the contour lines of start color #0c7f99, f, end color #0c7f99 and start color #bc2612, g, end color #bc2612 are tangent to each other.
This is the same as finding points where the gradient vectors of start color #0c7f99, f, end color #0c7f99 and start color #bc2612, g, end color #bc2612 are parallel to each other.
The entire process can be boiled down into setting the gradient of a certain function, called the Lagrangian, equal to the zero vector.
[Specifically...]

Motivating example

Suppose you want to maximize this function:

start color #0c7f99, f, left parenthesis, x, comma, y, right parenthesis, equals, 2, x, plus, y, end color #0c7f99

But let's also say you limited yourself to inputs left parenthesis, x, comma, y, right parenthesis which satisfy the following equation:

start color #bc2612, x, squared, plus, y, squared, equals, 1, end color #bc2612

In other words, for which point left parenthesis, x, comma, y, right parenthesis on the start color #bc2612, start text, u, n, i, t, space, c, i, r, c, l, e, end text, end color #bc2612 is the value start color #0c7f99, 2, x, plus, y, end color #0c7f99 biggest?

This is what's known as a constrained optimization problem. The restriction to points where start color #bc2612, x, squared, plus, y, squared, equals, 1, end color #bc2612 is called a "constraint", and start color #0c7f99, f, left parenthesis, x, comma, y, right parenthesis, equals, 2, x, plus, y, end color #0c7f99 is the function that needs to be optimized.

Here's one way to visualize this: First draw the graph of start color #0c7f99, f, left parenthesis, x, comma, y, right parenthesis, end color #0c7f99, which looks like a slanted plane since start color #0c7f99, f, end color #0c7f99 is linear. Next, project the circle start color #bc2612, x, squared, plus, y, squared, equals, 1, end color #bc2612 from the x, y-plane vertically onto the graph of start color #0c7f99, f, end color #0c7f99. The maximum we are seeking corresponds with the highest point of this projected circle on the graph.

Filmy wideo na Khan Academy

Zobacz transkrypcję filmu

More general form

In general, constrained optimization problems involve maximizing/minimizing a multivariable function whose input has any number of dimensions:

start color #0c7f99, f, left parenthesis, x, comma, y, comma, z, comma, dots, right parenthesis, end color #0c7f99

Its output will always be one-dimensional, though, since there's not a clear notion of "maximum" with vector-valued outputs.

The type of constraints that the Lagrange multiplier technique applies to must take the form of some other multivariable function start color #bc2612, g, left parenthesis, x, comma, y, comma, z, comma, dots, right parenthesis, end color #bc2612 being set equal to a constant start color #bc2612, c, end color #bc2612.

start color #bc2612, g, left parenthesis, x, comma, y, comma, z, comma, dots, right parenthesis, equals, c, end color #bc2612

Since this is meant to be a constraint on the input of start color #0c7f99, f, end color #0c7f99, the number of dimensions in the input of start color #bc2612, g, end color #bc2612 is the same as that of start color #0c7f99, f, end color #0c7f99. For example, the example outlined above fits this general form as follows:

start color #0c7f99, f, left parenthesis, x, comma, y, right parenthesis, equals, 2, x, plus, y, end color #0c7f99

start color #bc2612, g, left parenthesis, x, comma, y, right parenthesis, equals, x, squared, plus, y, squared, end color #bc2612

start color #bc2612, c, equals, 1, end color #bc2612

[Multiple constraints]

Using contour maps

Reasoning about this problem becomes easier if we visualize start color #0c7f99, f, end color #0c7f99 not with a graph, but with its contour lines.

As a reminder, a contour line of start color #0c7f99, f, left parenthesis, x, comma, y, right parenthesis, end color #0c7f99 is the set of all points where start color #0c7f99, f, left parenthesis, x, comma, y, right parenthesis, equals, k, end color #0c7f99 for some constant k. The following interactive tool shows how this line (drawn in blue) changes as the constant k changes. The circle start color #bc2612, g, left parenthesis, x, comma, y, right parenthesis, equals, 1, end color #bc2612 is also shown (in red). Try to make k as big/small as possible while still allowing contour line of start color #0c7f99, f, end color #0c7f99 to intersect the circle.

Concept check: What does it mean if for a particular value of k, the blue line representing start color #0c7f99, f, left parenthesis, x, comma, y, right parenthesis, equals, k, end color #0c7f99 does not intersect the red circle representing start color #bc2612, g, left parenthesis, x, comma, y, right parenthesis, equals, 1, end color #bc2612?

(Choice A)
There are no values of x and y satisfying both start color #0c7f99, 2, x, plus, y, equals, k, end color #0c7f99 and start color #bc2612, x, squared, plus, y, squared, equals, 1, end color #bc2612
(Choice B)
The given optimization problem has no solutions.

Notice, the circle where start color #bc2612, g, left parenthesis, x, comma, y, right parenthesis, equals, 1, end color #bc2612 can be thought of as a particular contour line of the function start color #bc2612, g, end color #bc2612. So with that, here's the clever way to think about constrained optimization problems:

Key observation: The maximum and minimum values of start color #0c7f99, f, end color #0c7f99, subject to the constraint start color #bc2612, g, left parenthesis, x, comma, y, right parenthesis, equals, 1, end color #bc2612, correspond with contour lines of start color #0c7f99, f, end color #0c7f99 that are tangent to the contour representing start color #bc2612, g, left parenthesis, x, comma, y, right parenthesis, equals, 1, end color #bc2612.

If start color #0c7f99, f, end color #0c7f99 were a different function, its contours might not always be straight lines. This is unique to our example since start color #0c7f99, f, end color #0c7f99 is linear. For example, take a look at this function:

start color #0c7f99, f, left parenthesis, x, comma, y, right parenthesis, equals, 2, x, squared, plus, square root of, 5, y, end square root, end color #0c7f99,

Its contour lines look like this:

That said, the key observation still holds, and is worth repeating: When k is a maximum or minimum of f subject to the constraint, the contour line for start color #0c7f99, f, left parenthesis, x, comma, y, right parenthesis, equals, k, end color #0c7f99 will be tangent to contour representing start color #bc2612, g, left parenthesis, x, comma, y, right parenthesis, equals, 1, end color #bc2612.

Where the gradient comes into play

How do you put the idea of two contour lines being tangent into a formula you can solve?

To answer this, we turn to our loyal friend the gradient. There are many ways to interpret del, f: The direction of steepest ascent, a tool for computing directional derivatives, etc. But for our purposes here, the property we care about is that the gradient of f evaluated at a point left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, right parenthesis always gives a vector perpendicular to the contour line passing through that point.

This means when the contour lines of two functions start color #0c7f99, f, end color #0c7f99 and start color #bc2612, g, end color #bc2612 are tangent, their gradient vectors are parallel. Here's what that might look like for arbitrary functions start color #0c7f99, f, end color #0c7f99 and start color #bc2612, g, end color #bc2612:

The fact that contour lines are tangent tells us nothing about the magnitude of each of these gradient vectors, but that's okay. When two vectors point in the same direction, it means we can multiply one by some constant to get the other. Specifically, let left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, right parenthesis represent a particular point where the contour lines of start color #0c7f99, f, end color #0c7f99 and start color #bc2612, g, end color #bc2612 are tangent (writing x, start subscript, 0, end subscript and y, start subscript, 0, end subscript with a 0 subscripts just indicates that we are considering constant values, and hence a specific point). Since this tangency means their gradient vectors align, here's what you might write down:

$\begin{aligned} \nabla \blueE{f(x_0, y_0)} = \greenE{\lambda}_0 \nabla \redE{g(x_0, y_0)} \end{aligned}$

Here, start color #0d923f, lambda, end color #0d923f, start subscript, 0, end subscript represents some constant. Some authors use a negative constant, minus, start color #0d923f, lambda, end color #0d923f, start subscript, 0, end subscript, but I personally prefer a positive constant, as it gives a cleaner interpretation of start color #0d923f, lambda, start subscript, 0, end subscript, end color #0d923f down the road.

Let's see what this looks like in our example where start color #0c7f99, f, left parenthesis, x, comma, y, right parenthesis, equals, 2, x, plus, y, end color #0c7f99 and start color #bc2612, g, left parenthesis, x, comma, y, right parenthesis, equals, x, squared, plus, y, squared, end color #bc2612. The gradient of f is

$\begin{aligned} \nabla f(x, y) = \left[ \begin{array}{c} \dfrac{\partial}{\partial \blueD{x}}(2\blueD{x} + y) \\ \\ \dfrac{\partial}{\partial \redD{y}}(2x + \redD{y}) \\ \end{array} \right] = \left[ \begin{array}{c} 2 \\ 1 \end{array} \right] \end{aligned}$

and the gradient of g is

$\begin{aligned} \nabla g(x, y) = \left[ \begin{array}{c} \dfrac{\partial}{\partial \blueD{x}}(\blueD{x}^2 + y^2 - 1) \\ \\ \dfrac{\partial}{\partial \redD{y}}(x^2 + \redD{y}^2 - 1) \\ \end{array} \right] = \left[ \begin{array}{c} 2x \\ 2y \end{array} \right] \end{aligned}$

Therefore, the tangency condition ends up looking like this:

$\begin{aligned} \left[ \begin{array}{c} 2 \\ 1 \end{array} \right] = \greenE{\lambda_0} \left[ \begin{array}{c} 2x_0 \\ 2y_0 \end{array} \right] \end{aligned}$

Solving the problem in the specific case

To sum up where we are so far, we are looking for input points left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, right parenthesis with the following properties:

g, left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, right parenthesis, equals, 1, which for our example means
start color #bc2612, x, start subscript, 0, end subscript, squared, plus, y, start subscript, 0, end subscript, squared, equals, 1, end color #bc2612
del, f, left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, right parenthesis, equals, start color #0d923f, lambda, start subscript, 0, end subscript, end color #0d923f, del, g, left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, right parenthesis for some constant start color #0d923f, lambda, start subscript, 0, end subscript, end color #0d923f, which for our example means
$\begin{aligned} \quad {2} &{= 2\greenE{\lambda_0} x_0} \\ {1} &{= 2\greenE{\lambda_0} y_0} \end{aligned}$

There are 3 equations and 3 unknowns, so this is a perfectly solvable situation.

[See the final solution]

The Lagrangian function

In the 1700's, our buddy Joseph Louis Lagrange studied constrained optimization problems of this kind, and he found a clever way to express all of our conditions into a single equation.

You can write these conditions generally by saying we are looking for constants x, start subscript, 0, end subscript, y, start subscript, 0, end subscript and lambda, start subscript, 0, end subscript that satisfy the following conditions:

The constraint:
start color #bc2612, g, left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, right parenthesis, equals, c, end color #bc2612
The tangency condition:
del, f, left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, right parenthesis, equals, lambda, start subscript, 0, end subscript, del, g, left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, right parenthesis.
This can be broken into its components as follows:
f, start subscript, x, end subscript, left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, right parenthesis, equals, lambda, start subscript, 0, end subscript, g, start subscript, x, end subscript, left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, right parenthesis
f, start subscript, y, end subscript, left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, right parenthesis, equals, lambda, start subscript, 0, end subscript, g, start subscript, y, end subscript, left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, right parenthesis

Lagrange wrote down a special new function which takes in all the same input variables as f and g, along with the new kid in town lambda, thought of now as a variable rather than a constant.

L, left parenthesis, x, comma, y, comma, lambda, right parenthesis, equals, start color #0c7f99, f, left parenthesis, x, comma, y, right parenthesis, end color #0c7f99, minus, lambda, left parenthesis, start color #bc2612, g, left parenthesis, x, comma, y, right parenthesis, minus, c, end color #bc2612, right parenthesis

For example, consider our example above.

\begin{aligned} \quad \blueE{f(x, y)} &= \blueE{2x + y }\\ \redE{g(x, y)} &= \redE{x^2 + y^2} \\ \redE{c} &= \redE{1} \\ \end{aligned}

Here's how this new function would look:

L, left parenthesis, x, comma, y, comma, lambda, right parenthesis, equals, start color #0c7f99, 2, x, plus, y, end color #0c7f99, minus, lambda, left parenthesis, start color #bc2612, x, squared, plus, y, squared, minus, 1, end color #bc2612, right parenthesis, point

Notice, the partial derivative of L with respect to lambda is minus, left parenthesis, g, left parenthesis, x, comma, y, right parenthesis, minus, c, right parenthesis:

\begin{aligned} \quad \mathcal{L}_\lambda(x, y, \lambda) &= \dfrac{\partial}{\partial \lambda}\left(f(x, y) - \lambda (g(x, y)-c \right) \\ &= 0 - (g(x, y)-c) \end{aligned}

So we can translate the condition g, left parenthesis, x, comma, y, right parenthesis, equals, c as

\begin{aligned} \quad \redE{ \mathcal{L}_\lambda(x, y, \lambda) = -g(x, y) + c = 0 } \end{aligned}

What's more, look at what we get when we set one of the other partial derivatives equal to 0:

\begin{aligned} \quad \mathcal{L}_x(x, y, \lambda) &= 0 \\ \\ \dfrac{\partial}{\partial x}(f(x, y) - \lambda (g(x, y)-c)) &= 0 \\ \\ f_x(x, y) - \lambda g_x(x, y) &= 0 \\ \\ {f_x(x, y)} &{= \lambda g_x(x, y)} \end{aligned}

That just so happens to be another one of our conditions! Almost identically, the condition L, start subscript, y, end subscript, left parenthesis, x, comma, y, comma, lambda, right parenthesis, equals, 0 unravels to become

\begin{aligned} \quad {f_y(x, y) = \lambda g_y(x, y)} \end{aligned}

Together, these conditions are the same as saying.

\begin{aligned} \quad \nabla f(x, y) = \lambda \nabla g(x, y) \end{aligned}

Therefore, the three conditions we need to solve to find x, comma, y and lambda come down to the various partial derivatives of L being equal to 0. This can be written extremely compactly by setting the gradient of L equal to the zero vector:

\begin{aligned} \quad \nabla \mathcal{L} = \textbf{0} \end{aligned}

For example, using our specific functions from above, we see how this encodes the system of equations we need to solve:

\begin{aligned} \quad \nabla \mathcal{L} = \left[ \begin{array}{c} \dfrac{\partial}{\partial x}(2x + y - \lambda(x^2 + y^2 - 1)) \\ \\ \dfrac{\partial}{\partial y}(2x + y - \lambda(x^2 + y^2 - 1)) \\ \\ \dfrac{\partial}{\partial \lambda}(2x + y - \lambda(x^2 + y^2 - 1)) \\ \\ \end{array} \right] = \left[ \begin{array}{c} 2 - 2\lambda x \\ 1 - 2\lambda y \\ -x^2 - y^2 + 1 \\ \end{array} \right] = \left[ \begin{array}{c} 0 \\ 0 \\ 0 \\ \end{array} \right] \end{aligned}

As a tribute to ol' Joey Lou, we call this function L the "Lagrangian", and the new variable lambda that we introduce is called a "Lagrange multiplier". Imagine if someone added "-ian" the end of your last name and made it the name of a function everybody uses. Pretty sweet!

Warning: Some authors use a convention where the sign of lambda is reversed:

\begin{aligned} \quad \mathcal{L}(x, y, \lambda) = f(x, y) \redE{+} \lambda (g(x, y)-c) \end{aligned}

This doesn't make any difference when it comes to solving the problem, but you should keep it in mind in case the course you are taking or the text you are reading follows this convention.

[What if the constraint isn't so constraining]

Podsumowanie

When you want to maximize (or minimize) a multivariable function start color #0c7f99, f, left parenthesis, x, comma, y, comma, dots, right parenthesis, end color #0c7f99 subject to the constraint that another multivariable function equals a constant, start color #bc2612, g, left parenthesis, x, comma, y, comma, dots, right parenthesis, equals, c, end color #bc2612, follow these steps:

Krok 1: Introduce a new variable start color #0d923f, lambda, end color #0d923f, and define a new function L as follows:
L, left parenthesis, x, comma, y, comma, dots, comma, start color #0d923f, lambda, end color #0d923f, right parenthesis, equals, start color #0c7f99, f, left parenthesis, x, comma, y, comma, dots, right parenthesis, end color #0c7f99, minus, start color #0d923f, lambda, end color #0d923f, left parenthesis, start color #bc2612, g, left parenthesis, x, comma, y, comma, dots, right parenthesis, minus, c, end color #bc2612, right parenthesis
This function L is called the "Lagrangian", and the new variable start color #0d923f, lambda, end color #0d923f is referred to as a "Lagrange multiplier"
Krok 2: Set the gradient of L equal to the zero vector.
del, L, left parenthesis, x, comma, y, comma, dots, comma, start color #0d923f, lambda, end color #0d923f, right parenthesis, equals, start bold text, 0, end bold text, left arrow, start color gray, start text, W, e, k, t, o, r, space, z, e, r, o, w, y, end text, end color gray
In other words, find the critical points of L.
Krok 3: Consider each solution, which will look something like left parenthesis, x, start subscript, 0, end subscript, comma, y, start subscript, 0, end subscript, comma, dots, comma, start color #0d923f, lambda, end color #0d923f, start subscript, 0, end subscript, right parenthesis. Plug each one into f. Or rather, first remove the start color #0d923f, lambda, end color #0d923f, start subscript, 0, end subscript component, then plug it into f, since f does not have start color #0d923f, lambda, end color #0d923f as an input. Whichever one gives the greatest (or smallest) value is the maximum (or minimum) point you are seeking.

Chcesz dołączyć do dyskusji?

Zaloguj się

Sortuj według

Na razie brak głosów w dyskusji

Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.