Лагранжева релаксация

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

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

Задача максимизации лагранжевой функции двойственных переменных (лагранжевых множителей) является лагранжевой двойственной задачей.

• 1 Математическое описание
• 2 Решение LR как граница
• 3 Переход к решению исходной задачи
• 4 Связанные методы
• 5 Ссылки
  • 5.1 Книги
  • 5.2 Статьи

Предположим, нам дан задача линейного программирования с $x\; \in \; R\; n\; \{\backslash \; displaystyle\; x\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{n\}\}$и $A\; \in \; R\; m,\; n\; \{\; \backslash \; displaystyle\; A\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{m,\; n\}\}$следующего вида:

max		$c\; T\; x\; \{\backslash \; displaystyle\; c\; ^\; \{T\}\; x\}$
ул
		$A\; x\; \le \; b\; \{\backslash \; displaystyle\; Ax\; \backslash \; leq\; b\}$

Если мы разделим ограничения в $A\; \{\backslash \; displaystyle\; A\}$так, чтобы $A\; 1\; \in \; R\; m\; 1\; п\; \{\backslash \; displaystyle\; A\_\; \{1\}\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{m\_\; \{1\},\; n\}\}$, $A\; 2\; \in \; R\; m\; 2,\; n\; \{\backslash \; displaystyle\; A\_\; \{2\}\; \backslash \; in\; \backslash \; mathbb\; \{R\; \}\; ^\; \{m\_\; \{2\},\; n\}\}$и $m\; 1\; +\; m\; 2\; =\; m\; \{\backslash \; displaystyle\; m\_\; \{1\}\; +\; m\_\; \{2\}\; =\; m\}$мы может записать систему:

max		$c\; T\; x\; \{\backslash \; displaystyle\; c\; ^\; \{T\}\; x\}$
st
(1)		$A\; 1\; x\; \le \; b\; 1\; \{\backslash \; displaystyle\; A\_\; \{1\}\; x\; \backslash \; leq\; b\_\; \{1\}\}$
(2)		$A\; 2\; x\; \le \; b\; 2\; \{\backslash \; displaystyle\; A\_\; \{\; 2\}\; x\; \backslash \; leq\; b\_\; \{2\}\}$

Мы можем ввести ограничение (2) в цель:

max		$c\; T\; x\; +\; \lambda \; T\; (b\; 2\; -\; A\; 2\; x)\; \{\backslash \; displaystyle\; c\; ^\; \{T\}\; x\; +\; \backslash \; lambda\; ^\; \{T\}\; (b\_\; \{2\}\; -A\_\; \{2\}\; x)\}$
ул.
(1)		$A\; 1\; x\; \le \; b\; 1\; \{\backslash \; displaystyle\; A\_\; \{1\}\; x\; \backslash \; leq\; b\_\; \{1\}\}$

Если мы допустим $\lambda \; =\; (\lambda \; 1,\dots ,\; \lambda \; m\; 2)\; \{\backslash \; displaystyle\; \backslash \; lambda\; =\; (\backslash \; lambda\; \_\; \{1\},\; \backslash \; ldots,\; \backslash \; lambda\; \_\; \{m\_\; \{2\}\})\}$быть неотрицательными весами, мы штрафуемся, если нарушаем ограничение (2), и мы также будем вознаграждены, если строго соблюдаем ограничение. Вышеупомянутая система называется лагранжевой релаксацией нашей исходной задачи.

В частности, используется свойство, которое для любого фиксированного набора $\lambda \; ~\; \{\backslash \; displaystyle\; \{\backslash \; tilde\; \{\backslash \; lambda\}\}\}$, оптимальный результат для задачи лагранжевой релаксации будет не меньше, чем оптимальный результат для исходной задачи. Чтобы убедиться в этом, пусть $x\; ^\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{x\}\}\}$будет оптимальным решением исходной задачи, и пусть $x\; ¯\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{\; x\}\}\}$- оптимальное решение лагранжевой релаксации. Тогда мы можем видеть, что

$c\; T\; x\; ^\; \le \; c\; T\; x\; ^\; +\; \lambda \; ~\; T\; (b\; 2\; -\; A\; 2\; x\; ^)\; \le \; c\; T\; x\; ¯\; +\; \lambda \; ~\; T\; (b\; 2\; -\; A\; 2\; x\; ¯)\; \{\backslash \; displaystyle\; c\; ^\; \{T\}\; \{\backslash \; hat\; \{x\}\}\; \backslash \; leq\; c\; ^\; \{T\}\; \{\backslash \; hat\; \{x\}\}\; +\; \{\backslash \; tilde\; \{\backslash \; lambda\}\}\; ^\; \{T\}\; (b\_\; \{2\}\; -A\_\; \{2\}\; \{\backslash \; hat\; \{x\}\})\; \backslash \; leq\; c\; ^\; \{T\}\; \{\backslash \; bar\; \{x\}\}\; +\; \{\backslash \; tilde\; \{\backslash \; lambda\}\}\; ^\; \{T\}\; (b\_\; \{2\}\; -A\_\; \{2\}\; \{\backslash \; bar\; \{x\; \}\})\}$

Первое неравенство верно, потому что $x\; ^\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{x\}\}\}$выполнимо в исходной задаче, а второе неравенство верно, потому что $x\; ¯\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{x\}\}\}$- оптимальное решение лагранжевой релаксации.

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

