Nichtlineare Programmierung

Nichtlineare Programmierung (NLP) ist ein Teilgebiet der mathematischen Programmierung und des Operations Research, das sich mit Optimierungsproblemen befasst, bei denen die Zielfunktion und/oder mindestens eine der Nebenbedingungen nichtlineare Funktionen der Entscheidungsvariablen sind.

Die NLP ist eine Verallgemeinerung der linearen Programmierung und ermöglicht die Modellierung einer breiteren Klasse von realen Systemen und Prozessen, bei denen die Abhängigkeiten zwischen den Variablen nicht streng proportional sind (d. h. sie werden durch Kurven und nicht durch Geraden beschrieben).

Gegenstand und Zweck

Die nichtlineare Programmierung wird verwendet, um optimale Lösungen in Situationen zu finden, in denen:

• Die Abhängigkeit der Zielgröße (Gewinn, Kosten, Effizienz usw.) von den steuerbaren Parametern nichtlinear ist (z. B. abnehmende Skalenerträge, quadratische Kosten).
• Die Beschränkungen von Ressourcen oder technologischen Prozessen durch nichtlineare Beziehungen beschrieben werden (z. B. chemische Reaktionen, physikalische Gesetze, wirtschaftliche Abhängigkeiten).

NLP-Probleme treten in vielen Bereichen auf:

• Ingenieurwesen (Optimierung von Konstruktionen, Prozessen).
• Wirtschaft und Finanzen (Portfoliooptimierung unter Berücksichtigung von Risiken, Marktmodellierung).
• Chemische Verfahrenstechnik (Optimierung von Reaktorbetriebsmodi).
• Maschinelles Lernen (Training neuronaler Netze, Support Vector Machine).
• Steuerung von Produktionsprozessen.
• Logistik (unter Berücksichtigung nichtlinearer Kosten).

Mathematische Formulierung des NLP-Problems

Die allgemeine Aufgabe der nichtlinearen Programmierung wird wie folgt formuliert:

Es wird eine Menge von Werten für die Entscheidungsvariablen gesucht, die eine nichtlineare Zielfunktion maximiert oder minimiert. Dabei müssen die Werte der Variablen ein System von Nebenbedingungen erfüllen, die sowohl in Form von Ungleichungen (z. B. «Größe A muss kleiner oder gleich B sein») als auch in Form von Gleichungen (z. B. «Größe C muss genau gleich D sein») ausgedrückt werden können. Wesentlich ist, dass mindestens eine der Funktionen, die das Ziel oder die Nebenbedingungen beschreiben, nichtlinear ist. Häufig werden auch Nichtnegativitätsbedingungen für die Variablen hinzugefügt, d. h. die Forderung, dass ihre Werte größer oder gleich null sein müssen.

Die Menge aller Wertekombinationen der Variablen, die die Nebenbedingungen erfüllen, bildet den zulässigen Bereich.

Unterschiede zur linearen Programmierung

Die nichtlineare Programmierung unterscheidet sich wesentlich von der linearen Programmierung (LP):

• Nichtlinearität: Die Zielfunktion oder die Nebenbedingungen (oder beides) enthalten nichtlineare Abhängigkeiten.
• Eigenschaften des zulässigen Bereichs: Der zulässige Bereich in der NLP kann nicht-konvex sein (im Gegensatz zur LP, wo der zulässige Bereich immer ein konvexes Polyeder ist).
• Eigenschaften des Optimums: Die optimale Lösung in der NLP befindet sich nicht notwendigerweise an einem Eckpunkt des zulässigen Bereichs; sie kann auf dem Rand oder im Inneren des Bereichs liegen. In der NLP können lokale Optima existieren, die nicht global sind.
• Lösungskomplexität: NLP-Probleme sind in der Regel deutlich schwieriger zu lösen als LP-Probleme. Es gibt keinen einzigen universellen Algorithmus, der dem Simplex-Verfahren für alle NLP-Probleme entspricht.

Wesentliche Schwierigkeiten und Herausforderungen der NLP

Die Lösung von Problemen der nichtlinearen Programmierung ist mit einer Reihe von Schwierigkeiten verbunden:

• Existenz lokaler Extrema: Die meisten NLP-Methoden garantieren nur das Auffinden eines lokalen Optimums (einer Lösung, die in einer bestimmten Umgebung die beste ist). Die Suche nach dem globalen Optimum (der besten Lösung im gesamten zulässigen Bereich) ist eine komplexe Aufgabe, insbesondere bei nicht-konvexen Problemen.
• Nicht-Konvexität: Wenn das Problem nicht konvex ist (die Zielfunktion oder der zulässige Bereich ist nicht-konvex), können mehrere lokale Optima existieren, und Standard-Gradientenverfahren können in einem von ihnen «stecken bleiben».
• Rechenkomplexität: Lösungsalgorithmen für NLP erfordern oft erheblich mehr Rechenressourcen im Vergleich zur LP.

Wichtige Klassen von NLP-Problemen

Trotz der allgemeinen Komplexität gibt es wichtige Unterklassen von NLP-Problemen, für die effiziente Lösungsmethoden entwickelt wurden:

• Konvexe Programmierung: Die Aufgabe der Minimierung einer konvexen Funktion über einer konvexen Menge zulässiger Lösungen (oder der Maximierung einer konkaven Funktion). Eine Schlüsseleigenschaft ist, dass jedes lokale Minimum auch ein globales Minimum ist. Dies vereinfacht die Suche nach der optimalen Lösung erheblich.
• Quadratische Programmierung: Die Zielfunktion ist quadratisch, und alle Nebenbedingungen sind linear.
• Separable Programmierung: Die Zielfunktion und die Nebenbedingungen können als Summen von Funktionen dargestellt werden, von denen jede nur von einer einzigen Variablen abhängt.

Lösungsmethoden für NLP-Probleme

I. Verfahren der unrestringierten Optimierung (Optimierung ohne Nebenbedingungen)

• Gradientenverfahren (Verfahren des steilsten Abstiegs, Verfahren der konjugierten Gradienten)
• Newton-Verfahren und Quasi-Newton-Verfahren (z. B. BFGS)
• Verfahren mit Approximation der Hesse-Matrix

II. Verfahren der restringierten Optimierung (Optimierung mit Nebenbedingungen)

• Transformationsmethoden:
  • Strafkostenverfahren (Penalty-Methoden)
  • Barriereverfahren (Barrier Methods)
• Methoden der zulässigen Richtungen:
  • Verfahren der zulässigen Richtungen
• Methoden, die auf Optimalitätsbedingungen basieren:
  • Karush-Kuhn-Tucker-Bedingungen (KKT-Bedingungen)
  • Lagrange-Multiplikatoren-Methode
• Iterative Verfahren:
  • Sequentielle quadratische Programmierung (SQP)
  • Innere-Punkte-Verfahren

III. Verfahren der globalen Optimierung

• Heuristische und metaheuristische Verfahren:
  • Genetische Algorithmen
  • Simulierte Abkühlung
  • Tabu-Suche (Tabu Search)
• Deterministische Verfahren:
  • Branch-and-Bound-Verfahren
  • Algorithmen der globalen Optimierung für Probleme mit spezieller Struktur

Siehe auch

• Lineare Programmierung
• Optimierung
• Zielfunktion
• Mathematisches Modell

Literatur

• Bazaraa, M. S., Shetty, C. M. Nichtlineare Programmierung: Theorie und Algorithmen. Moskau: Mir, 1982.
• Fiacco, A. V., McCormick, G. P. Nichtlineare Programmierung: Methoden der sequentiellen unrestringierten Minimierung. Moskau: Mir, 1972.
• Himmelblau, D. M. Angewandte nichtlineare Programmierung. Moskau: Mir, 1975.
• Nocedal, J., Wright, S. J. Numerical Optimization. 2. Aufl. Springer, 2006.