Relaks Lagrange'a

W dziedzinie optymalizacji matematycznej relaksacja Lagrange'a jest metodą relaksacji , która przybliża trudny problem optymalizacji z ograniczeniami prostszym problemem. Rozwiązanie problemu zrelaksowanego jest przybliżonym rozwiązaniem pierwotnego problemu i dostarcza użytecznych informacji.

Metoda karze naruszenia ograniczeń nierówności za pomocą mnożnika Lagrange'a , który nakłada koszt na naruszenia. Te dodatkowe koszty są używane zamiast ścisłych ograniczeń nierówności w optymalizacji. W praktyce ten zrelaksowany problem często można rozwiązać łatwiej niż problem pierwotny.

Problem maksymalizacji funkcji Lagrange'a zmiennych podwójnych (mnożników Lagrange'a) to podwójny problem Lagrange'a .

Opis matematyczny

$A \ in \ mathbb {R} ^ { m,n}}$ mamy problem z programowaniem liniowym , gdzie $Displaystyle$ ZA , o następującej postaci:

maks		$\ displaystyle c ^ {T} x}$
st
		${\ Displaystyle Ax \ równoważnik b}$

Jeśli podzielimy ograniczenia w $taki$ sposób, że ${\ Displaystyle A_ {1} \ in \ mathbb {R} ^ {m_ {1}, n}$ , ${\ Displaystyle A_ {2} \ w \ mathbb {R} ^ {m_ {2}, n}}$ i ${\ Displaystyle m_ {1} + m_ {2} = m}$ możemy zapisać układ:

maks		$\ displaystyle c ^ {T} x}$
ul
(1)		${\ Displaystyle A_ {1} x \ równoważnik b_ {1}}$
(2)		${\ Displaystyle A_ {2} x \ równoważnik b_ {2}}$

Do celu możemy wprowadzić ograniczenie (2):

maks		${\ Displaystyle c ^ {T} x + \ lambda ^ {T} (b_ {2} -A_ {2} x)}$
ul
(1)		${\ Displaystyle A_ {1} x \ równoważnik b_ {1}}$

${\ Displaystyle \ lambda = (\ lambda _ {1}, \ ldots, \ lambda _ {m_ {2}})} będą nieujemne,$ zostaniemy ukarani jeśli naruszymy ograniczenie (2), a także zostaniemy nagrodzeni, jeśli ściśle je spełnimy. Powyższy system nazywa się relaksacją Lagrange'a naszego pierwotnego problemu.

Rozwiązanie LR jako granica

Szczególnie użyteczna jest właściwość, że dla dowolnego ustalonego zestawu $wartości$ relaksacji Lagrange'a nie będzie mniejszy niż optymalny wynik dla oryginalny problem. Aby to zobaczyć, niech $hat {x}}}$$^$ { \ . Możemy to wtedy zobaczyć

${\ Displaystyle c ^ {T} {\ kapelusz {x}}\leq c^{T}{\kapelusz {x}}+{\tylda {\lambda}}^{T}(b_{2}-A_{2}{\kapelusz {x}}) \leq c ^{T}{\bar {x}}+{\tylda {\lambda}}^{T}(b_{2}-A_{2}{\bar {x}})}$

Pierwsza nierówność jest prawdziwa, ponieważ $jest$ wykonalna w pierwotnym problemie, a druga nierówność jest prawdziwa, ponieważ jest optymalnym rozwiązaniem $}}$ relaksację Lagrange'a.

Iteracja w kierunku rozwiązania pierwotnego problemu

Powyższa nierówność mówi nam, że jeśli zminimalizujemy maksymalną wartość, jaką uzyskujemy z problemu rozluźnionego, uzyskamy ściślejszą granicę obiektywnej wartości naszego pierwotnego problemu. W ten sposób możemy rozwiązać pierwotny problem, zamiast tego badając problem częściowo dualizowany

min

${\ Displaystyle P (\ lambda)}$

ul

${\ Displaystyle \ lambda \ geq 0}$

gdzie definiujemy ${\ Displaystyle P (\ lambda)}$ jako

maks		${\ Displaystyle c ^ {T} x + \ lambda ^ {T} (b_ {2} -A_ {2} x)}$
ul
(1)		${\ Displaystyle A_ {1} x \ równoważnik b_ {1}}$

