Главная > Нелинейное программирование. Единый подход
<< Предыдущий параграф Следующий параграф >>
Пред.
След.
Макеты страниц

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

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

2.5. ДОСТАТОЧНОСТЬ И УСЛОВИЯ КУНА—ТАККЕРА

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

Найти при

В терминах задачи Оптимальной точкой, очевидно, является тем не менее, как мы сейчас покажем, условия Куна — Таккера выполняются и при

Очевидно, условие 1 Куна — Таккера выполняется, так как точка. Теперь рассмотрим условия 2 и 3 Куна — Таккера в точке Для этого требуется найти и такие, что

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

Теорема достаточности. Докажем, что если целевая функция псевдовогнута и ограничения квазивогнуты, то условия Куна — Таккера — достаточные условия для оптимальности.

Теорема 2.15. Допустим, что в задаче НЛП с дифференцируемыми целевая функция псевдовогнута, а ограничения квазивогнуты. Предположим, что х удовлетворяет условиям Куна—Таккера. Тогда х — решение задачи НЛП.

Доказательство. Выберем любую допустимую точку Необходимо доказать, что

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

Условия Куна — Такера — это просто утверждение того, что для всех таких, что Но удовлетворяет требованиям , таким образом,

Из псевдовогнутости

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

в этом направлении, то упр. 18, где приведен связанный с этим и более общий результат.)

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

Categories

1
Оглавление
email@scask.ru