Benutzer:Stepri2005/Kurs:Optimierung II/Optimalitätskriterien für nichtlineare Optimierungsprobleme mit Nebenbedingungen

In diesem Kapitel wollen wir Optimalitätsbedingungen erster und zweiter Ordnung für die nichtlineare Optimierung unter Nebenbedingungen bereit stellen. Dazu gehören vor allem wieder die Karush-Kuhn-Tucker- (KKT-)Bedingungen, die ja in der Optimierung mit Restriktionen eine ähnlich wichtige Rolle für Algorithmen spielen, wie es die Bedingung in der unrestringierten Optimierung tut.

9.1 Das restringierte Optimierungsproblem

Bearbeiten

Von jetzt an betrachten wir das folgende Optimierungsproblem mit endlich vielen Gleichungs- und Ungleichungsnebenbedingungen, wobei wieder über   zu minimieren ist:

 

Die zulässige Menge von   bezeichnen wir mit

(9.1)  

Wir gehen hier der Einfachheit halber davon aus, dass die Funktionen   und   mindestens einmal und erforderlichenfalls auch zweimal stetig auf dem   differenzierbar sind.

Alle Ungleichungen von  , die in   strikt erfüllt sind, d. h. für welche   gilt, sind aufgrund der geforderten Stetigkeit der   und ihrer endlichen Anzahl auch in einer Umgebung von   erfüllt und können damit „lokal“ vernachlässigt werden. Deshalb interessiert, welche Ungleichungen von   in   aktiv sind, d. h., für welche Ungleichungen   ist. Entsprechend nennen wir

 

die Menge der in   aktiven Indizes. Eine Ungleichung, für welche   in   ist, bezeichnen wir als inaktiv in  . Mit   meinen wir einen zugehörigen Index  . In diesem Zusammenhang hat man die folgende intuitiv einleuchtenden Aussagen.

Lemma 9.1

Bearbeiten
(i)   ist genau dann ein lokaler Minimalpunkt von  , wenn   ein lokaler Minimalpunkt von
 
ist für
 
(ii) Ist   ein lokaler Minimalpunkt von  , so ist   auch ein lokaler Minimalpunkt von
 
für
 

Übung!

Würde man die in einer lokalen Lösung von   aktiven Restriktionen kennen, so könnte man also die für diese Lösung inaktiven Restriktionen von Vorneherein im Problem streichen. Im Hinblick auf die Erfüllung notwendiger Optimalitätsbedingungen könnte man sogar alle anderen Ungleichungen als Gleichungen behandeln. Da die Anzahl der mit Gleichheit in einem Punkt x^* erfüllten Nebenbedingungen typischerweise kleiner oder gleich der Zahl der Variablen des Problems ist, also hier typischerweise   angenommen werden kann, übersteigt die Zahl der Ungleichungsrestriktionen, die keine Rolle für die gefundene Lösung spielen, die Zahl der aktiven Restriktionen in der Praxis oft beträchtlich. Es bietet sich daher zumindest für Probleme mit sehr vielen Ungleichungsnebenbedingungen an, Lösungsstrategien zu entwickeln, die in der aktuellen Näherung nur die aktiven Restriktionen oder nur eine kleine Teilmenge von Restriktionen verwenden, welche z. B. die aktiven und fast aktive Restriktionen umfasst.

Die zulässige Menge   von Problem   kann auch dann konvex sein, wenn unter den   und   nichtkonvexe Funktionen sind. Zumeist ist aber in einem solchen Fall die Konvexität von   nicht erkennbar, so dass man ein derartiges Problem als ein nichtkonvexes Problem behandeln muss. Abweichend von der in Optimierung I gegebenen Definition, dass ein Optimierungsproblem konvex heißt, wenn   eine konvexe Funktion und   eine konvexe Menge ist und Bezug nehmend auf Lemma 2.27 aus Optimierung I nennen wir daher der Einfachheit halber von nun an das Problem   konvex, wenn gilt:

(9.2)   sind konvex und   sind affin-linear.

