Основно съдържание

Курс: Анализ на функции на много променливи > Раздел 3

Урок 6: Оптимизация с ограничение (статии)

Множители на Лагранж (въведение)

Класна стая на Google

Множителите на Лагранж са метод за решаване на оптимизационни задачи при наличие на ограничения. Полезно!

Преговор

Основни идеи

С помощта на множителите на Лагранж можем да намираме минимум или максимум на дадена функция $f (x; y; \dots)$ ‍ при наличие на ограничения върху аргументите.
Ограниченията изглеждат така:
$g (x; y; \dots) = c$ ‍
Където $g$ ‍ е друга функция със същия брой аргументи като $f$ ‍, а $c$ ‍ е константа.
Например, ако дефиниционната област на функцията $f$ ‍ е двумерна, а червената крива изобразява решенията на $g (x; y) = c$ ‍, то графиката изглежда така:
Оптимизация с ограничение
Целта ни е да намерим най-високата точка върху червената крива.
Основната идея е да разгледаме точките, в които контурните линии на $f$ ‍ и $g$ ‍ се допират.
С други думи, търсим точките, в които градиентите на $f$ ‍ и $g$ ‍ са успоредни.
Този процес е еквивалентен на това да приравним градиента на една специална функция, наречена лагранжиан, на нулевия вектор.
Стъпка 1: Въвеждаме нова променлива $λ$ ‍ (гръцката буква ламбда) и дефинираме функцията $L$ ‍ по следния начин:
$L (x; y; \dots, λ) = f (x; y; \dots) - λ (g (x; y; \dots) - c)$ ‍
Функцията $L$ ‍ се нарича "лагранжиан", а новата променлива $λ$ ‍ се нарича "множител на Лагранж"
Стъпка 2: Приравняваме градиента на $L$ ‍ на нулевия вектор.
$\nabla L (x; y; \dots, λ) = 0 \leftarrow нулев вектор$ ‍
С други думи, търсим критичните точки на $L$ ‍.
Стъпка 3: За всяка критична точка $(x_{0}; y_{0}; \dots; λ_{0})$ ‍ заместваме съответните стойности в $f$ ‍ (всички координати без $λ_{0}$ ‍, тъй като $f$ ‍ няма аргумент $λ$ ‍ ). Точката, която даде най-голяма (или най-малка) стойност на $f$ ‍, е максимумът (или минимумът), който търсим.

Мотивиращ пример

Ако искаме да намерим максимума на следната функция:

$f (x; y) = 2 x + y$ ‍

но освен това стойностите на

(x; y)

трябва да изпълняват следното условие:

$x^{2} + y^{2} = 1$ ‍

С други думи търсим за коя точка

(x; y)

върху

единичната окръжност

стойността на израза

2 x + y

е най-голяма.

Такива задачи наричаме оптимизационни задачи с ограничение. Условието

x^{2} + y^{2} = 1

за евентуалните решения се нарича "ограничение", а

f (x; y) = 2 x + y

е функцията, чийто максимум или минимум ще търсим.

Нека визуализираме задачата по следния начин. Първо чертаем графиката на

f (x; y)

, която е наклонена равнина, тъй като функцията

f

е линейна. След това проектираме вертикално окръжността

x^{2} + y^{2} = 1

от равнината

x y

върху графиката на

f

. Търсеният максимум съответства на най-високата точка върху проекцията на окръжността.

Видео плейър на видеоклиповете в Кан Академия

Виж видео транскрипцията

В общ вид

В този раздел ще формулираме общия вид на оптимизационна задача с ограничение. За начало, искаме да намерим максимума или минимума на дадена функция на няколко променливи:

$f (x; y; z; \dots)$ ‍

В този контекст функцията е скаларна, тъй като понятието "максимум" има значение само в едно измерение.

Ограничението, което ще разгледаме, е от вида

g (x; y; z; \dots)

= дадена константа

c

. По-късно ще научим как да решаваме такива задачи с помощта на множители на Лагранж.

