Benutzer:Stepri2005/Kurs:Optimierung/Optimalitätskriterien für linear restringierte Optimierungsprobleme

Aus Wikiversity

3.1 Das Farkas-Lemma und Folgerungen[Bearbeiten]

Das Hauptziel dieses Kapitels ist es, Optimalitätsbedingungen für lokale Minimalpunkte linear restringierter Optimierungsprobleme bereit zu stellen. Dazu benötigen wir das sog. Farkas-Lemma sowie Folgerungen aus diesem Lemma, das bzw. die wir in diesem Abschnitt beweisen wollen. Für den Beweis des Farkas-Lemmas benötigen wir die folgende Aussage, deren Beweis man überspringen mag. Dabei ist

Lemma 3.1[Bearbeiten]

Sei . Dann ist die Menge
(3.1)
nichtleer, konvex und abgeschlossen.

Beweis.[Bearbeiten]

Offenbar ist Element von . Für gilt weiter und mit gewissen . Für hat man daher sowie

Folglich ist konvex. Den Beweis der Abgeschlossenheit von führen wir mittels vollständiger Induktion über die Spaltenzahl von .

Für setzen wir

Für erhalten wir dann mit die Halbgerade

welche, wie man sich leicht klarmacht, abgeschlossen ist. Wir nehmen nun an, dass die Menge bei beliebigem für jedes abgeschlossen ist.

Sei und eine Folge in mit für ein . Insbesondere gilt also mit einem . Weil die Menge

ein linearer Teilraum des und ein solcher abgeschlossen ist, gibt es weiter ein mit . Da anderenfalls alles gezeigt wäre, nehmen wir an, dass , d. h. für alle mit gilt.

Sei nun

wobei und nach unserer Annahme ist. Für jedes mit hat man dann für alle und für jedes mit gilt für

Ist weiter

und , so folgt

(3.2) für ein .

Sind und die Matrix und der Vektor, die aus und durch Streichung der -ten Spalte bzw. Komponente hervorgehen, so erhalten wir schließlich

(3.3)

Die unendliche Folge muss mindestens ein unendlich oft enthalten, so dass mit für eine Teilfolge von folgt. Mit ergibt sich aus (3.3) . Da die Menge nach der Induktionsannahme abgeschlossen ist, erhalten wir , was wegen der Annahme widerspricht.

q.e.d.

Das Farkas-Lemma lautet nun:

Lemma 3.2 (Farkas)[Bearbeiten]

Es seien und gegeben. Dann besitzt das System
(3.4)
genau dann eine Lösung , wenn das System
(3.5)
keine Lösung hat.

Beweis.[Bearbeiten]

Existiert ein , welches (3.4) erfüllt, so folgt und damit wegen im Fall notwendig . Also hat dann das System (3.5) keine Lösung.

Wir beweisen nun umgekehrt: Besitzt das System (3.4) keine Lösung, d. h. ist nicht Element der Menge

so hat das System (3.5) eine Lösung. Wir zeigen dazu insbesondere, dass für ein Vektor existiert mit

Denn mit hat man dann

für alle bzw. für alle , woraus man erschließt. Nach Lemma 3.1 ist die Menge nichtleer, konvex und abgeschlossen.

Sei also . Nach Beispiel 2.34 ist die Zielfunktion des quadratischen Optimierungsproblems

gleichmäßig konvex, so dass dieses Problem gemäß Satz 2.41 eine eindeutige Lösung besitzt. Weiter ist für alle . Wegen der Minimaleigenschaft von nimmt die Funktion

ihr Minimum für an, so dass gilt:

(3.6) bzw. .

Sei nun . Dann ist auch für alle und folglich wegen der Optimalität von

Letzteres impliziert nach Ausmultiplikation der Normen und Streichung identischer Terme auf beiden Seiten der Ungleichung

und somit nach Division durch , Grenzübergang für und Anwendung von (3.6):

Für bekommt man demnach für alle . Mit (3.6) folgt ferner

Da und ist, ist und daher , was schließlich impliziert.

q.e.d.

