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*), чтобы неравенство

Имело место для всех  и всех XS. При этом

Теорема 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.

Вопросы к главе 7

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

2.  Что такое седловая точка? Какую роль играет решение задачи о седловой точке в условной оптимизации?

3.  При выполнении каких условий существуют седловые точки в задачах нелинейного программирования?

4.  Укажите основные направления использования необходимых и достаточных условий оптимальности второго порядка.

5.  Напишите функцию Лагранжа.

Яндекс.Метрика