Lagrangeova relaxace - Lagrangian relaxation

V oblasti matematická optimalizace, Lagrangeova relaxace je relaxační metoda který přibližný obtížný problém omezená optimalizace jednodušším problémem. Řešení uvolněného problému je přibližné řešení původního problému a poskytuje užitečné informace.

Metoda penalizuje porušení omezení nerovnosti pomocí a Lagrangeův multiplikátor, což vede k porušení předpisů. Tyto přidané náklady se používají místo přísných omezení nerovnosti v optimalizaci. V praxi lze tento uvolněný problém často vyřešit snadněji než původní problém.

Problémem maximalizace Lagrangeovy funkce duálních proměnných (Lagrangeových multiplikátorů) je Lagrangeova dvojí problém.

Matematický popis

Předpokládejme, že jsme dostali a problém lineárního programování, s ${displaystyle xin mathbb {R} ^ {n}}$ a ${displaystyle Ain mathbb {R} ^ {m, n}}$ , v následující podobě:

max		${displaystyle c ^ {T} x}$
Svatý.
		${displaystyle Axleq b}$

Pokud rozdělíme omezení dovnitř ${displaystyle A}$ takhle ${displaystyle A_ {1} v mathbb {R} ^ {m_ {1}, n}}$ , ${displaystyle A_ {2} v mathbb {R} ^ {m_ {2}, n}}$ a ${displaystyle m_ {1} + m_ {2} = m}$ můžeme napsat systém:

max		${displaystyle c ^ {T} x}$
Svatý.
(1)		${displaystyle A_ {1} xleq b_ {1}}$
(2)		${displaystyle A_ {2} xleq b_ {2}}$

Můžeme zavést omezení (2) do cíle:

max		${displaystyle c ^ {T} x + lambda ^ {T} (b_ {2} -A_ {2} x)}$
Svatý.
(1)		${displaystyle A_ {1} xleq b_ {1}}$

Pokud to necháme ${displaystyle lambda = (lambda _ {1}, ldots, lambda _ {m_ {2}})}$ být nezápornými váhami, budeme penalizováni, pokud porušíme omezení (2), a budeme také odměněni, pokud přísně splníme omezení. Above systém se nazývá Lagrangeova relaxace našeho původního problému.

Řešení LR jako vázané

Obzvláště užitečná je vlastnost, která pro jakoukoli pevnou sadu ${displaystyle {ilde {lambda}}}$ hodnot, optimální výsledek Lagrangeovy relaxační úlohy nebude menší než optimální výsledek původní úlohy. Chcete-li to vidět, nechte ${displaystyle {hat {x}}}$ být optimálním řešením původního problému a nechť ${displaystyle {ar {x}}}$ být optimálním řešením Lagrangeovy relaxace. Pak to můžeme vidět

{displaystyle c ^ {T} {hat {x}} leq c ^ {T} {hat {x}} + {ilde {lambda}} ^ {T} (b_ {2} -A_ {2} {hat {x }}) leq c ^ {T} {ar {x}} + {ilde {lambda}} ^ {T} (b_ {2} -A_ {2} {ar {x}})}

První nerovnost je pravdivá, protože ${displaystyle {hat {x}}}$ je proveditelná v původním problému a druhá nerovnost je pravdivá, protože ${displaystyle {ar {x}}}$ je optimálním řešením Lagrangeovy relaxace.

Iterace směrem k řešení původního problému

Výše uvedená nerovnost nám říká, že pokud minimalizujeme maximální hodnotu, kterou získáme z uvolněného problému, získáme přísnější limit objektivní hodnoty našeho původního problému. Můžeme tedy vyřešit původní problém tak, že prozkoumáme částečně zdvojený problém

min

{displaystyle P (lambda)}

Svatý.

{displaystyle lambda geq 0}

kde definujeme ${displaystyle P (lambda)}$ tak jako

max		${displaystyle c ^ {T} x + lambda ^ {T} (b_ {2} -A_ {2} x)}$
Svatý.
(1)		${displaystyle A_ {1} xleq b_ {1}}$

