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

- Sei
. Dann ist die Menge
(3.1)

- nichtleer, konvex und abgeschlossen.
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
![{\displaystyle v(t):=t{\hat {z}}+(1-t)z^{l}=z^{l}+t({\hat {z}}-zl)\in \mathbb {R} ^{r},\quad t\in [0,1],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/342c229c73c996d46d4d58ea0fc0197760d739bb)
wobei
und nach unserer Annahme
ist. Für jedes
mit
hat man dann
für alle
und für jedes
mit
gilt für
![{\displaystyle v(t_{j})_{j}=0;\quad v(t)_{j}\geq 0,\quad t\in [0,t_{j}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/046a33232a4ea95dc0d4c4d795ff8c33212747da)
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)
![{\displaystyle {\tilde {x}}^{l}:=B_{j(l)}{\tilde {v}}^{j(l)}=Bv^{l}=B\left[t_{l}{\hat {z}}+(1-t_{l})z^{l}\right]=t_{l}x^{*}+(1-t_{l})x^{l}=x^{l}+t_{l}(x^{*}-x^{l}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/122e2c72f174577f71c12a5e39a253a888d4bb1a)
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:
- Es seien
und
gegeben. Dann besitzt das System
(3.4)

- genau dann eine Lösung
, wenn das System
(3.5)

- keine Lösung
hat.
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
![{\displaystyle \|{\hat {v}}-b\|^{2}\leq \|[{\hat {v}}+\theta (v-{\hat {v}})]-b\|^{2},\quad \theta \in (0,1).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71b7f259533754e2937b5391f8269acffa1fe4f1)
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
.
- Es seien
und
gegeben. Dann besitzt das System
(3.7)

- genau dann eine Lösung
, wenn das System
(3.8)

- keine Lösung
hat.
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.
- 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.
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.
- 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.
(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.
- Es seien
konvexe und die
affin-lineare Funktionen. Ist
ein KKT-Punkt von Problem
, so ist
(globale) Lösung von
.
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
:

![{\displaystyle =\sum _{j=1}^{m}\lambda _{j}^{*}[\underbrace {(a^{j})^{T}x^{*}-b_{j}} _{=0}+\underbrace {b_{j}-(a^{j})^{T}x} _{=0}]-\sum _{i\in I(x^{*})}\underbrace {\mu _{i}^{*}} _{\geq 0}[\underbrace {g_{i}(x)} _{\leq 0}-\underbrace {g_{i}(x^{*})} _{=0}]\geq 0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/058abd4026fa90b53f6753bc1b6f0e23cdd7ca13)
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.
- Ein Vektor
heißt Abstiegsrichtung für
in
, falls ein
existiert, so dass gilt:
(3.22)
![{\displaystyle f(x+tp)<f(x),\quad t\in (0,t_{1}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/120c8a2f5d810e286413b453ba9cb7851cd4ad0e)
Das folgende Lemma stellt eine einfache Bedingung bereit, mit deren Hilfe leicht Abstiegsrichtungen in einem vorgegebenen Punkt angegeben werden können.
- Es sei
. Gilt für 

so ist
Abstiegsrichtung für
in
.
Die Definition der Richtungsableitung von
bei
in Richtung
liefert
(3.23)

Folglich gilt für ein
![{\displaystyle {\frac {f(x+tp)-f(x)}{t}}<0,\quad t\in (0,t_{1}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/603f904daf2f96ada3afe8b9c97ac9612dff52f5)
Somit ist (3.22) richtig.
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:
- Eine Richtung
heißt zulässige Richtung für
in
, wenn ein
existiert, so dass gilt:
(3.30)
![{\displaystyle x+tp\in Z,\quad t\in [0,t_{2}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2079a6a0ce145c1872da285075694fa546285f8)
- 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.
- 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)

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

(3.33)

Ferner hat man mit hinreichend kleinen
![{\displaystyle i\notin I(x):\quad (c^{i})^{T}(x+tp)-d_{i}=\overbrace {(c^{i})^{T}x-d_{i}} ^{<0}+t(c^{i})^{T}p\leq 0,\quad t\in (0,\tau _{i}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df3d7a40669e428e6adbba65fe71fc9e19b7ad04)
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.
- Sei
und seien die
und
affin-linear. Ist
lokale Lösung von
, dann ist
ein KKT-Punkt von
.
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:
- Sei
konvex und seien die
und
affin-linear. Es ist
genau dann Lösung von Problem
, wenn
ein KKT-Punkt von
ist.
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.
(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.