$g (x; y; z; \dots) = c$ ‍

Тъй като ограничението важи за аргументите на

f

, то функцията

g

трябва да приема същия брой агументи като

f

. Например в задачата по-горе двете функции са

$f (x; y) = 2 x + y$ ‍

$g (x; y) = x^{2} + y^{2}$ ‍

$c = 1$ ‍

Контурни карти (графики)

Подходящ метод за изобразяване на

f

са т. нар. контурни карти.

Припомняме, че контурна линия на графиката на функцията

f (x; y)

наричаме множеството от точки, за които

f (x; y) = k

за дадена константа

k

. Динамичната графика, изобразена по-долу, показва движението на тази контурна линия (в синьо) при промяна на

k

. Окръжността

g (x; y) = 1

е показана в червено. Опитай да намериш най-малката и най-голямата стойност на

k

, за която контурната линия на

f

пресича окръжността.

Упражнение: Какво означава за дадена стойност на

k

контурната линия, представяща функцията

f (x; y) = k

да не пресича червената окръжност с уравнение

g (x; y) = 1

Окръжността

g (x; y) = 1

е всъщност контурна линия на функцията

g

. В такъв случай можем да забележим следното:

Ключово наблюдение: Максималните и минималните стойности на

f

при дадено условие

g (x; y) = 1

съответстват на контурните линии на

f

, които допират контура

g (x; y) = 1

Ако функцията

f

не беше линейна, както е в нашия пример за линейна функция

f

, контурните ѝ линии нямаше да са прави. Например,

$f (x; y) = 2 x^{2} + \sqrt{5 y}$ ‍,

Контурните линии на тази функция изглеждат така:

Но и тук горното наблюдение важи: когато

k

е максимум или минимум на

f

при дадено ограничение, контурните линии съответстващи на

f (x; y) = k

допират тези на

g (x; y) = 1

Ролята на градиента

Какво e математическото значение на това, че две контурни линии се допират?

За да отговорим на този въпрос, трябва да разгледаме градиента

\nabla f

. В този урок ще използваме свойството, че градиентът на $f$ ‍ в точката $(x_{0}; y_{0})$ ‍ е вектор, перпендикулярен на контурната линия, минаваща през тази точка.

Това означава, че когато контурните линии на две функции

f

g

се допират, техните градиенти в допирната точка са успоредни. Ето как изглеждат те за две произволни функции

f

g

Фактът, че контурните линии се допират, не ни дава информация за отношението на дължините на двата успоредни градиента. Нека

(x_{0}; y_{0})

е точката, в която контурите на

f

и на

g

се допират. Тогава за градиентите им имаме следната зависимост:

$\begin{array}{r} \nabla f (x_{0}; y_{0}) = λ_{0} \nabla g (x_{0}; y_{0}) \end{array}$ ‍

където

λ_{0}

е константа, изразяваща отношението на дължините на двата градиента. Някои автори използват отрицателна константа

- λ_{0}

, но в тази и в следващите статии ще използваме

λ_{0}

Нека се върнем към примера

f (x; y) = 2 x + y

g (x; y) = x^{2} + y^{2}

. Градиентът на

f

е равен на

$\begin{array}{r} \nabla f (x; y) = [\begin{array}{c} \frac{\partial}{\partial x} (2 x + y) \\ \frac{\partial}{\partial y} (2 x + y) \end{array}] = [\begin{array}{c} 2 \\ 1 \end{array}] \end{array}$ ‍

и градиентът на

g

$\begin{array}{r} \nabla g (x; y) = [\begin{array}{c} \frac{\partial}{\partial x} (x^{2} + y^{2} - 1) \\ \frac{\partial}{\partial y} (x^{2} + y^{2} - 1) \end{array}] = [\begin{array}{c} 2 x \\ 2 y \end{array}] \end{array}$ ‍

Следователно условието за допиране на двете контурни линии изглежда така:

