7.7. Условия существования седловой точки
При обсуждении условий оптимальности Куна – Таккера предполагалось, что целевая функция и функции, входящие в ограничения, являются дифференцируемыми. Далее рассматриваются критерии оптимальности для недифференцируемых функций при наличии ограничений.
Определение. Говорят, что функция F(X, Y) имеет Седловую точку (х*, у*), если 
для всех х и у.
В определении седловой точки подразумевается, что при Х* минимизирует функцию F(X, Y*) По всем Х, а У* максимизирует функцию F(X*, Y) по всем У.
Обратимся к методу множителей Лагранжа, изложенному выше. Этот метод используется при решении задач условной оптимизации, которые записываются в следующем виде:
Минимизировать F(X)
При ограничениях Hk(X) = 0, k = 1, … , K.
Определим функцию Лагранжа
Предположим, что при V = V* Минимум L(X; V*) достигается в точке Х = х*, причем Hk(X*)=0. В соответствии с методом множителей Лагранжа известно, что Х* есть оптимальное решение задачи нелинейного программирования. Можно показать, что (X*; V*) – седловая точка функции Лагранжа, т. е.
При любых X и V.
Рассмотрим общую задачу нелинейного программирования:
Минимизировать F(X)
При ограничениях 
Множество S Может вводится для того, чтобы учесть дополнительные ограничения на управляемые переменные, например, в тех случаях, когда все управляемые переменные должны принимать только целые значения или значения из некоторого дискретного множества.
Задача Куна – Таккера о седловой точке формулируется следующим образом: найти такой вектор (X*; U*), чтобы неравенство
Имело место для всех 
и всех X S. При этом
Теорема 3. Достаточные условия оптимальности
Если (X*;U*) – решение задачи Куна – Таккера о седловой точке, то х* есть оптимальное решение задачи нелинейного программирования.
Замечание.
1) В теореме 3 не требуется выполнения предположений о выпуклости или вогнутости соответствующих функций.
2) Теорема 3 не опирается на условие регулярности допустимой области.
3) Учет нелинейных ограничений-равенств в виде Hk(X*)=0, K=1, . . . , K, можно осуществить путем переопределения функции Лагранжа: 
Здесь переменные Vk, K=1, …, K, не ограничены по знаку.
4) Теорема 3 устанавливает лишь достаточные условия оптимальности. В связи с этим следует отметить, что встречаются такие задачи нелинейного программирования, в которых седловые точки не существуют и которые в то же время обладают оптимальными решениями.
Рассмотрим условие существования седловых точек. Несколько теорем устанавливают необходимые условия оптимальности, которые гарантируют существование седловой точки при отсутствии предположения о дифференцируемости соответствующих функций. Однако формулировки таких теорем базируются не предположениях о выполнении условий регулярности допустимой области и выпуклости функций.
Теорема 4. Необходимые условия оптимальности
Пусть Х* минимизирует F(X) при ограничениях 
Предполагается, что S – выпуклое множество, F(X) – выпуклая функция, а Gj(X) – функции, вогнутые на множестве S. Предполагается также, что существует такая точка 
, в которой 
для всех J=1, 2, …, J. Тогда существует такой вектор множителей 
, что (X*, U*) является седловой точкой функции Лагранжа
И неравенство
Выполняется для всех 
Следующая теорема обеспечивает некоторое упрощение вычислений, связанных с нахождением седловой точки.
Теорема 5. Вектор (X*; U*), где 
, определяет седловую точку в задаче Куна – Таккера о седловой точке тогда и только тогда, когда выполняются следующие условия:
1) х* минимизирует L(X; U*) по всем 
;
2) 
для J =1, …, J;
3) 
для J=1, …, J.
Важно отметить, что существование седловых точек характерно не для всех задач нелинейного программирования; седловые точки имеются лишь в тех задачах, которые отвечают условиям Теоремы 4.
1. Поясните трудности, которые возникают при использовании метода множителей Лагранжа для решения задач с неотрицательными переменными.
2. Что такое седловая точка? Какую роль играет решение задачи о седловой точке в условной оптимизации?
3. При выполнении каких условий существуют седловые точки в задачах нелинейного программирования?
4. Укажите основные направления использования необходимых и достаточных условий оптимальности второго порядка.
5. Напишите функцию Лагранжа.
| < Предыдущая | Следующая > |
|---|
