Седловая точка функции Лагранжа. Достаточные условия оптимальности в задаче на условный экстремум

В теории оптимального управления важное место занимают, так называемые, прямая и двойственная задачи.

Прямой задачей принято называть минимаксную задачу по отношению к функции Лагранжа

.

следующего вида

.

(4.10)

Здесь введено обозначение для функции максимума

.

(4.11)

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

.

(4.12)

Нетрудно убедиться, что решение прямой задачи совпадает с решением исходной задачи на условный экстремум по минимизации функции f ( x ) при условии g ( x )=0.

Действительно,

.

и, следовательно,

(4.13)

Именно поэтому минимаксная задача по отношению к функции Лагранжа называется прямой задачей.

Двойственной задачей принято называть максиминную задачу по отношению к функции Лагранжа

,

(4.14)

где введено обозначение для функции минимума

.

(4.15)

Двойственная задача имеет большое значение, так как во многих случаях её решение также совпадает с решением прямой задачи. Но в отличие от прямой задачи, которая по существу является исходной задачей на условный экстремум, двойственная задача сводится к решению двух задач на безусловный экстремум. А это означает, что практически получить решение двойственной задачи проще, чем решить прямую задачу.

Рассмотрим важный случай, когда решения прямой и двойственной задач совпадают. Предположим, что функция Лагранжа F ( x, l ) имеет единственный (безусловный) минимум по x при любом l. Тогда в силу необходимого условия такого минимума имеем

.

Обозначим решение этого уравнения через . Другими словами,

.

Если l = l ^* - вектор множителей Лагранжа, который соответствует задаче на условный экстремум, то ,  и тогда получаем

.

Для произвольного l

.

Поэтому                             ,

что означает                         

или

.

Таким образом, решение задачи на условный экстремум функции f ( x ) при ограничении g ( x ) = 0 свелось к решению задачи на максимин функции Лагранжа.

В этом случае

,

или в развёрнутом виде

.

(4.16)

Это равенство эквивалентно следующему условию

.

(4.17)

Точка ( x ^*, l ^* ), удовлетворяющая последнему условию, называется седловой точкой функции Лагранжа.

Наличие седловой точки является достаточным условием оптимальности в задаче на условный экстремум функции f ( x ) при ограничении g ( x ) = 0. Покажем это. Пусть ( x ^*, l ^* ) – седловая точка функции Лагранжа F ( x ^*, l ^* ). Тогда для любого l

.

Отсюда следует

.

Для любых l это будет выполняться, только тогда, когда .

С другой стороны, для любого x

.

И если g ( x ) = 0, то f ( x ^* ) £ f ( x ). Следовательно, точка x ^* является решением задачи на условный экстремум.

Таким образом, наличие седловой точки (x ^*, l ^*) функции Лагранжа является достаточным условием оптимальности x ^* в задаче на условный минимум функции f ( x ) при ограничении g ( x )=0.

Пример. Исследуем функциюf ( x ) = x ₁ ² + x ₂ ²на экстремум при условии  x ₁ + x ₂ =1.

Составим функцию Лагранжа

.

Из необходимых условий оптимальности следует

, ,
.

Обратимся теперь к достаточным условиям оптимальности,  для чего исследуем функцию F ( x, l ) на безусловный экстремум по x для любого l. Необходимое условие оптимальности в этом случае примет вид

.

Вычислим гессиан функции F

.

Видим, что H_f положительно-определенная матрица. Поэтому в точке  функция Лагранжа имеет единственный минимум при любом l,. А это в свою очередь означает, что функция Лагранжа F ( x, l ) имеет седловую точку. В соответствии с достаточными условиями оптимальности точка  является точкой минимума в задаче на условный экстремум.

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

На первом этапе ее решения найдем безусловный минимум функции Лагранжа по x

.

Нетрудно получить

.

На втором этапе решения двойственной задачи необходимо найти безусловный максимум функции h(l) по l

.

Из необходимых условий оптимальности получим

.

На основе достаточных условий оптимальности устанавливаем, что точка l ^* = 1 является точкой максимума функции h(l).

Таким образом, решение двойственной задачи

.

совпадает с решением прямой (исходной) задачи.

Упражнение 1. Показать, что соотношения

 и  эквивалентны. Наличие ограничений вида x Î X, l Î L не изменяет данного результата.

Упражнение 2. Показать, что F ( x, l ) имеет седловую точку, если для любого l существует единственный минимум функции F ( x, l ) по x.

Упражнение 3. Показать, что в задаче на отыскание максимума f ( x ) при условии g ( x )=0 прямая задача имеет вид

,

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

.

Упражнение 4. Показать, что если имеют место условия , то функция f ( x ) достигает в точке x ^* максимума при условии g ( x )=0.

 

⇐ Предыдущая1234567Следующая ⇒

Поделиться: