Теория двойственности и недифференциальные условия оптимальности в задаче выпуклого программирования
В задачах математического программирования (1.4)—(1.6) можно указать условия оптимальности, не прибегая к понятиям производных и градиентов, с помощью так называемой теории двойственности. Особенно плодотворен этот подход в задачах выпуклого программирования.
Будем рассматривать функцию Лагранжа (1.7). Обозначим через 
точную нижнюю грань целевой функции задачи (1.4)—(1.6) на ее допустимом множестве 
. Точка 
является решением задачи (1.4)-(1.6) в том и только в том случае, если 
.
Введем вектор 
с координатами
Вектор 
называется вектором Куна-Таккера задачи (1.4)—(1.6), если при всех 
Любой задаче математического программирования можно поставить в соответствие так называемую двойственную задачу оптимизации. Между прямой и двойственной задачами имеются полезные связи.
Двойственной к задаче (1.4) — (1.6) называют задачу
где
Рассмотрим подробнее задачу линейного программирования
Переменные 
могут иметь любые значения. Функция Лагранжа этой задачи
Согласно определению двойственности, двойственной задачей к исходной задаче является следующая:
Исходную задачу называют прямой. Если целевую функцию в двойственной задаче 
заменить на —
, то можно утверждать, что задача, двойственная к произвольной задаче математического программирования, всегда выпукла. Если в задаче математического программирования множество замкнуто и выпукло, функции 
, непрерывны и выпуклы на 
, функции 
линейны или отсутствуют и решение прямой задачи конечно 
, в частности она имеет решение, то множество решений двойственной задачи непусто и совпадает с множеством векторов Куна-Таккера прямой задачи. При этом справедливо соотношение двойственности 
, т.е. минимум целевой функции прямой задачи совпадает с максимумом целевой функции двойственной задачи. Учитывая, что число переменных в двойственной задаче равно числу условий-ограничений в прямой задаче, в ряде случаев двойственную задачу решить проще.
Получим необходимые и достаточные условия оптимальности в задаче выпуклого программирования на основе теории двойственности. В этом случае изменится только форма необходимых и достаточных условий (не будут участвовать производные), но предпосылки в обоих случаях будут одинаковы.
Для примера рассмотрим задачу квадратического программирования:
при
где 
— положительно определенная симметрическая матрица размерностью
заданные векторы из
заданные числа.
Функция Лагранжа задачи
Задача, двойственная к исходной
Для положительно определенной матрицы Спроизводная функции Лагранжа
в точке
и двойственная задача записывается в виде
Полученная функция квадратична — условия неотрицательности относятся к первым к переменным. Решить двойственную задачу гораздо проще. Если же в исходной задаче нет ограничений неравенств, то двойственная задача приводит к безусловной оптимизации квадратичной функции.
Пара 
называется седловой точкой функции
Тогда точка 
является решением прямой задачи в том и только в том случае, если существует вектор 
такой, что пара 
— седловая точка функции Лагранжа 
на 
. Таким образом, если одновременно решать и прямую и двойственную задачи, то к точке минимума (т.е. к решению) мы можем приближаться с двух сторон.
Вектору Куна-Таккера часто придают экономические интерпретации. Рассмотрим две из них. Пусть предприятие выпускает некую продукцию и стремится получить максимальный доход. Условия-ограничения в виде неравенств характеризуют затраты ресурсов при выпуске продукции. Очевидно, что в процессе ее выпуска один или несколько ресурсов будут исчерпаны полностью. Для нас это активные ограничения. Другая часть ресурсов будет не использована (пассивные ограничения). В двойственной задаче (согласно условию дополняющей нежесткости) для активных ограничений множители
а для пассивных ограничений
(эти ресурсы недефицитны). То есть предприятию следует закупать в первую очередь те ресурсы, для которых
имеют наибольшее значение. Если же есть возможность увеличивать количество всех ресурсов сразу, то их желательно приобретать в пропорциях, описываемых вектором Куна-Таккера.
В иной интерпретации предприятие хочет продать «ненужную» часть сырья и установить за него такую цену, чтобы максимизировать общий доход. Пусть вектор с — заданный вектор цен на сырье. Предприятие стремится продать сырье по таким ценам, чтобы получить такую же прибыль, как в случае, когда из проданного сырья изготовлена продукция, а для этого цены с должны быть назначены равными координатам вектора Куна-Таккера .
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны:
