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

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

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

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

Определение

А расслабление задачи минимизации

${displaystyle z=min{c(x):xin Xsubseteq mathbf {R} ^{n}}}$

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

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

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

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

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

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

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

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

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

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

Примечания

1. Джеффрион (1971)
2. Мурти, Катта Г. (1983). «16 итерационных методов для линейных неравенств и линейных программ (особенно 16.2 методов релаксации и 16.4 сохраняющих разреженность итерационных алгоритмов SOR для линейного программирования)». Линейное программирование. Нью-Йорк: John Wiley & Sons, Inc., стр. 453–464. ISBN  978-0-471-09725-9. МИСТЕР  0720547.
3. Гоффин, Ж.-Л. (1980). «Релаксационный метод решения систем линейных неравенств». Математика. Опер. Res. 5 (3): 388–414. Дои:10.1287 / moor.5.3.388. JSTOR  3689446. МИСТЕР  0594854.
4. Мину, М. (1986). Математическое программирование: теория и алгоритмы. Эгон Балас (предисловие) (Перевод Стивена Вайды из французского изд. (1983, Париж: Данод)). Чичестер: публикация Wiley-Interscience. John Wiley & Sons, Ltd., стр. Xxviii + 489. ISBN  978-0-471-90170-9. МИСТЕР  0868279. (Второе изд., 2008 г., на французском: Математическое программирование: теория и алгоритмы. Editions Tec & Doc, Париж, 2008. xxx + 711 с.. МИСТЕР2571910 )
5. Релаксационные методы нахождения допустимых решений систем линейных неравенств возникают в линейном программировании и лагранжевой релаксации. Гоффин (1980) Ошибка harvtxt: несколько целей (2 ×): CITEREFGoffin1980 (помощь) и Мину (1986) Ошибка harvtxt: несколько целей (2 ×): CITEREFMinoux1986 (помощь)| loc = Раздел 4.3.7, стр. 120–123 цитировать Шмуэль Агмон (1954), и Теодор Моцкин и Исаак Шенберг (1954) и Л. Т. Губин, Борис Т. Поляк, и Э. В. Райк (1969).

Рекомендации

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

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

• Немхаузер, Г. Л.; Rinnooy Kan, A.H.G .; Тодд, М. Дж., ред. (1989). Оптимизация. Справочники по исследованию операций и науке об управлении. 1. Амстердам: Издательство Северной Голландии, с. Xiv + 709. ISBN  978-0-444-87284-5. МИСТЕР  1105099.
  • W. R. Pulleyblank, Многогранная комбинаторика (стр. 371–446);
  • Джордж Л. Немхаузер и Лоуренс А. Уолси, Целочисленное программирование (стр. 447–527);
  • Клод Лемарешаль, Недифференцируемая оптимизация (стр. 529–572);
• Рардин, Рональд Л. (1998). Оптимизация исследования операций. Прентис Холл. ISBN  978-0-02-398415-0.
• Рубичек Т. (1997). Расслабление в теории оптимизации и вариационном исчислении. Берлин: Вальтер де Грюйтер. ISBN  978-3-11-014542-7.