Разрыв в двойственности
-
Определение разрыва в двойственности
- Разрыв в двойственности — это разница между первичным и двойственным решениями в задачах оптимизации.
- Если d∗ — оптимальное двойное значение, а p∗ — оптимальное начальное значение, разрыв равен p∗ — d∗.
- Разрыв всегда больше или равен 0 для задач минимизации и равен 0 при сильной двойственности.
-
Общая теория двойственности
- Рассматриваются две двойственные пары пространств (X, X∗) и (Y, Y∗).
- Функция f: X → R∪{+∞} может быть расширена с учетом ограничений, что приводит к функции F: X × Y → R∪{+∞}.
- Разрыв в двойственности определяется как разница между F∗ и f.
-
Вычислительная оптимизация
- В вычислительной оптимизации существует альтернативный «разрыв в двойственности», который измеряет разницу между двойственным решением и значением неоптимальной итерации.
- Этот разрыв количественно определяет расхождение между текущим неоптимальным решением и оптимальным значением двойной задачи.
-
Рекомендации
- В статье приведены рекомендации по использованию разрыва в двойственности в задачах оптимизации.