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

Relaxation (approximation)

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

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

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

Определение

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

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

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

  1. для всех .

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

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

Если оптимальное решение исходной задачи, то и . Следовательно, обеспечивает верхнюю границу .

Если в дополнение к предыдущим предположениям, , , выполняется следующее: если оптимальное решение релаксированной задачи возможно для исходной задачи, то оно оптимально для исходной задачи.[1]

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

Примечания

  1. ^ а б c Джеффрион (1971)
  2. ^ Мурти, Катта Г. (1983). «16 итерационных методов для линейных неравенств и линейных программ (особенно 16.2 методов релаксации и 16.4 сохраняющих разреженность итерационных алгоритмов SOR для линейного программирования)». Линейное программирование. Нью-Йорк: John Wiley & Sons, Inc., стр. 453–464. ISBN 978-0-471-09725-9. МИСТЕР 0720547.CS1 maint: ref = harv (связь)
  3. ^ Гоффин, Ж.-Л. (1980). «Релаксационный метод решения систем линейных неравенств». Математика. Опер. Res. 5 (3): 388–414. Дои:10.1287 / moor.5.3.388. JSTOR 3689446. МИСТЕР 0594854.CS1 maint: ref = harv (связь)
  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 с.CS1 maint: ref = harv (связь). МИСТЕР2571910)
  5. ^ Релаксационные методы нахождения допустимых решений систем линейных неравенств возникают в линейном программировании и лагранжевой релаксации. Гоффин (1980) и Мину (1986)| loc = Раздел 4.3.7, стр. 120–123 цитировать Шмуэль Агмон (1954), и Теодор Моцкин и Исаак Шенберг (1954) и Л. Т. Губин, Борис Т. Поляк, и Э. В. Райк (1969).

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

  • Дж. Буттаццо (1989). Полунепрерывность, релаксация и интегральное представление в вариационном исчислении. Pitman Res. Заметки по математике. 207. Харлоу: Лонгманн.
  • Джеффрион, А. М. (1971). "Двойственность в нелинейном программировании: упрощенная разработка, ориентированная на приложения". SIAM Обзор. 13 (1). С. 1–37. JSTOR 2028848.CS1 maint: ref = harv (связь).
  • Гоффин, Ж.-Л. (1980). «Релаксационный метод решения систем линейных неравенств». Математика. Опер. Res. 5 (3): 388–414. Дои:10.1287 / moor.5.3.388. JSTOR 3689446. МИСТЕР 0594854.CS1 maint: ref = harv (связь)
  • Мину, М. (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 с.CS1 maint: ref = harv (связь). МИСТЕР2571910)|
  • Немхаузер, Г. Л.; Rinnooy Kan, A.H.G .; Тодд, М. Дж., ред. (1989). Оптимизация. Справочники по исследованию операций и науке об управлении. 1. Амстердам: Издательство Северной Голландии, с. Xiv + 709. ISBN 978-0-444-87284-5. МИСТЕР 1105099.CS1 maint: ref = harv (связь)
    • W. R. Pulleyblank, Многогранная комбинаторика (стр. 371–446);
    • Джордж Л. Немхаузер и Лоуренс А. Уолси, Целочисленное программирование (стр. 447–527);
    • Клод Лемарешаль, Недифференцируемая оптимизация (стр. 529–572);
  • Рардин, Рональд Л. (1998). Оптимизация исследования операций. Прентис Холл. ISBN 978-0-02-398415-0.
  • Рубичек Т. (1997). Расслабление в теории оптимизации и вариационном исчислении. Берлин: Вальтер де Грюйтер. ISBN 978-3-11-014542-7.