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

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

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

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

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

макс		${\displaystyle c^{T}x}$
ул
		${\displaystyle Ax\leq b}$

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

макс		${\displaystyle c^{T}x}$
ул
(1)		${\displaystyle A_{1}x\leq b_{1}}$
(2)		${\displaystyle A_{2}x\leq b_{2}}$

Мы можем ввести ограничение (2) в задачу:

макс		${\displaystyle c^{T}x+\lambda ^{T}(b_{2}-A_{2}x)}$
ул
(1)		${\displaystyle A_{1}x\leq b_{1}}$

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

Особое применение имеет свойство, что для любого фиксированного набора значений оптимальный результат для задачи релаксации Лагранжа будет не меньше оптимального результата для исходной задачи. Чтобы увидеть это, пусть будет оптимальным решением исходной задачи, а пусть будет оптимальным решением релаксации Лагранжа. Тогда мы можем увидеть, что ${\displaystyle {\tilde {\lambda }}\succeq 0}$${\displaystyle {\хэт {x}}}$${\displaystyle {\bar {x}}}$

${\displaystyle c^{T}{\hat {x}}\leq c^{T}{\hat {x}}+{\tilde {\lambda }}^{T}(b_{2}-A_{2}{\hat {x}})\leq c^{T}{\bar {x}}+{\tilde {\lambda }}^{T}(b_{2}-A_{2}{\bar {x}})}$

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

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

мин

${\displaystyle P(\лямбда)}$

ул

${\displaystyle \lambda \geq 0}$

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

макс		${\displaystyle c^{T}x+\lambda ^{T}(b_{2}-A_{2}x)}$
ул
(1)		${\displaystyle A_{1}x\leq b_{1}}$

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

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

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

• Равиндра К. Ахуджа , Томас Л. Магнанти и Джеймс Б. Орлин (1993). Сетевые потоки: теория, алгоритмы и приложения . Prentice Hall. ISBN 0-13-617549-X.{{cite book}}: 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. стр. xiv+490. doi :10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. МР  2265882.
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). Алгоритмы выпуклого анализа и минимизации, Том I: Основы . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. Том. 305. Берлин: Springer-Verlag. стр. xviii+417. ISBN 3-540-56850-6. МР  1261420.
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). «14 двойственностей для практикующих». Алгоритмы выпуклого анализа и минимизации, Том II: Расширенная теория и методы расслоения . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. Том. 306. Берлин: Springer-Verlag. стр. xviii+346. ISBN 3-540-56852-2.
• Лэсдон, Леон С. (2002). Теория оптимизации для больших систем (переиздание издания Macmillan 1970 г.). Минеола, Нью-Йорк: Dover Publications, Inc., стр. xiii+523. MR  1888251.
• Лемарешаль, Клод (2001). «Лагранжева релаксация». В Михаэле Юнгере и Денисе Наддефе (ред.). Вычислительная комбинаторная оптимизация: доклады весенней школы, проходившей в замке Дагштуль, 15–19 мая 2000 г. Конспекты лекций по информатике. Том. 2241. Берлин: Springer-Verlag. стр. 112–156. дои : 10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR  1900016. S2CID  9048698.
• Minoux, M. (1986). Математическое программирование: Теория и алгоритмы . Эгон Балас (предисловие) (Перевод Стивена Вайды с французского издания (1983 Париж: Дюно). Чичестер: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. стр. xxviii+489. ISBN 0-471-90170-9. MR  0868279. (Второе издание 2008 г., на французском языке: Programmation Mathématique: Théorie et алгоритмы . Editions Tec & Doc, Париж, 2008. xxx+711 стр.).

• Эверетт, Хью III (1963). «Обобщенный метод множителей Лагранжа для решения задач оптимального распределения ресурсов». Исследование операций . 11 (3): 399–417. doi :10.1287/opre.11.3.399. JSTOR  168028. MR  0152360.
• Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (август 2007 г.). «Лагранжева релаксация с помощью методов субградиента ballstep». Математика исследования операций . 32 (3): 669–686. doi :10.1287/moor.1070.0261. MR  2348241.
• Брагин, Михаил А.; Лух, Питер Б.; Ян, Джозеф Х.; Ю, Нанпенг и Стерн, Гари А. (2015). «Сходимость метода суррогатной лагранжевой релаксации», Журнал теории оптимизации и приложений. 164 (1): 173-201, doi :10.1007/s10957-014-0561-3
• Брагин, Михаил А.; Такер, Эмили, Л. (2022) «Суррогатная лагранжева релаксация на основе уровней для смешанно-целочисленного линейного программирования», Scientific Reports . 12 : 22417, doi:10.1038/s41598-022-26264-1
• Нил Янг, Пример релаксации Лагранжа, в блоге AlgNotes.
• Нил Янг, 2012, Игрушечные примеры решателей Плоткина-Шмойса-Тардоса и Ароры-Кейла в CSTheory Stack Exchange.