Anderenfalls sprechen wir bei   von einem (nichtkonvexen) nichtlinearen Problem.

In Übereinstimmung mit der in Optimierung I gegebenen Definition sagen wir weiter, dass   ein quadratisches Optimierungsproblem ist im Fall

  ist quadratisch und   sind affin-linear.

Von besonderem Interesse sind bekanntlich konvexe quadratische Optimierungsprobleme, d. h. quadratische Optimierungsprobleme mit konvexer Zielfunktion  . Schließlich heißt das Problem   ja ein lineares Optimierungsproblem, wenn gilt:

  sind affin-linear.

Die   und   haben dann mit Vektoren   und Zahlen   die Form

(9.3)  

mit Gradienten

(9.4)  

9.2 Die Karush-Kuhn-Tucker Bedingungen

Bearbeiten

Die folgende Definition war in Optimierung 1 gegeben worden.

Definition 9.2

Bearbeiten
Seien  . Die folgenden Gleichungen und Ungleichungen in den Veränderlichen   heißen Karush-Kuhn-Tucker- (KKT-)Bedingungen für Problem  :
(9.5)  
(9.6)  
(9.7)  
(9.8)  
(9.9)  
Einen Punkt  , zu dem Vektoren   und   existieren, so dass für   die KKT-Bedingungen erfüllt sind, nennt man einen KKT-Punkt (von  ).

Für Erläuterungen zu den KKT-Bedingungen und für Beispiele, für die wir die KKT-Bedingungen aufgestellt hatten, verweisen wir auf die Optimierung I. Dort findet man auch den folgenden Satz, den wir wegen seiner Bedeutung für die Betrachtungen hier wiederholen.

Satz 9.3

Bearbeiten
Es seien   konvexe und die   affin-lineare Funktionen. Ist   ein KKT-Punkt von Problem  , so ist   (globale) Lösung von  .

In Optimierung I war weiter gezeigt und verwendet worden, dass die KKT-Bedingungen für linear restringierte nichtlineare Optimierungsprobleme notwendige Optimalitätsbedingungen erster Ordnung darstellen:

Satz 9.4

Bearbeiten
Sei   und seien die   und   affin-linear. Ist   lokale Lösung von  , dann ist   ein KKT-Punkt von  .

Für linear restringierte konvexe Optimierungsprobleme konnten wir schließen, indem wir die letzten beiden Sätze kombinierten:

Korollar 9.5

Bearbeiten
Sei   konvex und seien die   und   affin-linear. Es ist   genau dann Lösung von Problem  , wenn   ein KKT-Punkt von   ist.

Wenn   ein lineares oder konvexes Problem ist, spricht man bei lokalen Lösungen auch einfach von Lösungen des Problems.

Das folgende Beispiel zeigt nun, dass die KKT-Bedingungen ohne eine Zusatzvoraussetzung an das Problem keine notwendigen Optimalitätsbedingungen für allgemeine nichtlineare Probleme darstellen müssen.

Beispiel 9.6

Bearbeiten

Man betrachte die folgende Aufgabe:

 

Offenbar ist   die globale Lösung dieses Problems und gilt  . Die Bedingung (9.7) der KKT-Bedingungen lautet in diesem Fall

(9.10)  

Das lineare Gleichungssystem (9.10) besitzt offenbar keine Lösung. Somit ist   in diesem Fall kein KKT-Punkt.


Es existieren eine Reihe unterschiedlicher Annahmen, die zum Ziel haben, eine Situation wie sie im letzten Beispiel auftritt, auszuschließen. Da sich diese in irgendeiner Weise auf die Restriktionen bzw. das durch sie definierte zulässige Gebiet beziehen, spricht man in der englischsprachigen Literatur bei einer solchen Annahme von einer Constraint Qualification (CQ) („Qualification“ heißt Vorbedingung). Die am häufigsten verwendete Bedingung ist die in der folgenden Definition angegebene, die in Beispiel 9.6 offenbar nicht erfüllt ist.

Definition 9.7

Bearbeiten

