Релаксация (приближение)

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

Например, линейного программирования ослабление задачи целочисленного программирования устраняет ограничение целочисленности и, таким образом, допускает нецелочисленные рациональные решения. Лагранжево ослабление сложной задачи комбинаторной оптимизации наказывает за нарушение некоторых ограничений, позволяя решить более легкую задачу. Методы релаксации дополняют или дополняют алгоритмы ветвей и границ комбинаторной оптимизации; линейное программирование и лагранжева релаксация используются для получения границ в алгоритмах ветвей и границ целочисленного программирования.

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

Определение

Ослабление проблемы минимизации

$z=\min\{c(x):x\in X\subseteq \mathbf {R} ^{n}\}$

это еще одна задача минимизации вида

$z_{R}=\min\{c_{R}(x):x\in X_{R}\subseteq \mathbf {R} ^{n}\}$

с этими двумя свойствами

1. $X_{R}\supseteq X$
2. $c_{R}(x)\leq c(x)$ для всех $x\in X$.

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

Свойства

Если $x^{*}$ является оптимальным решением исходной задачи, то $x^{*}\in X\subseteq X_{R}$ и $z=c(x^{*})\geq c_{R}(x^{*})\geq z_{R}$. Поэтому, $x^{*}\in X_{R}$ обеспечивает верхнюю границу $z_{R}$.

Если в дополнение к предыдущим предположениям $c_{R}(x)=c(x)$, $\forall x\in X$, справедливо следующее: если оптимальное решение ослабленной задачи допустимо для исходной задачи, то оно оптимально для исходной задачи.

Некоторые техники релаксации

• Релаксация линейного программирования
• Лагранжева релаксация
• Полуопределенное расслабление
• Суррогатное расслабление и двойственность

Ссылки

• Бутаццо, Г. (1989). Полунепрерывность, релаксация и интегральное представление в вариационном исчислении . Питман Рез. Заметки по математике. 207. Харлоу: Лонгманн.
• Джеффрион, AM (1971). «Двойственность в нелинейном программировании: упрощенная прикладно-ориентированная разработка». Обзор СИАМ . 13 (1): 1–37. JSTOR   2028848 .
• Гоффен, Ж.-Л. (1980). «Релаксационный метод решения систем линейных неравенств». Математика исследования операций . 5 (3): 388–414. дои : 10.1287/moor.5.3.388 . JSTOR   3689446 . МР   0594854 .
• Мину, М. (1986). Математическое программирование: Теория и алгоритмы . Чичестер: межнаучная публикация Wiley. Джон Уайли и сыновья. ISBN  978-0-471-90170-9 . МР   0868279 . Перевод Стивена Вайды с Математическое программирование: теория и алгоритмы . Париж: Дюнод. 1983. МР   2571910 .
• Мурти, Катта Г. (1983). «16 Итерационные методы для решения линейных неравенств и линейных программ (особенно 16.2 Методы релаксации и 16.4 Итеративные алгоритмы SOR, сохраняющие разреженность, для линейного программирования)». Линейное программирование . Нью-Йорк: Джон Уайли и сыновья. ISBN  978-0-471-09725-9 . МР   0720547 .
• Немхаузер, Г.Л .; Риннуй Кан, AHG; Тодд, М.Дж., ред. (1989). Оптимизация . Справочники по исследованию операций и науке управления. Том. издательства Северной Голландии. 1. Амстердам: ISBN  978-0-444-87284-5 . МР   1105099 .
  • WR Pulleyblank , Полиэдральная комбинаторика (стр. 371–446);
  • Джордж Л. Немхаузер и Лоуренс А. Уолси, Целочисленное программирование (стр. 447–527);
  • Клод Лемарешаль , Недифференцируемая оптимизация (стр. 529–572);
• Рардин, Рональд Л. (1998). Оптимизация в исследовании операций . Прентис Холл. ISBN  978-0-02-398415-0 .
• Рубичек, Т. (1997). Релаксация в теории оптимизации и вариационном исчислении . Берлин: Вальтер де Грюйтер. ISBN  978-3-11-014542-7 .