ДВОЙСТВЕННАЯ ЗАДАЧА ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ.

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

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

Задачи (1) и (2) эквивалентны и если только исходная задача имеет решение. В противном случае . Двойственной к задаче (1) является задача отыскания

Для формулировки теоремы двойственности необходимо ввести следующее обобщение задачи (1)

Если мн-во планов (решений) задачи (1) либо (4) пусто, то величины и либо соответственно следует положить равными — . При этом всегда Если — выпуклые функции (кверху), R — выпуклое множество, т. е. задача (1) является задачей программирования выпуклого, то выполняется равенство . Т. о., для задачи выпуклого программирования справедлива следующая теорема. Задача (1) и задача (3) связаны соотношением двойственности в том и только в том случае, если переход от исходной задачи (1) к обобщенной исходной задаче (4) не ведет к возрастанию верхней грани (1), т. е. Эту теорему наз. теоремой двойственности.

Известно несколько условий, достаточных для выполнения соотношения двойственности : 1) ф-ции — выпуклы вверх и непрерывны на замкнутом выпуклом мн-ве R, мн-во G планов задачи (1) непусто и ограничено. При этом верхняя грань в прямой задаче (1) достигается при хотя нижняя грань в двойственной задаче (3) может и не достигаться. 2) Ф-ции f {х), gt (х) выпуклы (вверх), мн-во R выпукло и выполняется условие Слейтера: существует план задачи (1) такой, что . Это условие исключает наличие в задаче условий в виде равенств. Однако для задаче , где

линейные ф-ции, имеет место обобщение условия Слейтера, состоящее в том, что существует такой план что где — внутр. точка мн-ва R. При этом нижняя грань в двойственной задаче при достигается для некоторого Я. Однако верхняя грань в исходной задаче может и не достигаться. 3) Ф-ция выпуклая (вверх) кусочно-гладкая, ф-ции выпуклые (вверх) кусочно-линейные, R — выпуклое многогранное мн-во и мн-во планов задачи (1) непусто. При этом в случае при некоторых

Пара двойственных задач (1) и (3) тесно связана с задачей отыскания седловой точки ф-ции Лагранжа Эту связь видно из следующей теоремы. Для существования седловой точки ф-ции Лагранжа при необходимо и достаточно, чтобы задачи (1) и (3) были связаны соотношением двойственности и имели в качестве решений некоторые точки При этом любая пара решений двойственных задач составляет седловую точку ф-ции и, обратно, седловая точка ф-ции определяет решения и X задач (1) и (3) соответственно. Т. о., эта теорема позволяет сводить решение задачи (1) к нахождению седловой точки ф-ции Лагранжа в области если эта точка существует.

Для составления двойственной задачи необходимо найти ф-цию

Эта ф-ция выпукла книзу. В самом деле, если любая пара точек -мерного простр., то при

Следовательно, двойственная задача является задачей выпуклого программирования для общей задачи матем. программирования. Так как всегда v и, то решение двойственной задачи дает оценку сверху глобального максимума (см. Экстремум глобальный) многоэкстремальной задачи (1).

Проиллюстрируем на конкретном примере составление двойственной задачи. Пусть исходная задача где постоянный вектор, а матрица размера . Найдем ф-цию , где вектор размерности , как

Здесь А — матрица, транспонированная А. Итак, двойственной задачей к исходной является задача

В. П. Гуленко.