Выпуклое программирование
Лекции.Орг

Поиск:


Выпуклое программирование




Общая задача выпуклого программирования имеет вид

(6.4.1)

где – выпуклые функции, – выпуклое множество.

Будем обозначать – область определения функции, т.е. множество на котором функция определена, а за его пределами не определена.

Условия экстремума. Необходимые и достаточные условия задачи (6.4.1) сформулированы в следующей теореме.

Теорема 17 (Кун-Таккер). Пусть , i=1,…,m, – выпуклые функции, – выпуклое множество, входящее в области определения функций и выполняется условие Слейтера: найдется такое, что

(6.4.2)

Тогда допустимая точка является глобальным решением (6.4.1), если и только если найдутся такие, что:

и (6.4.3)

, (6.4.4)

где и

, (6.4.5)

Как и ранее функцию будем называть функцией Лагранжа, вектор множителями Лагранжа, прямыми переменными, двойственными переменными, условие условием дополняющей нежесткости, набор индексов множеством активных ограничений. Если для задачи (6.4.1) выполнены условия теоремы 1, то будем говорить о регулярной точке минимумаили регулярной задаче.

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

Пусть – два множества. Пара называется седловой точкой функции на , если

(6.4.6)

т.е. точка является точкой минимума по на , а – точкой максимума по на . Выражение (6.4.6) эквивалентно равенству

. (6.4.7)

Наличие седловой точки означает возможность перестановки операций минимума и максимума.

Теорема 18 (Кун-Таккер). В условиях теоремы 1 является решением задачи (6.4.1) тогда и только тогда, когда пара при некотором является седловой точкой на , т.е.

(6.4.8)

Двойственность. Симметрия относительно переменных и в (6.4.8) для задачи минимизации (6.4.1) по позволяет наедятся найти экстремальную задачу относительно переменных для которой также справедливы условия (6.4.8). Введем функцию

(6.4.9)

Поэтому исходная задача (6.4.1) может быть записана

. (6.4.10)

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

(6.4.11)

(возможно, что при некоторых ) и рассмотрим задачу

. (6.4.12)

Задача (6.4.12) называется двойственной, а (6.4.1) или (6.4.10) – прямой.

Теорема 19 (теорема двойственности). Справедливы соотношения двойственности:

а) Для любых допустимых и (т.е. для )

. (6.4.13)

б) Если прямая задача регулярна, – ее решение, – множители Лагранжа, то – решение (6.4.12) и

. (6.4.14)

в) Если для допустимых, , имеет место (6.4.14), то – решение прямой, а – решение двойственной задачи.

Максимум y(y) может достигаться лишь в точках, где . Поэтому (6.4.12) равносильна задаче

(6.4.15)

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

Единственность решения (6.4.1) гарантируется строгой выпуклостью функции .





Дата добавления: 2015-02-12; просмотров: 489 | Нарушение авторских прав | Изречения для студентов


Читайте также:

Рекомендуемый контект:


Поиск на сайте:



© 2015-2020 lektsii.org - Контакты - Последнее добавление

Ген: 0.006 с.