Условия существования седловой точки

При обсуждении условий оптимальности Куна – Таккера предполагалось, что целевая функция и функции, входящие в ограничения, являются дифференцируемыми. Далее рассматриваются критерии оптимальности для недифференцируемых функций при наличии ограничений.

Определение. Говорят, что функция f(x, y) имеет седловую точку (х*, у*), если для всех х и у.

В определении седловой точки подразумевается, что при х* минимизирует функцию f(x, y*) по всем х, а у* максимизирует функцию f(x*, y) по всем у.

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

Минимизировать f(x)

при ограничениях h_k(x) = 0, k = 1, … , K.

Определим функцию Лагранжа

Предположим, что при v = v* минимум L(x; v*) достигается в точке х = х*, причем h_k(x*)=0. В соответствии с методом множителей Лагранжа известно, что х* есть оптимальное решение задачи нелинейного программирования. Можно показать, что (x*; v*) – седловая точка функции Лагранжа, т. е.

при любых x и v.

Рассмотрим общую задачу нелинейного программирования:

минимизировать f(x)

при ограничениях

Множество S может вводится для того, чтобы учесть дополнительные ограничения на управляемые переменные, например, в тех случаях, когда все управляемые переменные должны принимать только целые значения или значения из некоторого дискретного множества.

Задача Куна – Таккера о седловой точке формулируется следующим образом: найти такой вектор (x*; u*), чтобы неравенство

имело место для всех и всех x Î S. При этом

Теорема 3. Достаточные условия оптимальности

Если (x*;u*) – решение задачи Куна – Таккера о седловой точке, то х* есть оптимальное решение задачи нелинейного программирования.

Замечание.

1) В теореме 3 не требуется выполнения предположений о выпуклости или вогнутости соответствующих функций.

2) Теорема 3 не опирается на условие регулярности допустимой области.

3) Учет нелинейных ограничений-равенств в виде h_k(x*)=0, k=1, . . . , K, можно осуществить путем переопределения функции Лагранжа: Здесь переменные v_k, k=1, …, K, не ограничены по знаку.

4) Теорема 3 устанавливает лишь достаточные условия оптимальности. В связи с этим следует отметить, что встречаются такие задачи нелинейного программирования, в которых седловые точки не существуют и которые в то же время обладают оптимальными решениями.

Рассмотрим условие существования седловых точек. Несколько теорем устанавливают необходимые условия оптимальности, которые гарантируют существование седловой точки при отсутствии предположения о дифференцируемости соответствующих функций. Однако формулировки таких теорем базируются не предположениях о выполнении условий регулярности допустимой области и выпуклости функций.

Теорема 4. Необходимые условия оптимальности

Пусть х* минимизирует f(x) при ограничениях Предполагается, что S – выпуклое множество, f(x) – выпуклая функция, а g_j(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. Напишите функцию Лагранжа.

Не нашли, что искали? Воспользуйтесь поиском по сайту: