Nichtlineare Programmierung

Die nichtlineare Programmierung optimiert eine glatte nichtlineare Zielfunktion unter nichtlinearen Nebenbedingungen und umfasst sowohl die Theorie der Optimalität als auch die Algorithmen zur Berechnung von Lösungen.

Definition

Ein nichtlineares Programm minimiert eine möglicherweise nichtlineare Zielfunktion über einer zulässigen Menge, die durch nichtlineare Gleichheits- und Ungleichheitsnebenbedingungen definiert ist; im Gegensatz zu konvexen Problemen kann es mehrere lokale Optima aufweisen, sodass die meisten Methoden Punkte suchen, die notwendige Optimalitätsbedingungen erfüllen.

Scope

Dieses Thema behandelt die unbeschränkte Minimierung, Liniensuche- und Trust-Region-Strategien, Gradienten-, Newton- und Quasi-Newton-Verfahren, Optimalitätsbedingungen erster und zweiter Ordnung, die Karush-Kuhn-Tucker-Bedingungen und Constraint Qualifications sowie beschränkte Verfahren wie Penalty-Methoden, erweiterte Lagrange-Funktionen und sequentielle quadratische Programmierung.

Core questions

• Welche Bedingungen charakterisieren ein lokales Optimum eines beschränkten nichtlinearen Problems?
• Wie finden Abstiegsverfahren einen stationären Punkt eines unbeschränkten Problems?
• Wie werden Nebenbedingungen in iterative Algorithmen integriert?
• Wann kann ein berechnetes lokales Optimum als global angesehen werden?

Key theories

Optimalitätsbedingungen

Karush-Kuhn-Tucker-Bedingungen erster Ordnung und Krümmungsbedingungen zweiter Ordnung charakterisieren lokale Optima von beschränkten Problemen unter geeigneten Constraint Qualifications.

Abstiegs- und Newton-artige Verfahren

Gradienten-, Newton- und Quasi-Newton-Verfahren erzeugen Abstiegsrichtungen und verwenden Liniensuchen oder Trust-Regionen, um zu stationären Punkten zu konvergieren, wobei Quasi-Newton-Updates die Krümmung kostengünstig approximieren.

Algorithmen zur beschränkten Optimierung

Penalty-Methoden, erweiterte Lagrange-Funktionen und sequentielle quadratische Programmierung wandeln beschränkte Probleme in Sequenzen einfacherer Probleme um und behandeln Gleichheits- und Ungleichheitsnebenbedingungen systematisch.

Clinical relevance

Nichtlineare Programmierung wird überall dort eingesetzt, wo Ziele oder Nebenbedingungen nicht linear sind, einschließlich der Modellanpassung und des Trainings statistischer und maschineller Lernmodelle, des Ingenieurdesigns, der optimalen Steuerung und der Parameterschätzung in den Wissenschaften.

History

Die Karush-Kuhn-Tucker-Bedingungen, die 1951 aufgestellt und bereits 1939 von Karush vorweggenommen wurden, verallgemeinerten die Lagrange-Multiplikatoren auf Ungleichheitsnebenbedingungen und begründeten die Theorie der beschränkten nichtlinearen Optimierung. Quasi-Newton-Verfahren, erweiterte Lagrange-Funktionen und sequentielle quadratische Programmierung entwickelten sich im Laufe des späten zwanzigsten Jahrhunderts zu den Standardwerkzeugen der numerischen Optimierung.

Key figures

• Harold Kuhn
• Albert Tucker
• Isaac Newton
• Magnus Hestenes

Seminal works

• nocedal2006
• bertsekas1999

Frequently asked questions

Warum ist nichtlineare Programmierung schwieriger als lineare Programmierung?

Nichtlineare Probleme können gekrümmte zulässige Bereiche und mehrere lokale Optima aufweisen, sodass im Allgemeinen keine Garantie besteht, dass eine berechnete Lösung global optimal ist, und Optima müssen nicht an Eckpunkten liegen. Algorithmen müssen sich auf lokale Informationen wie Gradienten und Krümmung stützen.

Was ist ein Quasi-Newton-Verfahren?

Es ist ein iteratives Verfahren, das den Newton-Schritt approximiert, ohne die vollständige Matrix der zweiten Ableitungen zu berechnen, und Krümmungsinformationen aus aufeinanderfolgenden Gradienten aufbaut. Verfahren wie BFGS erreichen eine schnelle Konvergenz zu wesentlich geringeren Kosten als exakte Newton-Schritte.