$\begin{array}{r} [\begin{array}{c} 2 \\ 1 \end{array}] = λ_{0} [\begin{array}{c} 2 x_{0} \\ 2 y_{0} \end{array}] \end{array}$ ‍

Обратно към нашия пример

Търсим точки

(x_{0}; y_{0})

със следните свойства

$g (x_{0}; y_{0}) = 1$ ‍, тоест
$x_{0}^{2} + y_{0}^{2} = 1$ ‍
$\nabla f (x_{0}; y_{0}) = λ_{0} \nabla g (x_{0}; y_{0})$ ‍ за някоя константа $λ_{0}$ ‍, тоест;
$\begin{aligned} 2 & = 2 λ_{0} x_{0} \\ 1 & = 2 λ_{0} y_{0} \end{aligned}$ ‍

Получихме три уравнения за три неизвестни величини, което означава, че можем да ги решим еднозначно.

Първо изразяваме

λ_{0}

и след това заместваме полученото решение, за да намерим

x_{0}

y_{0}

Използвайки последните две уравнения, можем да изразим

x_{0}

y_{0}

чрез

λ_{0}

$\begin{aligned} 2 & = 2 λ_{0} x_{0} \Rightarrow x_{0} = \frac{1}{λ_{0}} \\ 1 & = 2 λ_{0} y_{0} \Rightarrow y_{0} = \frac{1}{2 λ_{0}} \end{aligned}$ ‍

Сега за третото уравнение заместваме полученото в уравнението

x_{0}^{2} + y_{0}^{2} = 1

\begin{aligned} {x_{0}}^{2} + {y_{0}}^{2} & = 1 \\ {(\frac{1}{λ_{0}})}^{2} + {(\frac{1}{2 λ_{0}})}^{2} & = 1 \\ \frac{1}{λ_{0}^{2}} + \frac{1}{4 λ_{0}^{2}} & = 1 \end{aligned}

Съкращаваме

λ_{0}

от знаменателите като приведем под общ знаменател

4 λ_{0}^{2}

\begin{aligned} 4 + 1 & = 4 λ_{0}^{2} \\ \frac{5}{4} & = λ_{0}^{2} \\ \pm \sqrt{\frac{5}{4}} & = λ_{0} \\ \frac{\pm \sqrt{5}}{2} & = λ_{0} \end{aligned}

Използваме получените изрази на

x_{0}

y_{0}

, изразени чрез

λ_{0}

, и получаваме двойките

$\begin{aligned} (x_{0}; y_{0}) & = (\frac{1}{λ_{0}}, \frac{1}{2 λ_{0}}) \\ = (\frac{2}{\sqrt{5}}; \frac{1}{\sqrt{5}}) или (\frac{- 2}{\sqrt{5}}; \frac{- 1}{\sqrt{5}}) \end{aligned}$ ‍

Можем да разберем кое от тези решения е максимум и кое е минимум като заместим в

f (x; y)

и сравним двете стойности.

\begin{aligned} f (\frac{2}{\sqrt{5}}; \frac{1}{\sqrt{5}}) & = 2 \frac{2}{\sqrt{5}} + \frac{1}{\sqrt{5}} \\ = \frac{5}{\sqrt{5}} \\ = \sqrt{5} \leftarrow Максимум \\ f (- \frac{2}{\sqrt{5}}; - \frac{1}{\sqrt{5}}) & = 2 \frac{- 2}{\sqrt{5}} + \frac{- 1}{\sqrt{5}} \\ = \frac{- 5}{\sqrt{5}} \\ = - \sqrt{5} \leftarrow Минимум \end{aligned}

Лагранжиáнът

През 18. век математикът Джоузеф Луис Лагранж прекарал голяма част от живота си, занимавайки се с подобни оптимизационни задачи, и чрез работата си намерил начин да събере всички условия, които получихме при разсъжденията по-горе, в едно единствено уравнение.

В общия случай търсим константи

x_{0}

y_{0}

λ_{0}

, такива че:

