Нелинейное программирование
![]()
|
3.2. Интерпретация условий Куна — ТаккераДля того чтобы интерпретировать условия Куна — Таккера, рассмотрим задачу нелинейного программирования с ограничениями в виде равенств: минимизировать ![]() при ограничениях ![]() Запишем условия Куна—Таккера ![]() ![]() Далее рассмотрим функцию Лагранжа для задачи нелинейного программирования с ограничениями в виде равенств ![]() Для этой функции условия оптимальности первого порядка записываются в виде ![]() Нетрудно видеть, что условия Куна-Таккера (8) и (9) совпадают с условиями оптимальности первого порядка для задачи Лагранжа. Рассмотрим задачу нелинейного программирования с ограничениями в виде неравенств: минимизировать ![]() при ограничениях ![]() ![]() Запишем условия Куна—Таккера ![]() Соответствующая функция Лагранжа имеет вид ![]() Условия оптимальности первого порядка записываются как ![]() Заметим, что ![]() ![]() ![]() ![]() ![]() ![]() ![]() Если предположить, что ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Для того чтобы определить знак ![]() ![]() ![]() ![]() ![]() ![]() ![]() 3.3. Теоремы Куна—ТаккераВ предыдущем разделе построены условия Куна—Таккера для задач условной оптимизации. С помощью метода множителей Лагранжа получено интуитивное представление о том, что условия Куна — Танкера тесно связаны с необходимыми условиями оптимальности. В данном разделе рассматриваются строгие формулировки необходимых и достаточных условий оптимальности решения задачи нелинейного программирования. Теорема 1. Необходимость условий Куна—Таккера Рассмотрим задачу нелинейного программирования (0)-(2). Пусть ![]() ![]() ![]() ![]() ![]() Условие, согласно которому ![]() 1. Все ограничения в виде равенств и неравенств содержат линейные функции. 2. Все ограничения в виде неравенств содержат вогнутые функции, все ограничения-равенства — линейные функции, а также существует, по крайней мере, одна допустимая точка х, которая расположена во внутренней части области, определяемой ограничениями-неравенствами. Другими словами, существует такая точка х, что ![]() Если условие линейной независимости в точке оптимума не выполняется, то задача Куна—Таккера может не иметь решения. Пример 4 Минимизировать ![]() при ограничениях ![]() Решение. На рис.1 изображена область допустимых решений сформулированной выше нелинейной задачи. Ясно, что оптимальное решение этой задачи есть ![]() ![]() Рис.1 Допустимая область в задаче 4 Так как ![]() ![]() ![]() Запишем условия Куна—Таккера и проверим, выполняются ли они в точке (1, 0). Условия (3), (6) и (7) принимают следующий вид; ![]() ![]() ![]() ![]() ![]() ![]() При ![]() ![]() ![]() Заметим, что нарушение условия линейной независимости не обязательно означает, что точка Куна—Таккера не существует. Для того чтобы подтвердить это, заменим целевую функцию из этого примера функцией ![]() ![]() Нетрудно проверить, что точка ![]() Теорема о необходимости условий Куна—Таккера позволяет идентифицировать неоптимальные точки. Другими словами, теорему 1 можно использовать для доказательства того, что заданная допустимая точка, удовлетворяющая условию линейной независимости, не является оптимальной, если она не удовлетворяет условиям Куна—Таккера. С другой стороны, если в этой точке условия Куна—Таккера выполняются, то нет гарантии, что найдено оптимальное решение нелинейной задачи. В качестве примера рассмотрим следующую задачу нелинейного программирования. Следующая теорема устанавливает условия, при выполнении которых точка Куна—Таккера автоматически соответствует оптимальному решению задачи нелинейного программирования. Теорема.2 Достаточность условий Куна—Таккера Рассмотрим задачу нелинейного программирования (0) — (2). Пусть целевая функция ![]() ![]() ![]() ![]() Если условия теоремы 2 выполняются, то нахождение точки Куна—Таккера обеспечивает получение оптимального решения задачи нелинейного программирования. Теорему 2 можно также использовать для доказательства оптимальности данного решения задачи нелинейного программирования. В качестве иллюстрации опять рассмотрим пример: Минимизировать ![]() при ограничениях ![]() С помощью теоремы 2 докажем, что решение ![]() ![]() Так как матрица ![]() ![]() ![]() чтобы показать, что функция ![]() ![]() Поскольку матрица ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Точка ![]() ![]() Положив ![]() ![]() ![]() ![]() ![]() ![]() ![]() Замечания 1.Для встречающихся на практике задач условие линейной независимости, как правило, выполняется. Если в задаче все функции дифференцируемы, то точку Куна—Таккера следует рассматривать как возможную точку оптимума. Таким образом, многие из методов нелинейного программирования сходятся к точке Куна—Таккера. (Здесь уместно провести аналогию со случаем безусловной оптимизации, когда соответствующие алгоритмы позволяют определить стационарную точку.) 2. Если условия теоремы 2 выполнены, точка Куна—Таккера в то же время оказывается точкой глобального минимума. К сожалению, проверка достаточных условий весьма затруднительна, и, кроме того, прикладные задачи часто не обладают требуемыми свойствами. Следует отметить, что наличие хотя бы одного нелинейного ограничения в виде равенства приводит к нарушению предположений теоремы 2. 3.Достаточные условия, установленные теоремой 2, можно обобщить на случай задач с невыпуклыми функциями, входящими в ограничения в виде неравенств, невыпуклыми целевыми функциями и нелинейными ограничениями-равенствами. При этом используются такие обобщения выпуклых функций, как квазивыпуклые и псевдовыпуклые функции. |