Lagrangeový relaxační algoritmus tak pokračuje v prozkoumávání rozsahu proveditelnosti ${displaystyle lambda}$ hodnot při snaze minimalizovat výsledek vrácený vnitřním ${displaystyle P}$ problém. Každá hodnota vrácená uživatelem ${displaystyle P}$ je kandidát horní hranice problému, nejmenší z nich je udržována jako nejlepší horní hranice. Pokud navíc použijeme heuristiku, pravděpodobně nasazenou ${displaystyle {ar {x}}}$ hodnoty vrácené uživatelem ${displaystyle P}$ Abychom našli proveditelné řešení původního problému, můžeme iterovat, dokud se nejlepší horní hranice a náklady na nejlepší proveditelné řešení neshodují s požadovanou tolerancí.

Související metody

The rozšířená Lagrangeova metoda je v duchu docela podobný Lagrangeově relaxační metodě, ale přidává další termín a aktualizuje duální parametry ${displaystyle lambda}$ zásadovějším způsobem. To bylo představeno v 70. letech a bylo hojně využíváno.

The pokutová metoda nepoužívá duální proměnné, ale spíše odstraňuje omezení a místo toho penalizuje odchylky od omezení. Metoda je koncepčně jednoduchá, ale v praxi se upřednostňují obvykle rozšířené Lagrangeovy metody, protože trestová metoda trpí problémy se špatnou kondicí.

Reference

Knihy

Ravindra K. Ahuja, Thomas L. Magnanti, a James B. Orlin (1993). Síťové toky: teorie, algoritmy a aplikace. Prentice Hall. ISBN 0-13-617549-X.CS1 maint: více jmen: seznam autorů (odkaz)
Bertsekas, Dimitri P. (1999). Nelineární programování: 2. vydání. Athena Scientific. ISBN 1-886529-00-0.
Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerická optimalizace: Teoretické a praktické aspekty. Universitext (druhé přepracované vydání překladu z roku 1997, francouzské vydání). Berlín: Springer-Verlag. str. xiv + 490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. PAN 2265882.
Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Konvexní algoritmy analýzy a minimalizace, svazek I: Základy. Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]. 305. Berlín: Springer-Verlag. str. xviii + 417. ISBN 3-540-56850-6. PAN 1261420.
Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). „14 Dualita pro odborníky“. Konvexní algoritmy pro analýzu a minimalizaci, svazek II: Pokročilá teorie a svazkové metody. Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]. 306. Berlín: Springer-Verlag. str. xviii + 346. ISBN 3-540-56852-2.
Lasdon, Leon S. (2002). Teorie optimalizace pro velké systémy (dotisk edice Macmillan z roku 1970). Mineola, New York: Dover Publications, Inc., str. Xiii + 523. PAN 1888251.CS1 maint: ref = harv (odkaz)
Lemaréchal, Claude (2001). "Lagrangeova relaxace". V Michael Jünger a Denis Naddef (ed.). Výpočetní kombinatorická optimalizace: Příspěvky z jarní školy konané ve Schloß Dagstuhl, 15. – 19. Května 2000. Přednášky z informatiky. 2241. Berlín: Springer-Verlag. str. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. PAN 1900016.CS1 maint: ref = harv (odkaz)
Minoux, M. (1986). Matematické programování: Teorie a algoritmy. Egon Balas (předmluva) (Přeložil Steven Vajda z francouzského vydání (1983 Paříž: Dunod).). Chichester: Publikace Wiley-Interscience. John Wiley & Sons, Ltd. str. Xxviii + 489. ISBN 0-471-90170-9. PAN 0868279. (2008, druhé vydání, ve francouzštině: Programmation mathématique: Théorie et algorithmes. Vydání Tec & Doc, Paříž, 2008. xxx + 711 stran).CS1 maint: ref = harv (odkaz)

Články

Everett, Hugh, III (1963). "Zobecněná Lagrangeova multiplikátorová metoda pro řešení problémů s optimálním přidělováním zdrojů". Operační výzkum. 11 (3): 399–417. doi:10.1287 / opre.11.3.399. JSTOR 168028. PAN 0152360.CS1 maint: ref = harv (odkaz)
Kiwiel, Krzysztof C .; Larsson, Torbjörn; Lindberg, P. O. (srpen 2007). "Lagrangeova relaxace pomocí kuličkových podstupňových metod". Matematika operačního výzkumu. 32 (3): 669–686. doi:10,1287 / měsíc 1070,0261. PAN 2348241.CS1 maint: ref = harv (odkaz)