Nichtlineare Optimierung

In diesem einführenden Kapitel geben wir einen Einblick in die Thematik der nichtlinearen Optimierung und stellen die Grundlagen zur mathematischen Behandlung von Optimierungsaufgaben bereit.

Die Zielfunktion eines Optimierungsproblems ist oft nicht überall differenzierbar oder die Berechnung der Ableitung ist sehr aufwendig (vgl. hierzu Abschnitt 2.3). Deshalb hat man Verfahren entwickelt, die keine Ableitungen der Zielfunktion verwenden. Wir behandeln zwei ableitungsfreie Verfahren, das Nelder-Mead-Verfahren und ein Mutations-Selektions-Verfahren, zur Lösung unrestringierter Optimierungsaufgaben. Dabei setzen wir der Einfachheit halber D = ℝ ⁿ voraus, betrachten also das Problem mit der Zielfunktion f:ℝ ⁿ → ℝ.

Für das folgende setzen wir generell voraus, dass D ⊂ℝ ⁿ nichtleer und offen ist, und dass f eine Funktion f: D → ℝ ist. Wir betrachten das unrestringierte Problem und wollen notwendige und hinreichende Bedingungen zur Charakterisierung von lokalen Lösungen solcher Aufgaben untersuchen. Dazu werden wir voraussetzen, dass die Zielfunktion f gewisse Differenzierbarkeitseigenschaften hat. Wir verweisen in diesem Zusammenhang auf Abschnitt 1.7.

Wie in Kapitel 2 betrachten wir das unrestringierte Optimierungsproblem wobei f:ℝ ⁿ → ℝ die Zielfunktion ist. Dabei setzen wir der Einfachheit halber wieder D = ℝ ⁿ voraus. Wir wollen numerische Verfahren zur Berechnung einer lokalen Lösung von (PU) behandeln, wobei wir voraussetzen, dass die Zielfunktion f wenigstens stetig differenzierbar ist.

Im Zusammenhang mit dem Lagerhaltungsproblem (LH1) haben wir in Abschnitt 2.3.4 gesehen, dass es oft erforderlich ist, bei der Optimierung zusätzliche Nebenbedingungen zu berücksichtigen. Wir betrachten daher jetzt Optimierungsprobleme wobei ℝ⊂ℝ ⁿ eine offene Menge und f: D → ℝ eine differenzierbare Funktion ist. Die zulässige Menge F ⊂ D definiert die Nebenbedingungen. Für einige allgemeine Aussagen benötigen wir nur die Konvexität von F; die wesentlichen Resultate dieses Kapitels betreffen jedoch Probleme, bei denen F durch lineare Gleichungen und Ungleichungen definiert ist. Wir wollen Lösungen solcher Probleme wie im unrestringierten Fall durch Optimalitätsbedingungen charakterisieren, die im nächsten Kapitel dann die Grundlage für die Entwicklung numerischer Verfahren sein werden.

Auf der Basis der theoretischen Resultate des letzten Kapitels wollen wir uns jetzt mit Lösungsverfahren für Optimierungsaufgaben mit linearen Restriktionen beschäftigen. Wir betrachten zuerst quadratische Optimierungsprobleme, deren spezielle Struktur man bei Optimierungsverfahren ausnutzen kann, und anschließend Probleme mit nichtquadratischer Zielfunktion.

Gegenstand dieses Kapitels sind Optimierungsprobleme mit nichtlinearen Gleichungsund Ungleichungsrestriktion. Wie bei Problemen mit linearen Restriktionen wollen wir lokale Minima durch notwendige und hinreichende Optimalitätsbedingungen charakterisieren, auf deren Grundlage man Lösungsverfahren konstruieren kann. Dazu lineari-sieren wir das Optimierungsproblem in einer lokalen Lösung und erhalten ein lineares Optimierungsproblem, auf das wir die Theorie aus Kapitel 5 anwenden können. Um die Linearisierung zu rechtfertigen, müssen wir allerdings eine Regularitätsbedingung voraussetzen. Ein Schwerpunkt dieses Kapitels besteht daher in der Diskussion geeigneter Regularitätsbedingungen. Dabei werden wir auch auf bereits in Kapitel 5 benutzte Bedingungen wie “lineare Unabhängigkeit der Gradienten der aktiven Restriktionen“ zurückkommen.

Auf der Basis der theoretischen Resultate des letzten Kapitels wollen wir uns jetzt mit numerischen Verfahren zur Lösung des Problems (PNU) befassen. Wir verallgemeinern zunächst das Newton-SQP-Verfahren aus Abschnitt 6.4.1. Dann gehen wir auf Erweiterungen des Verfahrens ein, die wie das gedämpfte Newton-Verfahren bei unrestringierten Problemen die globalen Konvergenzeigenschaften verbessern und die lokal quadratische oder superlineare Konvergenz erhalten. Abschließend diskutieren wir wieder einige Anwendungen.