Relaxace (přibližná) - Relaxation (approximation)
v matematická optimalizace a související pole, relaxace je strategie modelování. Relaxace je přiblížení obtížného problému blízkým problémem, který se snáze vyřeší. Řešení uvolněného problému poskytuje informace o původním problému.
Například a lineární programování relaxace celočíselné programování Problém odstraňuje omezení integrity a umožňuje tak nelineární racionální řešení. A Lagrangeova relaxace komplikovaného problému v kombinatorické optimalizaci penalizuje porušení některých omezení, což umožňuje vyřešit snadnější uvolněný problém. Relaxační techniky doplňují nebo doplňují větev a svázaný algoritmy kombinatorické optimalizace; lineární programování a Lagrangeovy relaxace se používají k získání hranic v algoritmech větve a meze pro celočíselné programování.[1]
Strategie modelování relaxace by neměla být zaměňována s iterační metody z relaxace, jako postupná nadměrná relaxace (SOR); při řešení problémů se používají iterační metody relaxace diferenciální rovnice, lineární nejmenší čtverce, a lineární programování.[2][3][4] K řešení Lagrangeových relaxací však byly použity iterační metody relaxace.[5]
Definice
A relaxace problému minimalizace
je další minimalizační problém formy
s těmito dvěma vlastnostmi
- pro všechny .
První vlastnost uvádí, že proveditelná doména původního problému je podmnožinou proveditelné domény uvolněného problému. Druhá vlastnost uvádí, že objektivní funkce původního problému je větší nebo rovna objektivní funkci uvolněného problému.[1]
Vlastnosti
Li je tedy optimálním řešením původního problému a . Proto, poskytuje horní mez na .
Pokud kromě předchozích předpokladů , , platí toto: Pokud je pro původní problém proveditelné optimální řešení uvolněného problému, pak je pro původní problém optimální.[1]
Některé relaxační techniky
- Relaxace lineárního programování
- Lagrangeova relaxace
- Semidefinitní relaxace
- Náhradní relaxace a dualita
Poznámky
- ^ A b C Geoffrion (1971)
- ^ Murty, Katta G. (1983). "16 iteračních metod pro lineární nerovnosti a lineární programy (zejména 16.2 Relaxační metody a 16.4 iterativní algoritmy SOR pro zachování lineárního programování pro lineární programování)". Lineární programování. New York: John Wiley & Sons, Inc., str. 453–464. ISBN 978-0-471-09725-9. PAN 0720547.CS1 maint: ref = harv (odkaz)
- ^ Goffin, J.-L. (1980). "Relaxační metoda pro řešení systémů lineárních nerovností". Matematika. Oper. Res. 5 (3): 388–414. doi:10,1287 / bř. 5. 3. 388. JSTOR 3689446. PAN 0594854.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 978-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). PAN2571910 )
- ^ Relaxační metody pro nalezení proveditelného řešení systémů lineární nerovnosti vznikají v lineárním programování a v Lagrangeově relaxaci. Goffin (1980) a Minoux (1986) | loc = Sekce 4.3.7, s. 120–123 Shmuel Agmon (1954) a Theodore Motzkin a Isaac Schoenberg (1954), a L. T. Gubin, Boris T. Polyak a E. V. Raik (1969).
Reference
- G. Buttazzo (1989). Polokontinuita, relaxace a integrální reprezentace v variačním počtu. Pitman Res. Poznámky v matematice. 207. Harlow: Longmann.
- Geoffrion, A. M. (1971). „Dualita v nelineárním programování: zjednodušený vývoj orientovaný na aplikace“. Recenze SIAM. 13 (1). s. 1–37. JSTOR 2028848.CS1 maint: ref = harv (odkaz).
- Goffin, J.-L. (1980). "Relaxační metoda pro řešení systémů lineárních nerovností". Matematika. Oper. Res. 5 (3): 388–414. doi:10,1287 / bř. 5. 3. 388. JSTOR 3689446. PAN 0594854.CS1 maint: ref = harv (odkaz)
- Minoux, M. (1986). Matematické programování: Teorie a algoritmy ((S předmluvou Egona Balase) 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 978-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). PAN2571910 )|
- Nemhauser, G. L.; Rinnooy Kan, A. H. G .; Todd, M. J., eds. (1989). Optimalizace. Příručky v operačním výzkumu a vědě o řízení. 1. Amsterdam: North-Holland Publishing Co. str. Xiv + 709. ISBN 978-0-444-87284-5. PAN 1105099.CS1 maint: ref = harv (odkaz)
- W. R. Pulleyblank, Polyedrická kombinatorika (str. 371–446);
- George L. Nemhauser a Laurence A. Wolsey, programování celých čísel (str. 447–527);
- Claude Lemaréchal „Nediferencovatelná optimalizace (str. 529–572);
- Rardin, Ronald L. (1998). Optimalizace v operačním výzkumu. Prentice Hall. ISBN 978-0-02-398415-0.
- Roubíček, T. (1997). Relaxace v teorii optimalizace a variačním počtu. Berlín: Walter de Gruyter. ISBN 978-3-11-014542-7.