Entspannung (Näherung)

Im Mathematische Optimierung und verwandte Felder, Entspannung ist ein Modellierungsstrategie. Eine Entspannung ist eine Annäherung eines schwierigen Problems durch ein nahe gelegenes Problem, das leichter zu lösen ist. Eine Lösung des entspannten Problems liefert Informationen zum ursprünglichen Problem.

Zum Beispiel a Lineares Programmieren Entspannung von an Ganzzahlprogrammierung Das Problem beseitigt die Integralitätsbeschränkung und ermöglicht daher rationale Lösungen für nicht-optimale Rationale. EIN Lagrange -Entspannung Von einem komplizierten Problem bei der kombinatorischen Optimierung bestraft es Verstöße gegen einige Einschränkungen und ermöglicht es, ein einfacher entspannter Problem zu lösen. Entspannungstechniken ergänzen oder ergänzen Zweig und gebunden Algorithmen der kombinatorischen Optimierung; Lineare Programmier- und Lagrange-Relaxationen werden verwendet, um Grenzen in Ast-und-gebundenen Algorithmen für die Ganzzahlprogrammierung zu erhalten.[1]

Die Modellierungsstrategie der Entspannung sollte nicht mit verwechselt werden iterative Methoden von Entspannung, wie zum Beispiel aufeinanderfolgende Überrelaxation (SOR); Iterative Methoden der Entspannung werden zur Lösung von Problemen in verwendet Differentialgleichung, lineare kleinste Quadrate, und Lineares Programmieren.[2][3][4] Iterative Entspannungsmethoden wurden jedoch verwendet, um Lagrange -Relaxationen zu lösen.[a]

Definition

A Entspannung des Minimierungsproblems

ist ein weiteres Minimierungsproblem der Form

mit diesen beiden Eigenschaften

  2. für alle .

Die erste Eigenschaft besagt, dass die machbare Domäne des ursprünglichen Problems eine Teilmenge der realisierbaren Domäne des entspannten Problems ist. Die zweite Eigenschaft besagt, dass die objektive Funktion des ursprünglichen Problems größer oder gleich der objektiven Funktion des entspannten Problems ist.[1]

Eigenschaften

Wenn ist dann eine optimale Lösung des ursprünglichen Problems und . Deswegen, Bietet eine Obergrenze auf .

Wenn zusätzlich zu den vorherigen Annahmen, zusätzlich zu , Die folgenden Haltungen: Wenn eine optimale Lösung für das entspannte Problem für das ursprüngliche Problem möglich ist, ist dies für das ursprüngliche Problem optimal.[1]

Einige Entspannungstechniken

Anmerkungen

  1. ^ Relaxationsmethoden zum Suche nach praktikablen Lösungen für lineare Ungleichheitssysteme entstehen in der linearen Programmierung und in der Lagrange -Entspannung. [2][5][6][7][8]
  1. ^ a b c Geoffrion (1971)
  2. ^ a b Goffin (1980).
  3. ^ Murty (1983), S. 453–464.
  4. ^ Minoux (1986).
  5. ^ Minoux (1986), Abschnitt 4.3.7, S. 120–123.
  6. ^ Shmuel Agmon (1954)
  7. ^ Theodore Motzkin und Isaac Schoenberg (1954)
  8. ^ L. T. Gubin, Boris T. Polyak und E. V. Raik (1969)

Verweise

  • Buttazzo, G. (1989). Semikontinuität, Relaxation und integrale Darstellung im Kalkül der Variationen. Pitman res. Notizen in Mathematik. 207. Harlow: Longmann.
  • Geoffrion, A. M. (1971). "Dualität in der nichtlinearen Programmierung: eine vereinfachte Anwendungsoriententwicklung". Siam Review. 13 (1): 1–37. JStor 2028848.
  • Goffin, J.-L. (1980). "Die Relaxationsmethode zur Lösung von Systemen linearer Ungleichheiten". Mathematik. Operation. Res. 5 (3): 388–414. doi:10.1287/moor.5.3.388. JStor 3689446. HERR 0594854.
  • Minoux, M. (1986). Mathematische Programmierung: Theorie und Algorithmen. Chichester: Eine Wiley-Interscience-Publikation. John Wiley & Sons. ISBN 978-0-471-90170-9. HERR 0868279. Übersetzt von Steven Vajda von Programmierung Mathématique: Théorie et al. Algorithmes. Paris: Dunod. 1983. HERR 2571910.
  • Murty, Katta G. (1983). "16 iterative Methoden für lineare Ungleichheiten und lineare Programme (insbesondere 16,2 Relaxationsmethoden und 16,4 sparsity-präsentierende iterative SOR-Algorithmen für die lineare Programmierung)." Lineares Programmieren. New York: John Wiley & Sons. ISBN 978-0-471-09725-9. HERR 0720547.
  • Nemhauser, G. L.; Rinnooy Kan, A. H. G.; Todd, M. J., Hrsg. (1989). Optimierung. Handbücher in Operations Research and Management Science. Vol. 1. Amsterdam: North-Holland Publishing Co. ISBN 978-0-444-87284-5. HERR 1105099.
    • W. R. Pulleyblank, Polyedrische Kombinatorik (S. 371–446);
    • George L. Nemhauser und Laurence A. Wolsey, Integer -Programmierung (S. 447–527);
    • Claude Lemaréchal, Nicht differenzierbare Optimierung (S. 529–572);
  • Rardin, Ronald L. (1998). Optimierung in der Operationsforschung. Prentice Hall. ISBN 978-0-02-398415-0.
  • Roubíček, T. (1997). Relaxation in der Optimierungstheorie und Variationsrechnung. Berlin: Walter de Gruyter. ISBN 978-3-11-014542-7.