Нелинейное программирование (стр. 3 из 7)

Запишем условия Куна—Таккера

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

Условия оптимальности первого порядка записываются как

Заметим, что

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

Если предположить, что

- е ограничение является неактивным (т.е. С другой стороны, если -е ограничение активное (т. е. ), то соответствующая неявная цена не обязательно равна нулю, однако , так как . Таким образом, для всех значений .

Для того чтобы определить знак

(неявной цены, ассоциированной с ограничением ), следует увеличить правую часть ограничения от 0 до 1. Ясно, что при этом область допустимых решений сужается, поскольку любое решение, удовлетворяющее ограничению , автоматически удовлетворяет неравенству . Следовательно, размеры допустимой области уменьшаются, и минимальное значение улучшить невозможно (так как вообще оно может только возрастать). Другими словами, неявная цена , ассоциированная с -м ограничением, должна быть неотрицательной, что соответствует условиям Куна—Таккера.

3.3. Теоремы Куна—Таккера

В предыдущем разделе построены условия Куна—Таккера для задач условной оптимизации. С помощью метода множителей Лагранжа получено интуитивное представление о том, что условия Куна — Танкера тесно связаны с необходимыми условиями оптимальности. В данном разделе рассматриваются строгие формулировки необходимых и достаточных условий оптимальности решения задачи нелинейного программирования.

Теорема 1. Необходимость условий Куна—Таккера

Рассмотрим задачу нелинейного программирования (0)-(2). Пусть

- дифференцируемые функции, а х* — допустимое решение данной задачи. Положим . Далее пусть линейно независимы. Если х* — оптимальное решение задачи нелинейного программирования, то существует такая пара векторов , что является решением задачи Куна—Таккера (3)—(7).

Условие, согласно которому

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

1. Все ограничения в виде равенств и неравенств содержат линейные функции.

2. Все ограничения в виде неравенств содержат вогнутые функции, все ограничения-равенства — линейные функции, а также существует, по крайней мере, одна допустимая точка х, которая расположена во внутренней части области, определяемой ограничениями-неравенствами. Другими словами, существует такая точка х, что

Если условие линейной независимости в точке оптимума не выполняется, то задача Куна—Таккера может не иметь решения.

Пример 4

Минимизировать

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

Решение.

На рис.1 изображена область допустимых решений сформулированной выше нелинейной задачи. Ясно, что оптимальное решение этой задачи есть

. Покажем, что условие линейной независимости не выполняется в точке оптимума.

Рис.1 Допустимая область в задаче 4

Так как

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

Запишем условия Куна—Таккера и проверим, выполняются ли они в точке (1, 0). Условия (3), (6) и (7) принимают следующий вид;

(11)

(12)

(13)

(14)

(15)

(16)

При

из уравнения (11) следует, что , тогда как уравнение (14) дает , Следовательно, точка оптимума не является точкой Куна — Таккера.

Заметим, что нарушение условия линейной независимости не обязательно означает, что точка Куна—Таккера не существует. Для того чтобы подтвердить это, заменим целевую функцию из этого примера функцией

. При этом оптимум по-прежнему достигается в точке (1,0), в которой условие линейной независимости не выполняется. Условия Куна—Таккера (12) - (16) остаются неизменными, а уравнение (11) принимает вид

Нетрудно проверить, что точка

является точкой Куна—Таккера, т. е. удовлетворяет условиям Куна—Таккера.

Теорема о необходимости условий Куна—Таккера позволяет идентифицировать неоптимальные точки. Другими словами, теорему 1 можно использовать для доказательства того, что заданная допустимая точка, удовлетворяющая условию линейной независимости, не является оптимальной, если она не удовлетворяет условиям Куна—Таккера. С другой стороны, если в этой точке условия Куна—Таккера выполняются, то нет гарантии, что найдено оптимальное решение нелинейной задачи. В качестве примера рассмотрим следующую задачу нелинейного программирования.

Следующая теорема устанавливает условия, при выполнении которых точка Куна—Таккера автоматически соответствует оптимальному решению задачи нелинейного программирования.

Теорема.2 Достаточность условий Куна—Таккера

Рассмотрим задачу нелинейного программирования (0) — (2). Пусть целевая функция

выпуклая, все ограничения в виде неравенств содержат вогнутые функции , а ограничения в виде равенств содержат линейные функции . Тогда если существует решение , удовлетворяющее условиям Куна—Таккера (3) — (7), то х* — оптимальное решение задачи нелинейного программирования.