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

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

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

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

Определение [ править ]

Релаксации задачи минимизации

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

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

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

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

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

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

Свойства [ править ]

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

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

Некоторые техники релаксации [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Дж. Буттаццо (1989). Полунепрерывность, релаксация и интегральное представление в вариационном исчислении . Pitman Res. Заметки по математике. 207. Харлоу: Лонгманн.

• Джеффрион AM (1971). «Двойственность в нелинейном программировании: упрощенная разработка, ориентированная на приложения». SIAM Обзор . 13 (1). С. 1–37. JSTOR  2028848 ..
• Гоффин, Ж.-Л. (1980). «Релаксационный метод решения систем линейных неравенств». Математика. Опер. Res . 5 (3): 388–414. DOI : 10.1287 / moor.5.3.388 . JSTOR  3689446 . Руководство по ремонту  0594854 .
• Мину, М. (1986). Математическое программирование: теория и алгоритмы ((с предисловием Эгона Баласа) Перевод Стивена Вайды из французского изд. (1983 Paris: Dunod). Чичестер: публикация Wiley-Interscience. John Wiley & Sons, Ltd., стр. Xxviii + 489. ISBN 978-0-471-90170-9. Руководство по ремонту  0868279 . (Второе издание, 2008 г., на французском языке: Математическое программирование: Теория и алгоритмы . Издания Tec & Doc, Париж, 2008 г. xxx + 711 с. CS1 maint: discouraged parameter (link). MR 2571910 ) |

• Nemhauser, GL ; Ринну Кан, AHG; Тодд, MJ , ред. (1989). Оптимизация . Справочники по исследованию операций и науке об управлении. 1 . Амстердам: North-Holland Publishing Co., стр. Xiv + 709. 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.