Ограничението:
$g (x_{0}; y_{0}) = c$ ‍
Допиращи се контури:
$\nabla f (x_{0}; y_{0}) = λ_{0} \nabla g (x_{0}; y_{0})$ ‍.

Можем да разбием това уравнение на две части по следния начин:

$f_{x} (x_{0}; y_{0}) = λ_{0} g_{x} (x_{0}; y_{0})$ ‍
$f_{y} (x_{0}; y_{0}) = λ_{0} g_{y} (x_{0}; y_{0})$ ‍

Лагранж успял да обедини тези три уравнения в едно (векторно) уравнение за друга функция, която приема същите аргументи като

f

g

, заедно с третия аргумент

λ

$L (x; y; λ) = f (x; y) - λ (g (x; y) - c)$ ‍

Например в нашия пример имаме

\begin{aligned} f (x; y) & = 2 x + y \\ g (x; y) & = x^{2} + y^{2} \\ c & = 1 \end{aligned}

и новата функция ще изглежда така:

$L (x; y; λ) = 2 x + y - λ (x^{2} + y^{2} - 1) .$ ‍

Обърни внимание, че частната производна на

L

по

λ

- (g (x; y) - c)

\begin{aligned} L_{λ} (x; y; λ) & = \frac{\partial}{\partial λ} (f (x, y) - λ (g (x; y) - c) \\ = 0 - (g (x; y) - c) \end{aligned}

Тогава условието

g (x; y) = c

е еквивалентно на

\begin{array}{r} L_{λ} (x; y; λ) = - g (x; y) + c = 0 \end{array}

Нещо повече, ако приравним на нула и другите две частни производни на тази функция, получаваме

\begin{aligned} L_{x} (x; y; λ) & = 0 \\ \frac{\partial}{\partial x} (f (x; y) - λ (g (x; y) - c)) & = 0 \\ f_{x} (x; y) - λ g_{x} (x; y) & = 0 \\ f_{x} (x; y) & = λ g_{x} (x; y) \end{aligned}

Това е едно от условията, които изведохме! Аналогично уравнението

L_{y} (x; y; λ) = 0

е еквивалентно на

\begin{array}{r} f_{y} (x; y) = λ g_{y} (x; y) \end{array}

Трите условия заедно са еквивалентни на

\begin{array}{r} \nabla f (x; y) = λ \nabla g (x; y) \end{array}

Следователно трите уравнения, които трябва да решим, за да получим решенията за

x, y

λ

, са уравнения за частните производни на

L

. Тоест, търсим за кои стойности градиентът на

L

е равен на

0

\begin{array}{r} \nabla L = 0 \end{array}

Например в частния случай, с който започнахме, имаме

\begin{array}{r} \nabla L = [\begin{array}{c} \frac{\partial}{\partial x} (2 x + y - λ (x^{2} + y^{2} - 1)) \\ \frac{\partial}{\partial y} (2 x + y - λ (x^{2} + y^{2} - 1)) \\ \frac{\partial}{\partial λ} (2 x + y - λ (x^{2} + y^{2} - 1)) \end{array}] = [\begin{array}{c} 2 - 2 λ x \\ 1 - 2 λ y \\ - x^{2} - y^{2} + 1 \end{array}] = [\begin{array}{c} 0 \\ 0 \\ 0 \end{array}] \end{array}

Функцията

L

наричаме "лагранжиáн" на името на Лагранж, и новата променлива

λ

наричаме "множител на Лагранж".

Забележка: Някои автори записват

λ

с отрицателен знак:

\begin{array}{r} L (x; y; λ) = f (x; y) + λ (g (x; y) - c) \end{array}

Тази малка промяна не променя решенията, които получаваме, тъй като стойността на множителя на Лагранж може да е отрицателна.

Бележка: Какво се случва, ако ограничението е слабо?

Историята обаче не свършва тук, и останалата част най-добре можем да разкажем с пример.

Търсим максимума на функцията

\begin{array}{r} f (x; y) = e^{- (x^{2} + y^{2})} \end{array}

при дадено ограничение

\begin{array}{r} g (x; y) = x - y = 0 \end{array}

Графиката на

f (x; y) = e^{- (x^{2} + y^{2})}

е т. нар. "нормална крива" с максимум в точката

(x_{0}; y_{0}) = (0; 0)

Това ограничение е диагонална права в равнината

x y

(показана в червено).

Тази задача е до някаква степен тривиална, тъй като максимумът

(0; 0)

на

f

(без ограничение) изпълнява ограничението

g (x; y) = 0

\begin{array}{r} g (0; 0) = 0 + 0 = 0 \end{array}

На пръв поглед изглежда, че така улесняваме работата си. Все пак, ако няма нужда да се тревожим за някакво ограничение, задачата би трябвало да е по-лесна? На практика обаче почти винаги решението на задачата без ограничение не изпълнява ограничението, така че хората (и съответно компютърните алгоритми) се обръщат директно към Лагранж.

Оказва се, че въвеждането на множител на Лагранж дава правилно решение дори когато решението на ограничената задача е максимум и на функцията без ограничение. Причината за това не е очевидна, тъй като не можем да приложим предишната логика.

Например, нека разгледаме контурите от вида

e^{- (x^{2} + y^{2})} = k

за

k

между

0, 5

1

Контурът с уравнение

e^{- (x^{2} + y^{2})} = k

винаги пресича правата с уравнение

x - y = 0

и този контур се свива до точка, когато стойностите на

k

са възможно най-големи. Преди това казахме, че контурните линии ще бъдат допирателни към графиката на

f

, когато функцията достигне своя ограничен максимум, но изглежда много странна точка да е допирателна към крива.

Защо това не е проблем?

Ако функцията

f

достигне локален максимум в точката

(x_{0}; y_{0})

, градиентът ѝ в тази точка е равен на

0

\begin{array}{r} \nabla f (x_{0}; y_{0}) = 0 \end{array}

Тоест допирателната в даден локален максимум е хоризонтална.

В този случай свойството

\begin{array}{r} \nabla f (x_{0}; y_{0}) = λ \nabla g (x_{0}; y_{0}) \end{array}

все още важи, тъй като можем да заместим

λ = 0

Казваме, че дадена точка се "допира" до всички прави, минаващи през нея, точно както нулевият вектор е "пропорционален" (тоест успореден) на всеки друг вектор.

Така че множителите на Лагранж не само събират няколко условия в едно

\begin{array}{r} \nabla L = 0, \end{array}

автоматично се справя със специалните гранични случаи!

Обобщение

За да намерим локалните екстремуми на функцията

f (x; y; \dots)

при наличие на дадено ограничение

g (x; y; \dots) = c

, изпълняваме следните стъпки:

Стъпка 1: Въвеждаме нова променлива $λ$ ‍ (гръцката буква ламбда) и дефинираме функцията $L$ ‍ по следния начин:
$L (x; y; \dots, λ) = f (x; y; \dots) - λ (g (x; y; \dots) - c)$ ‍
Функцията $L$ ‍ се нарича "лагранжиан", а новата променлива $λ$ ‍ се нарича "множител на Лагранж"
Стъпка 2: Приравняваме градиента на $L$ ‍ на нулевия вектор.
$\nabla L (x; y; \dots, λ) = 0 \leftarrow нулев вектор$ ‍
С други думи, търсим критичните точки на $L$ ‍.
Стъпка 3: За всяка критична точка $(x_{0}; y_{0}; \dots; λ_{0})$ ‍, заместваме съответните стойности в $f$ ‍ (всички координати без $λ_{0}$ ‍, тъй като $f$ ‍ няма аргумент $λ$ ‍ ). Точката, която даде най-голяма (или най-малка) стойност на $f$ ‍, е максимумът (или минимумът), който търсим.

Искаш ли да се присъединиш към разговора?

Вписване в профила

Сортирай по:

Все още няма публикации.

Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.