Введение

Принцип математической оптимизации

В теории математической оптимизации дуальность, или принцип дуальности, – это принцип, согласно которому задачи оптимизации можно рассматривать с двух точек зрения: как прямую задачу или как двойственную задачу. Если прямая задача является задачей минимизации, то двойственная задача является задачей максимизации (и наоборот). Любое допустимое решение прямой (минимизационной) задачи не меньше, чем любое допустимое решение двойственной (максимизационной) задачи. Следовательно, решение прямой задачи является верхней границей решения двойственной задачи, а решение двойственной задачи – нижней границей решения прямой задачи. Этот факт называется слабой дуальностью. В общем случае оптимальные значения прямой и двойственной задач не обязаны быть равными. Их разность называется зазором дуальности. Для задач выпуклой оптимизации зазор дуальности равен нулю при выполнении условия квалификации ограничений. Этот факт называется сильной дуальностью.

Пробел в дуальности

Разрыв двойственности — это разница между значениями любого допустимого решения исходной задачи и любого допустимого решения двойственной задачи. Если — оптимальное значение двойственной задачи, а — оптимальное значение исходной задачи, то разрыв двойственности равен . Это значение всегда больше или равно 0 (для задач минимизации). Разрыв двойственности равен нулю тогда и только тогда, когда выполняется сильная двойственность. В противном случае разрыв строго положителен, и выполняется слабая двойственность. В вычислительной оптимизации часто сообщают о другом "разрыве двойственности", который представляет собой разницу между значением двойственного решения и значением допустимой, но неоптимальной итерации для исходной задачи. Этот альтернативный "разрыв двойственности" количественно определяет расхождение между значением текущей допустимой, но неоптимальной итерации исходной задачи и значением двойственной задачи; при выполнении условий регулярности значение двойственной задачи равно значению выпуклой оболочки исходной задачи: выпуклая оболочка — это задача, получаемая заменой невыпуклого допустимого множества его замкнутой выпуклой оболочкой и заменой невыпуклой функции ее выпуклым замыканием, то есть функцией, эпиграф которой является замкнутой выпуклой оболочкой исходной целевой функции.

Линейный случай

Линейные задачи программирования – это задачи оптимизации, в которых целевая функция и ограничения являются линейными. В исходной задаче целевая функция представляет собой линейную комбинацию n переменных. Существует m ограничений, каждое из которых задает верхнюю границу для линейной комбинации n переменных. Цель состоит в максимизации значения целевой функции при заданных ограничениях. Решение – это вектор (список) из n значений, который обеспечивает максимальное значение целевой функции. В двойственной задаче целевая функция является линейной комбинацией m значений, представляющих собой границы в m ограничениях исходной задачи. Существует n двойственных ограничений, каждое из которых задает нижнюю границу для линейной комбинации m двойственных переменных.

Связь между первичной проблемой и двойной проблемой

В линейном случае, в исходной задаче, от каждой субоптимальной точки, удовлетворяющей всем ограничениям, существует направление или подпространство направлений, вдоль которых можно двигаться, чтобы увеличить целевую функцию. Движение в любом из этих направлений считается устранением зазора между текущим решением-кандидатом и одним или несколькими ограничениями. Недопустимым значением решения-кандидата является значение, которое нарушает одно или несколько ограничений. В двойственной задаче двойственный вектор умножает ограничения, определяющие положение ограничений в исходной задаче. Изменение двойственного вектора в двойственной задаче эквивалентно изменению верхних границ в исходной задаче. Ищется наименьшая верхняя граница. То есть, двойственный вектор минимизируется для устранения зазора между предполагаемыми положениями ограничений и фактическим оптимумом. Недопустимым значением двойственного вектора является слишком низкое значение. Оно устанавливает предполагаемые положения одного или нескольких ограничений таким образом, что исключает фактический оптимум. Эта интуиция формализуется уравнениями в линейном программировании: Двойственность.

Нелинейный случай

В нелинейном программировании ограничения не обязательно являются линейными. Тем не менее, многие из тех же принципов остаются применимыми. Для того чтобы обеспечить возможность легкой идентификации глобального максимума нелинейной задачи, при ее формулировке часто требуется, чтобы функции были выпуклыми и имели компактные нижние множества уровней. В этом заключается значимость условий Каруша — Куна — Таккера. Они предоставляют необходимые условия для определения локальных оптимумов в задачах нелинейного программирования. Существуют дополнительные условия (условия регулярности), необходимые для определения направления к оптимальному решению. Оптимальное решение – это решение, являющееся локальным оптимумом, но необязательно глобальным.

История

Согласно Джорджу Данцигу, теорема о двойственности для линейной оптимизации была предположена Джоном фон Нейманом сразу после того, как Данциг представил задачу линейного программирования. Фон Нейман отметил, что он опирался на сведения из своей теории игр, и предположил, что двухперсональная матричная игра с нулевой суммой эквивалентна задаче линейного программирования. Строгие доказательства были впервые опубликованы в 1948 году Альбертом В. Таккером и его коллегами. (Предисловие Данцига к книге Неринга и Таккера, 1993)

Приложения

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

Статьи

Дуальность в линейном программировании Гари Д. Кнотт