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

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

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

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

Определение

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

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}\}

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

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

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

Характеристики

Если $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$ , справедливо следующее: если оптимальное решение ослабленной задачи допустимо для исходной задачи, то оно оптимально для исходной задачи. ^[1]

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

Примечания

^ Релаксационные методы поиска допустимых решений систем линейных неравенств возникают в линейном программировании и лагранжевой релаксации. ^[2]^[5]^[6]^[7]^[8]

^ Jump up to: ^а ^б ^с Джеффрион (1971)
^ Jump up to: ^а ^б Гоффен (1980) .
^ Мурти (1983) , стр. 453–464.
^ Мину (1986) .
^ Мину (1986) , раздел 4.3.7, стр. 120–123.
^ Шмуэль Агмон (1954)
^ Теодор Моцкин и Исаак Шенберг (1954)
^ L. T. Gubin, Boris T. Polyak, and E. V. Raik (1969)

Ссылки

Бутаццо, Г. (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 .

[9] Релаксационные методы поиска допустимых решений систем линейных неравенств возникают в линейном программировании и лагранжевой релаксации. ^[2]^[5]^[6]^[7]^[8]

[Geoff-1] Jump up to: ^а ^б ^с Джеффрион (1971)

[FOOTNOTEGoffin1980-2] Jump up to: ^а ^б Гоффен (1980) .

[FOOTNOTEMurty1983453–464-3] Мурти (1983) , стр. 453–464.

[FOOTNOTEMinoux1986-4] Мину (1986) .

[FOOTNOTEMinoux1986Section_4.3.7,_pp._120–123-5] Мину (1986) , раздел 4.3.7, стр. 120–123.

[6] Шмуэль Агмон (1954)

[7] Теодор Моцкин и Исаак Шенберг (1954)

[8] L. T. Gubin, Boris T. Polyak, and E. V. Raik (1969)

[1]

[2]

[3]

[4]

[а]

[5]

[6]

[7]

[8]