Eine Aussage vom Typ des Farkas-Lemmas bezeichnet man als Alternativsatz. Ein solcher Satz macht eine Aussage der Art, dass ein lineares System genau dann gelöst werden kann, wenn ein anderes lineares System nicht lösbar ist. Eine weitere solche Alternativaussage und eine Folgerung daraus, welche wir brauchen werden, wollen wir als nächstes aus dem Farkas-Lemma ableiten. Mit für und meinen wir dabei einen Spaltenvektor .

Korollar 3.3[Bearbeiten]

Es seien und gegeben. Dann besitzt das System
(3.7)
genau dann eine Lösung , wenn das System
(3.8)
keine Lösung hat.

Beweis.[Bearbeiten]

Für den Vektor definiere man Vektoren und durch

für . Dann gilt mit . Wegen

ist das System (3.7) somit äquivalent mit dem System für

Nach dem Farkas-Lemma besitzt letzteres System genau dann eine Lösung, wenn das System

keine Lösung hat. Offenbar ist letzteres System von Ungleichungen gleichbedeutend mit demjenigen in (3.8).

q.e.d.

Korollar 3.4[Bearbeiten]

Es seien und und es existiere ein mit
(3.9)
Besitzt dann das System
(3.10)
keine Lösung, so hat das System
eine Lösung.

Beweis.[Bearbeiten]

Es sei , z. B. , Lösung des Systems

(3.11)

und erfülle die Ungleichungen in (3.9). Für jedes folgt dann

Da das System in (3.10) keine Lösung besitzt, muss ferner gelten. Grenzübergang für liefert . Wegen (3.11) hat also das System

keine Lösung. Die Behauptung folgt nun mit Korollar 3.3.

q.e.d.

3.2 Die Karush-Kuhn-Tucker Bedingungen[Bearbeiten]

Wir betrachten nun das allgemeine restringierte Optimierungsproblem

Die zulässige Menge von bezeichnen wir mit

(3.12)

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 .

Wir führen nun Bedingungen ein, welchen in der restringierten Optimierung eine zentrale Rolle zukommt.

Definition 3.5[Bearbeiten]

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

Die Bedingungen (3.13) und (3.14) sind gleichbedeutend mit der Forderung, dass ein zulässiger Punkt für Problem , d. h., dass ist. Die Gleichung (3.15) drückt aus, dass sich der Gradient von als Linearkombination der Gradienten der und schreiben lässt, wobei die Koeffizienten vor den Gradienten der Funktionen, die zu den Ungleichungsrestriktionen gehören, gemäß (3.17) nichtnegativ sein und der Bedingung (3.16) genügen müssen. Diese Bedingung (3.16) bezeichnet man auch als Komplementaritätsbedingung, weil sie impliziert, dass - also in gewissem Sinne komplementär - mindestens einer der beiden Faktoren und identisch Null sein muss. Man spricht von strikter Komplementaritätsbedingung, wenn zusätzlich gilt, also genau einer der beiden Faktoren in (3.16) für jedes identisch Null ist.

In Abschnitt 3.3 werden wir zeigen, dass jeder lokale Minimalpunkt von Problem im Fall, dass alle Restriktionen in linear sind, ein KKT-Punkt von ist. Für linear restringierte Optimierungsprobleme des Typs sind also die KKT-Bedingungen notwendige Optimalitätsbedingungen erster Ordnung. (Wie man beweisen kann, sind sie dieses auch für Probleme mit beliebigen Funktionen , sofern das zulässige Gebiet von eine sog. Constraint Qualification erfüllt.)

Manche Autoren nennen die Bedingungen (3.13)–(3.17) auch Kuhn-Tucker-Bedingungen und nehmen dabei Bezug auf einen Satz aus dem Jahre 1951 von Kuhn und Tucker. Man stellte später jedoch fest, dass diese Bedingungen bereits 1939 in einer Master-Thesis von Karush angegeben worden waren, so dass man dessen Namen heute zumeist in ihrer Benennung mit einbezieht.

Die Komponenten der Vektoren und in den KKT-Bedingungen bzw. auch diese Vektoren selbst werden als (Lagrange-)Multiplikatoren bezeichnet. Lagrange hatte schon Optimierungsprobleme mit Nebenbedingungen untersucht, allerdings nur solche mit Gleichungsnebenbedingungen. Deshalb wird auch manchmal nur bei von Lagrange-Multiplikatoren gesprochen.