min

$P\; (\lambda )\; \{\backslash \; displaystyle\; P\; (\backslash \; lambda)\}$

s.t.

$\lambda \; \ge \; 0\; \{\backslash \; displaystyle\; \backslash \; lambda\; \backslash \; geq\; 0\}$

где мы определяем $P\; (\lambda )\; \{\backslash \; displaystyle\; P\; (\backslash \; lambda)\}$как

max		$c\; T\; x\; +\; \lambda \; T\; (b\; 2\; -\; A\; 2\; x)\; \{\backslash \; displaystyle\; c\; ^\; \{T\}\; x\; +\; \backslash \; lambda\; ^\; \{T\}\; (b\_\; \{2\}\; -A\_\; \{2\}\; x)\}$
ул.
(1)		$A\; 1\; x\; \le \; b\; 1\; \{\backslash \; displaystyle\; A\_\; \{1\}\; x\; \backslash \; leq\; b\_\; \{1\}\}$

Таким образом, алгоритм лагранжевой релаксации переходит к исследованию диапазона возможных $\lambda \; \{\; \backslash \; displaystyle\; \backslash \; lambda\}$, пытаясь минимизировать результат, возвращаемый внутренней проблемой $P\; \{\backslash \; displaystyle\; P\}$. Каждое значение, возвращаемое параметром $P\; \{\backslash \; displaystyle\; P\}$, является потенциальной верхней границей проблемы, наименьшее из которых сохраняется в качестве наилучшей верхней границы. Если мы дополнительно используем эвристику, возможно, засеянную значениями $x\; ¯\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{x\}\}\}$, возвращаемыми $P\; \{\backslash \; displaystyle\; P\}$, чтобы найти возможные решения исходной проблемы, затем мы можем выполнять итерацию до тех пор, пока лучшая верхняя граница и стоимость наилучшего допустимого решения не сойдутся до желаемого допуска.

расширенный лагранжев метод по духу очень похож на метод лагранжевой релаксации, но добавляет дополнительный член и обновляет двойные параметры $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$более принципиальным образом. Он был представлен в 1970-х годах и широко использовался.

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

Книги

• Равиндра К. Ахуджа, Томас Л. Магнанти и Джеймс Б. Орлин (1993). Сетевые потоки: теория, алгоритмы и приложения. Прентис Холл. ISBN 0-13-617549-X. CS1 maint: несколько имен: список авторов (ссылка )
• Берцекас, Дмитрий П. (1999). Нелинейный Программирование: 2-е издание. Athena Scientific. ISBN 1-886529-00-0.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Численная оптимизация: теоретические и практические аспекты. Universitext (Второе исправленное издание перевода французского издания 1997 года). Берлин: Springer -Verlag. Pp. Xiv + 490. doi : 10.1007 / 978-3-540-35447-5. ISBN 3-540-35445 -X. MR 2265882.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Выпуклый анализ и алгоритмы минимизации, Том I: Основы. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Наук]. 305 . Berlin: Springer-Verlag. Pp. Xviii + 417. ISBN 3-540-56850-6. MR 1261420.
• Hiriart-Urruty, Жан-Батист; Лемарешаль, Клод (1993). «14 двойственности для практикующих». Выпуклый анализ и алгоритмы минимизации, Том II: Расширенная теория и методы связки. Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 306 . Берлин: Springer-Verlag. С. xviii + 346. ISBN 3-540-56852-2.
• Ласдон, Леон С. (2002). Теория оптимизации для больших систем (переиздание 1970 Macmillan ed.). Минеола, Нью-Йорк: Dover Publications, Inc., стр. Xiii + 523. MR 1888251. CS1 maint: ref = harv (link )
• Lemaréchal, Claude (2001). «Лагранжианская релаксация». У Михаэля Юнгера и Дениса Наддефа (ред.) Вычислительная комбинаторная оптимизация: доклады весенней школы, прошедшей в Шлос-Дагштуле, 15–19 мая 2000 г. Лекционные заметки по компьютерным наукам. 2241 . Берлин: Springer-Verlag, стр. 112–156. doi : 10.1007 / 3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016. CS1 maint: ref = harv (ссылка )
• (1986). Математическое программирование: теория и алгоритмы. Эгон Балас (предисловие) (Перевод Стивена Вайды из французского изд. (1983 Paris: Dunod)). Чичестер: Публикация Wiley-Interscience. John Wiley Sons, Ltd., стр. Xxviii + 489. ISBN 0-471-90170-9. MR 0868279. (Второе издание 2008 г., на французском: Математическое программирование: Теория и алгоритмы. Издания Tec Doc, Париж, 2008. xxx + 711 стр.). CS1 maint: ref = harv (ссылка )

Статьи

• Эверетт, Хью, III (1963). "Generaliz под ред. Метод множителей Лагранжа для решения задач оптимального распределения ресурсов ». Исследование операций. 11 (3): 399–417. doi : 10.1287 / opre.11.3.399. JSTOR 168028. MR 0152360. CS1 maint: ref = harv (ссылка )
• Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, PO ( Август 2007 г.). «Лагранжева релаксация с помощью методов шарикового субградиента». Математика исследования операций. 32 (3): 669–686. doi : 10.1287 / moor.1070.0261. MR 2348241. CS1 maint: ref = harv (ссылка )