$do$ zbadania zakresu możliwych $,$ starając się zminimalizować wynik zwracany przez wewnętrzny . Każda wartość zwrócona przez $kandydującą$ górną granicą problemu, z których najmniejsza jest utrzymywana jako najlepsza górna granica $}$ zastosujemy heurystykę, prawdopodobnie zaszczepioną przez wartości zwrócone przez ${\ displaystyle {\ bar {x}}$ , aby znaleźć wykonalne rozwiązania pierwotnego problemu, możemy iterować, aż najlepsza górna granica i koszt najlepszego wykonalnego rozwiązania zbiegną się z pożądaną tolerancją.

Powiązane metody

Rozszerzona metoda Lagrange'a jest $w$ duchu dość podobna do metody relaksacji Lagrange'a, ale dodaje dodatkowy termin i aktualizuje podwójne parametry bardziej pryncypialny sposób. Został wprowadzony w latach 70. XX wieku i był szeroko stosowany.

Metoda kary nie wykorzystuje zmiennych podwójnych, ale raczej usuwa ograniczenia i zamiast tego karze odchylenia od ograniczenia. Metoda jest koncepcyjnie prosta, ale w praktyce preferowane są zwykle rozszerzone metody Lagrange'a, ponieważ metoda kary ma problemy ze złym uwarunkowaniem.

Książki

•   Ravindra K. Ahuja , Thomas L. Magnanti i James B. Orlin (1993). Przepływy sieciowe: teoria, algorytmy i zastosowania . Sala Prentice'a. ISBN 0-13-617549-X . {{ cite book }} : CS1 maint: wiele nazwisk: lista autorów ( link )
•   Bertsekas, Dimitri P. (1999). Programowanie nieliniowe: wydanie 2. Atena Naukowa. ISBN 1-886529-00-0 .
•    Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Optymalizacja numeryczna: aspekty teoretyczne i praktyczne . Universitext (drugie poprawione wydanie tłumaczenia wydania francuskiego z 1997 r.). Berlin: Springer-Verlag. s. 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). Algorytmy analizy wypukłej i minimalizacji, Tom I: Podstawy . Grundlehren der Mathematischen Wissenschaften [Podstawowe zasady nauk matematycznych]. Tom. 305. Berlin: Springer-Verlag. s. XVIII + 417. ISBN 3-540-56850-6 . MR 1261420 .
•   Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). „14 Duality dla praktykujących”. Algorytmy analizy wypukłej i minimalizacji, Tom II: Zaawansowana teoria i metody wiązek . Grundlehren der Mathematischen Wissenschaften [Podstawowe zasady nauk matematycznych]. Tom. 306. Berlin: Springer-Verlag. s. XVIII + 346. ISBN 3-540-56852-2 .
•   Lasdon, Leon S. (2002). Teoria optymalizacji dla dużych systemów (przedruk wydania Macmillan z 1970 r.). Mineola, Nowy Jork: Dover Publications, Inc., s. XIII+523. MR 1888251 .
•     Lemaréchal, Claude (2001). „Relaks Lagrange'a”. W Michael Jünger i Denis Naddef (red.). Obliczeniowa optymalizacja kombinatoryczna: referaty ze szkoły wiosennej, która odbyła się w Schloß Dagstuhl, 15–19 maja 2000 r . Notatki z wykładów z informatyki. Tom. 2241. Berlin: Springer-Verlag. s. 112–156. doi : 10.1007/3-540-45586-8_4 . ISBN 3-540-42877-1 . MR 1900016 . S2CID 9048698 .
•    Minoux, M. (1986). Programowanie matematyczne: teoria i algorytmy . Egon Balas (przedmowa) (przetłumaczone przez Stevena Vajdę z francuskiego wydania (1983 Paris: Dunod).). Chichester: Publikacja Wiley-Interscience. John Wiley & Sons, Ltd. s. xxviii + 489. ISBN 0-471-90170-9 . MR 0868279 . (2008 Wydanie drugie, w języku francuskim: Programmation mathématique: Théorie et algorytmes . Editions Tec & Doc, Paryż, 2008. xxx+711 s.).

Artykuły

•    Everett, Hugh, III (1963). „Metoda uogólnionego mnożnika Lagrange'a do rozwiązywania problemów optymalnej alokacji zasobów”. Badania Operacyjne . 11 (3): 399–417. doi : 10.1287/opre.11.3.399 . JSTOR 168028 . MR 0152360 .
•   Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, PO (sierpień 2007). „Relaksacja Lagrange'a za pomocą metod subgradientowych typu ballstep” . Matematyka badań operacyjnych . 32 (3): 669–686. doi : 10.1287/moor.1070.0261 . MR 2348241 .
• Bragin, Michaił A.; Luh, Peter B.; Yan, Joseph H.; Yu, Nanpeng i Stern, Gary A. (2015). „Zbieżność zastępczej metody relaksacji Lagrange'a”, Journal of Optimization Theory and Applications. 164 (1): 173-201, doi : 10.1007/s10957-014-0561-3