Einige Beobachtungen im Zusammenhang mit den KKT-Bedingungen fassen wir in der folgenden Bemerkung zusammen.

Bemerkung 3.6[Bearbeiten]

(i) Wenn keine Restriktionen vorliegen, d. h., wenn in Problem ist, reduzieren sich die Bedingungen (3.13)–(3.17) auf die bekannte Bedingung .

(ii) Da für die kein Vorzeichen festgelegt ist, kann man in (3.15) statt auch schreiben.

(iii) Erfüllt die KKT-Bedingungen, so ist die Komplementaritätsbedingung

(3.18)

in (3.16) wegen und äquivalent mit der Bedingung

(iv) Die Funktion

(3.19)

bezeichnet man als Lagrange-Funktion. Mit ihr lässt sich die Beziehung für in (3.15) auch schreiben in der Form

(v) Im Fall , d. h. im Fall, dass keine Ungleichungsrestriktionen in vorliegen, reduzieren sich die KKT-Bedingungen auf das Gleichungssystem

Dieses Gleichungssystem, welches aus Gleichungen in den Unbekannten besteht, lässt sich - nach Streichung von in - auch in der folgenden Form darstellen:

(3.20)

(vi) Weil gilt, kann man die Komplementaritätsbedingung (3.18) durch die Forderung „ “ ersetzen. Folglich sind die KKT-Bedingungen (3.13)–(3.17) äquivalent mit dem System

(3.21)

Man beachte aber, dass bei dieser Schreibweise die Anzahl der Summenglieder von abhängt und sich daher die Bedingung in (3.21) nicht durch den Gradienten der Funktion

ausdrücken lässt, da diese Funktion möglicherweise in nicht differenzierbar ist.

Für eine konvexe Funktion ist die Bedingung hinreichend dafür, dass ein (globaler) Minimalpunkt von ist. Diese Aussage können wir nun als erstes im folgenden Sinne auf restringierte konvexe Optimierungsprobleme verallgemeinern.

Satz 3.7[Bearbeiten]

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

Beweis.[Bearbeiten]

Die seien dargestellt in der Form und erfülle die KKT-Bedingungen von . Unter den gegebenen Voraussetzungen ist die zulässige Menge von gemäß Lemma 2.27 konvex. Insbesondere gilt . Daher schließt man unter Berücksichtigung von Satz 2.28 und Bemerkung 3.6 (vi) für alle :

Also ist optimal für Problem .

3.3 Abstiegsrichtung und zulässige Richtung[Bearbeiten]

Da wir daran interessiert sind, im Rahmen von Verfahren zur Minimierung einer Funktion den Funktionswert zu verkleinern, führen wir die nachstehende Definition ein.

Definition 3.8[Bearbeiten]

Ein Vektor heißt Abstiegsrichtung für in , falls ein existiert, so dass gilt:
(3.22)

Das folgende Lemma stellt eine einfache Bedingung bereit, mit deren Hilfe leicht Abstiegsrichtungen in einem vorgegebenen Punkt angegeben werden können.

Lemma 3.9[Bearbeiten]

Es sei . Gilt für

so ist Abstiegsrichtung für in .

Beweis.[Bearbeiten]

Die Definition der Richtungsableitung von bei in Richtung liefert

(3.23)

Folglich gilt für ein

Somit ist (3.22) richtig.

Bemerkung 3.10[Bearbeiten]

Im Fall ist offenbar

gemäß Lemma 3.9 eine Abstiegsrichtung für in .

Nach (3.23) hat man für alle genügend kleinen

mit für . Speziell folgt im Fall einer linearen Funktion, also im Fall für ein , dass ist, denn in diesem Fall hat man und somit

Im Hinblick auf einen möglichst großen Abstieg für in , also einen möglichst kleinen Wert , macht es demnach Sinn, nach einer auf 1 normierten Richtung zu fragen, welche im Fall das Problem

(3.24)

löst. Die eindeutige Lösung dieses Problems ist

(Denn mit der Cauchy-Schwarz-Ungleichung kann man den Zielfunktionswert von Problem (3.24) für alle zulässigen durch

(3.25)

nach unten abschätzen, wobei die untere Schranke offenbar gerade für angenommen wird und damit den Minimalwert des Problems definiert. Die Eindeutigkeit von folgt aus der Tatsache, dass man und hat und daher Gleichheit in der Cauchy-Schwarz-Ungleichung in (3.25) genau dann vorliegt, wenn für ein ist. Mit (3.25) ergibt sich für als einzige mögliche Wahl .)