Es seien  . Die Linear-Independence-Constraint-Qualification (LICQ) ist in   erfüllt, wenn gilt:

(9.11)   sind linear unabhängig.

Im Fall, dass die LICQ erfüllt ist, hat man:

Lemma 9.8

Bearbeiten
Sind   und ist   ein Punkt, in dem die LICQ gilt und für den mit Multiplikatoren   und   die KKT-Bedingungen erfüllt sind, dann sind   und   eindeutig.

Übung!

Man kann nun mit einigem Aufwand beweisen (siehe [GeiKa02]):

Satz 9.9

Bearbeiten
Seien  . Ist   lokale Lösung von Problem   und ist die LICQ in   erfüllt, dann ist   ein KKT-Punkt von  .

Ob die LICQ tatsächlich in einem mit einem Verfahren berechneten Punkt erfüllt ist, prüft man zumeist nicht nach.

Im Hinblick auf die Berechnung eines KKT-Punktes für nichtlineare Probleme untersuchen wir als nächstes ein Beispiel.

Beispiel 9.10

Bearbeiten

Wir betrachten das Problem

 

Mit Lemma 1.13 prüft man leicht nach, dass   gleichmäßig konvex ist und dass die   konvex sind. Weiter ist    . Also ist das zulässige Gebiet des Problems nichtleer. Insbesondere hat somit das Problem eine eindeutige Lösung   (Satz 1.9).

Weiter ist ein Punkt   ein KKT-Punkt des Problems und damit nach Satz 9.3 Lösung des Problems, wenn   zulässig ist und Multiplikatoren   und   existieren, so dass   das folgende System löst:

(9.12)  
(9.13)  

Dieses System besteht aus 4 Gleichungen in 4 Unbekannten und lautet ausgeschrieben wie folgt:

 

Man hat nun zumindest eine Lösung   dieses Systems zu berechnen, für die   zulässig und   nichtnegativ ist. (Zum Beispiel ist auch   und   eine Lösung des Systems, aber   ist nicht zulässig.) Bei einem so kleinen Problem kann man sich die Arbeit etwas erleichtern, indem man versuchsweise einzelne oder alle   gleich 0 setzt. (Typischerweise liegt eine Lösung des Problems auf dem Rand des zulässigen Gebietes, d. h., ist mindestens eine Restriktion in ihr aktiv.) Wie man durch Einsetzen von   und   für den Fall   erkennt, besitzt das resultierende System die Lösung   und  , wobei   offenbar zulässig und damit die (globale) Lösung des Problems ist. (Man hat   und  , so dass die LICQ in   erfüllt ist und folglich die KKT-Bedingungen auch notwendige Optimalitätsbedingungen für die Lösung   sind.)

In der Praxis stellt die hier aufgezeigte Vorgehensweise aber keine effiziente Methode zur Bestimmung einer Lösung eines nichtlinearen Optimierungsproblems dar. So ist es insbesondere sinnvoll, während des Lösungsprozesses zu untersuchen, ob die erzeugten Näherungen zulässig sind oder ob zumindest der Grad der Verletztheit der Restriktionen abnimmt.


9.3 Optimalitätsbedingungen zweiter Ordnung

Bearbeiten

In der Theorie numerischer Verfahren für nichtlineare restringierte Optimierungsprobleme spielen auch Optimalitätsbedingungen zweiter Ordnung für Problem   eine wichtige Rolle, in der Praxis ist ihre Überprüfung aber meist zu aufwändig. Solche Bedingungen enthalten im Allgemeinen eine Bedingung für die Hesse-Matrix bezüglich   der Lagrange-Funktion zu  . Diese lautet

(9.14)  

und ihre Hesse-Matrix bezüglich   ist im Fall   gegeben durch

(9.15)  

Es gibt nun zahlreiche Varianten solcher Bedingungen zweiter Ordnung. Hier wollen wir im Fall notwendiger Optimalitätsbedingungen solche angeben, welche die LICQ als Constraint Qualification voraussetzen (s. [GeiKa02]):

Satz 9.11