Die Richtung nennt man daher auch die Richtung des steilsten Abstiegs für in . Man kann sie lokal - und im linearen Fall auch global - als „beste“ Abstiegsrichtung ansehen. Für nichtlineare Funktionen muss sie dies jedoch global gesehen nicht sein. Auch im Gebirge ist ja die Richtung, die vom Standpunkt aus - vielleicht nur für ein kleines Stück - den steilsten Abstieg liefert, global gesehen nicht notwendig die beste Richtung für einen Abstieg ins Tal.


Im Fall linearer Restriktionen stellen wir nun die und mit Vektoren und Zahlen dar in der Form

(3.26)

In diesem Fall lautet die zulässige Menge von

(3.27)

und hat man

(3.28)

Lineare Ungleichungs- und Gleichungsrestriktionen gibt man oft auch in Matrix-Vektor-Schreibweise an. Sind und die Matrizen mit den Zeilen bzw. und und die Vektoren mit Komponenten bzw. , so bekommt Problem die Gestalt

Insbesondere hat man also

(3.29)

Für Verfahren, die eine Folge von zulässigen Punkten für generieren (viele Verfahren tun dies nicht), ist es erforderlich, in einem Punkt diejenigen Richtungen zu kennen, in die man sich ein Stück von aus weg bewegen kann, ohne zu verlassen und in die man den Funktionswert von gleichzeitig reduzieren kann. Wir definieren daher weiter:

Definition 3.11[Bearbeiten]

Eine Richtung heißt zulässige Richtung für in , wenn ein existiert, so dass gilt:
(3.30)
Eine solche Richtung heißt zulässige Abstiegsrichtung für in , wenn auch Abstiegsrichtung für in ist.

In diesem Zusammenhang machen wir die folgende Beobachtung.

Lemma 3.12[Bearbeiten]

Die und seien affin-lineare Funktionen wie in (3.26) und es sei . Dann ist genau dann eine zulässige Richtung in , wenn folgendes System löst:
(3.31)

Beweis.[Bearbeiten]

Sei und Lösung von (5.3). Dann gilt

(3.32)
(3.33)

Ferner hat man mit hinreichend kleinen

Also impliziert (5.3) die Bedingung (3.30) mit . Umgekehrt schließt man sofort mit der Bedingung (3.30), dass (3.32) und (3.33) gültig und damit die Beziehungen in (5.3) erfüllt sind.

q.e.d.

Erfüllt also die Bedingungen in (5.3) und ist zusätzlich , so ist offenbar zulässige Abstiegsrichtung für Problem im linear restringierten Fall.

3.4 Optimalitätsbedingungen für Probleme mit linearen Restriktionen[Bearbeiten]

Wir betrachten nun den Fall eines linear restringierten Optimierungsproblems. Die Nebenbedingungen und der zulässige Bereich haben also die Form wie in (3.26) und (3.27). Für diesen Fall können wir die folgende wichtige Aussage beweisen.

Satz 3.13[Bearbeiten]

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

Beweis.[Bearbeiten]

Die und seien wie in (3.26) dargestellt. Da eine lokale Lösung des Problems ist, ist und kann es keine zulässige Abstiegsrichtung für in bezüglich geben. Mit Lemma 3.12 können wir somit schließen, dass das System

keine Lösung besitzt. Korollar 3.3 garantiert daher die Existenz von Multiplikatoren und , so dass mit (3.28) gilt:

(3.34)

Setzen wir für , so folgt die Behauptung.

q.e.d.

Die KKT-Bedingungen sind also notwendige Optimalitätsbedingungen erster Ordnung für das Optimierungsproblem , wenn alle Nebenbedingungen darin linear sind. Man beachte aber, dass ein lokaler Minimalpunkt von kein KKT-Punkt von sein muss, wenn mindestens ein eine nichtlineare konvexe Funktion ist. Für linear restringierte konvexe und somit insbesondere für konvexe quadratische Probleme können wir aber noch aus den Sätzen 3.7 und 3.13 zusammenfassend schließen:

Korollar 3.14[Bearbeiten]

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

Beispiel 3.15[Bearbeiten]

Berechnen Sie den eindeutigen KKT-Punkt und den zugehörigen eindeutigen Multiplikator des Problems

Die KKT-Bedingungen (3.13)–(3.17) lauten in diesem Fall

Dieses Gleichungssystem hat die eindeutige Lösung . Die Zielfunktion des Problems kann mit

(3.35)

in der Form , geschrieben werden. Da , wie man ausrechnet, die Eigenwerte hat, ist nicht konvex und sind somit die KKT-Bedingungen für dieses Problem keine hinreichenden Optimalitätsbedingungen. Der Punkt kann somit zunächst nur als ein Punkt identifiziert werden, der mit die Optimalitätsbedingungen erster Ordnung erfüllt und somit ein Kandidat für einen lokalen Minimalpunkt des Problems ist.


Wir wollen uns noch weitere Beispiele anschauen.

Beispiel 3.16[Bearbeiten]

(1) Es sei symmetrisch und es seien und . Man betrachte das quadratische Optimierungsproblem

(3.36)

Schreibt man

wobei die -te Spalte der Einheitsmatrix und die -te Spalte von ist (vgl. (3.29)), so ergibt sich

Verwendet man, wie es häufig getan wird, die Variablen und und berücksichtigt man, dass die Komplementaritätsbedingung wegen und mit der Gleichung äquivalent ist, so gelangt man zu der folgenden Form der KKT-Bedingungen in den Variablen :

(3.37)

Wenn positiv semidefinit ist, ist das Problem (3.36) konvex, so dass nach Korollar 3.14 genau dann eine Lösung des Problems ist, wenn und existieren, so dass das System (3.37) löst.

(2) Wie zuvor seien eine symmetrische Matrix, und und gegeben sei jetzt das nur gleichungsrestringierte quadratische Optimierungsproblem

(3.38)

Mit lauten die KKT-Bedingungen (3.13)–(3.17) in diesem Fall

Dies ist ein lineares Gleichungssystem mit Gleichungen und Unbekannten , welches sich nach Multiplikation der zweiten Gleichung mit in der folgenden Matrix-Vektor-Form mit einer symmetrischen Systemmatrix darstellen lässt:

(3.39)

Für positiv semidefinites ist das Problem (3.38) konvex, so dass dieses Problem gemäß Korollar 3.14 genau dann löst, wenn ein existiert, so dass eine Lösung von (3.39) ist.

Ist positiv definit und , so ist die Lösungsmenge des Systems nichtleer und besitzt das Problem (3.38) genau eine Lösung (vgl. Beispiel 2.42). Diese Lösung und den zugehörigen, in diesem Fall eindeutigen Lagrange-Multiplikator kann man explizit angeben, was zumindest für theoretische Zwecke hilfreich ist. Und zwar liefert die erste Gleichung in (3.39) die Identität

(3.40)

Eingesetzt in die zweite Gleichung von (3.39) ergibt sich die Beziehung

Da die Matrix gemäß Lemma 2.21 invertierbar ist, erhalten wir

(3.41)

Setzen wir in (3.40) ein, so bekommen wir schließlich

(3.42)

(3) Seien mit und gegeben. Möchte man unter den Lösungen von eine hervorheben, so wählt man häufig diejenige, welche unter allen Lösungen die kleinste -Norm bzw., was äquivalent damit ist, die kleinste quadrierte -Norm besitzt, welche also das Problem

(3.43)

löst. Dieses Problem ist offenbar ein Spezialfall des Problems (3.38) mit und der symmetrischen, positiv definiten Matrix . Somit ist

die eindeutige Lösung von Problem (3.43) und

der zugehörige Multiplikator. Da die Matrix eine (spezielle) Lösung des Systems liefert und im Fall mit identisch ist, bezeichnet man sie als (Moore-Penrose-)Pseudoinverse von .

Um im Einzelfall zu erhalten, bestimmt man den Vektor , indem man die eindeutige Lösung des linearen Gleichungssystems berechnet. Da die Matrix nach Lemma 2.21 positiv definit ist, bietet sich dafür eine Cholesky-Zerlegung an.