Bearbeiten
Seien  . Ist   lokale Lösung von Problem   und ist die LICQ in   erfüllt, dann ist   ein KKT-Punkt von   und es gilt mit den zu   gehörigen Multiplikatoren   und  
 
für
 

Um zu hinreichenden Optimalitätsbedingungen zweiter Ordnung für beliebige Probleme des Typs   mit Funktionen   zu gelangen, genügt es nicht, statt der positiven Semidefinitheit bezüglich   auf   die positive Definitheit der Hesse-Matrix der Lagrange-Funktion auf   vorauszusetzen, sondern man hat diese auf einem Oberraum   von   zu fordern. Da wir den folgenden Satz weiter unten benötigen, wollen wir ihn auch beweisen.

Satz 9.12

Bearbeiten
Es seien  . Ist   ein KKT-Punkt von Problem   und gilt für zugehörige Multiplikatoren   und  
 
mit
 
und
 
so ist   strikt lokale Lösung von  .

Nach Voraussetzung genügt   den KKT-Bedingungen von   und ist damit  . Sei   keine strikt lokale Lösung von  . Dann ist   insbesondere kein isolierter Punkt von   und es existiert daher eine Folge   mit

 

Wir schreiben nun   in der Form

 

Offenbar ist   und gibt es wegen der Kompaktheit der Einheitskugel eine Teilfolge   von   mit   für ein   mit  . Ohne Beschränkung der Allgemeinheit gelte  .

Für jedes   hat man nun

 

Dividiert man diese Gleichung durch   und bildet man den Grenzübergang für  , so konvergiert die erste eckige Klammer gegen 0, wie man unter Anwendung des Satzes von Taylor schließt, so dass man insgesamt erhält:

 

Analog folgt aus

 

dass gilt:

 

Für jedes  , sofern ein solches existiert, muss ferner   gelten, da die Beziehung   unter Ausnutzung der Bedingung (9.7)

 

einen Widerspruch zu   implizieren würde. Also ist  .

Anwendung des Satzes von Taylor liefert als nächstes, dass für alle   und   Vektoren   auf der Verbindungsstrecke von   und   existieren, so dass gilt:

(9.16)  
(9.17)  
(9.18)  

Multiplikation von (9.17) mit  , von (9.18) mit   und anschließende Addition von (9.16), von (9.17) über   und von (9.18) über   führt weiter unter Ausnutzung der KKT-Bedingungen für   und insbesondere der Tatsache, dass   für alle   gilt, zu der Beziehung

 

Division dieser Ungleichung durch   und anschließender Grenzübergang für   liefern wegen   schließlich

 

Da   gezeigt wurde, widerspricht dies aber der vorausgesetzten positiven Definitheit von   auf  .

q.e.d.

Man beachte, dass für die Mengen   und   aus den Sätzen 9.11 und 9.12 die Inklusion   gilt. Als Beispiel betrachten wir nochmals Beispiel 3.15 aus der Optimierung I.

Beispiel 9.13

Bearbeiten

Gegeben sei das Problem

 

Die Zielfunktion   des Problems kann offenbar mit der Matrix

(9.19)  

in der Form  , geschrieben werden. Die KKT-Bedingungen sind in diesem Fall ein lineares Gleichungssystem von 4 Gleichungen und 4 Unekannten, das die eindeutige Lösung

 

besitzt (vgl. Beispiel 3.15 aus der Optimierung I). Da  , wie man ausrechnet, die Eigenwerte   hat, ist   nicht konvex (und somit insbesondere Satz 9.3 hier nicht anwendbar). Der Punkt   kann daher zunächst nur als ein Kandidat für einen lokalen Minimalpunkt des Problems identifiziert werden.

Man berechnet nun weiter

 

Die Matrix   entspricht also der Matrix   in (9.19). Da sie die Eigenwerte   hat, ist sie bezüglich des ganzen Raumes   weder positiv noch negativ definit. Mit

 

ist aber für alle  

 

Nach Satz 9.12 ist also   eine strikt lokale Lösung des Problems.