In diesem Abschnitt wiederholen wir noch einmal wichtige theoretische Aussagen, vor allem notwendige Bedingungen für Extrema im . In verallgemeinerter Form werden wir auch bei der Optimierung in Funktionenräumen dieselben Techniken verwenden: Nullsetzen von Ableitungen und Behandlung von Nebenbedingungen mithilfe von Lagrange-Multiplikatoren.
2.1 Partielle Differenzierbarkeit und Gradient
Beginnen wir mit der Differentiation von Funktionen in mehreren Veränderlichen.
Sei offen,
,
eine multivariante Funktion. Sei nun
fest gewählt. Dann ist die univariante Funktion (nur eine Größe variabel)
eine partielle Funktion von
.
Ableitung nach :
Dies ist die partielle Ableitung von nach
an der Stelle
. Andere Schreibweisen, z.B.
mit
statt
:
heißt (stetig) partiell differenzierbar, wenn alle partiellen Ableitungen existieren (und stetig sind).
Die partiellen Ableitungen können zusammengefasst und als Vektor geschrieben werden. Diesen nennt man den Gradienten von und schreibt:
Beispiel 2.1: Gradient
Beispiel für eine stetige Funktion, dessen Ableitung nicht stetig ist:
2.2 Totale Differenzierbarkeit und Tangentialebene
Hier zunächst eine Definition.
Definition 2.2: Totale Differenzierbarkeit
heißt (total) differenzierbar in
, wenn die Funktion in diesem Punkt linear durch eine Tangentialebene approximierbar ist, d.h. wenn es einen Vektor
gibt mit
Ist in jedem Punkt
differenzierbar, dann heißt
differenzierbar auf
.
Dabei steht das Landau-Symbol für einen Ausdruck
mit
für
. Zum Beispiel ist
. Bedeutung: Der quadratische Rest geht schneller gegen 0 als der Abstand. Statt der euklidischen Norm könnte man hier auch jede andere verwenden, denn im
ist
für jede beliebige Norm.
Ist in
(total) differenzierbar, schreibt man im Kontext der obigen Definition
statt
. Jede in
differenzierbare Funktion ist dort auch stetig und partiell differenzierbar. Es ist dann stets
(Im Folgenden wollen wir und
synonym verwenden.) Umgekehrt folgt aus der Existenz der partiellen Ableitungen noch nicht die Differenzierbarkeit von
. Dazu muss man noch zusätzlich Stetigkeit voraussetzen.
Satz 2.3: totale und stetig partielle Differenzierbarkeit
Wenn auf der offenen Menge
stetig partiell differenzierbar ist, dann ist
auf
total differenzierbar.
Geometrisch bedeutet die totale Differenzierbarkeit, dass der Graph der Funktion im Punkt
durch die Tangentialebene
approximiert werden kann. Der Normalenvektor der Tangentialebene ist durch
gegeben. Die Gleichung der Tangentialebene lässt sich umformen zu
.
Veranschaulichung:
Für unsere Zwecke und wegen des letzten Satzes ist der Begriff der stetigen partiellen Differenzierbarkeit eigentlich ausreichend. Wir haben die totale Differenzierbarkeit dennoch aufgeführt wegen ihrer geometrischen Anschaulichkeit und weil sie einen Weg zu einer abstrakten Differentialrechnung auf Banachräumen öffnet. Diese abstrakte Form der Ableitung heißt Fréchet-Ableitung und spielt in der funktionalanalytischen Theorie der Variationsrechnung eine große Rolle.
2.3 Richtungsableitung
Partielle Ableitungen zeigen immer in die Richtung einer der Koordinatenachsen. Wir können aber auch in beliebige Richtungen ableiten:
Wenn ist, heißt
die Richtungsableitung von
an der Stelle
in Richtung
.
Tatsächlich genügt im Wesentlichen die Kenntnis der partiellen Ableitungen, um auch alle Richtungsableitungen zu kennen.
Satz 2.4: Richtungsableitungen
Wenn auf der offenen Menge
total differenzierbar ist (insbesondere, wenn
stetig partiell differenzierbar ist), dann hat man für jeden Vektor
mit
:
Satz für das Skalarprodukt:
ist maximal, wenn
.
Man sieht: Der steilste Anstieg der Funktion geschieht in Richtung des Gradienten. Entsprechend zeigt
in Richtung des steilsten Abfalls der Funktionswerte. Diese Beobachtung ist Grundlage des bekanntesten Verfahrens der Optimierung im
, des Gradientenverfahrens, auch Methode des steilsten Abstiegs genannt. Dieses ist ein iteratives Verfahren, das eine Folge von Punkten
produziert, von der man hofft, dass sie gegen ein lokales Minimum der Funktion
konvergiert. Die Folge wird definiert über die Beziehung:
Man geht also von jedem Iterationspunkt aus weiter in Richtung des steilsten Abfalls von Funktionswerten, wobei eine zu wählende reelle Schrittweite ist.
2.4 Lokale und globale Extrema ohne Nebenbedingung
Sei .
ist stationär in
genau dann, wenn
.
hat ein globales Minimum in
, genau dann, wenn
.
hat ein lokales Minimum in
, genau dann, wenn es eine Umgebung
gibt mit
.
Die Definition für Maxima und Maximalstellen sind analog. Ein Extremum ist ein Minimum oder ein Maximum.
Der folgende Satz gibt eine notwendige Bedingung für eine Extremalstelle.
Satz 2.6: Lokale Extrema ohne Nebenbedingung
Es sei eine
-Funktion. Falls
eine lokale Extremstelle in
ist, dann folgt daraus
. Dies gilt nur, wenn
eine offene Menge ist, da bei einem Minimum auf dem Rand der Gradient nicht 0 sein muss.
Beweis:
Nach der Definition der Richtungsableitung in Satz 2.4 darf es an einer Extremalstelle keine Auf- oder Abstiegsrichtung geben. Wäre nämlich
, dann hätte die Funktion
an der Stelle
die Ableitung
und könnte dort somit kein Extremum haben.
Der Satz schränkt die Kandidatenmenge für Extremalstellen im Inneren des Definitionsbereichs von auf die stationären Stellen ein. Löst man das im Allgemeinen nichtlineare Gleichungssystem
, so befinden sich die lokalen (und damit auch insbesondere die globalen) Extrema innerhalb der Lösungsmenge. Umgekehrt ist aber nicht jede stationäre Stelle ein Extremum. Ist sie es nicht, nennt man sie einen Sattelpunkt.
Ob man das Gleichungssystem praktisch tatsächlich lösen kann, steht freilich auf einem anderen Blatt. Schafft man es tatsächlich, dann kann man den folgenden Satz heranziehen, um festzustellen, ob ein Kandidat auch tatsächlich ein Extremum ist. Um diesen Satz prägnanter formulieren zu können, führen wir vorher noch die folgende Bezeichnung ein:
Für ein offenes heißt die für
definierte Matrix
Hesse-Matrix von in
.
Die Hesse-Matrix ist die Verallgemeinerung der zweiten Ableitung für Funktionen in mehreren Veränderlichen. Bekanntlich hat eine -Funktion
eine Minimalstelle
, wenn
und
.
Für Funktionen in Variablen verallgemeinert sich das:
entspricht
und entspricht
ist positiv definit.
Eine symmetrische Matrix ist positiv definit genau dann wenn
. Dabei darf
nur gelten, wenn
ist.
Wenn stattdessen gilt, heißt
negativ definit. Gibt es sowohl einen Vektor
mit
als auch einen Vektor
mit
, dann heißt die symmetrische Matrix
indefinit.
Satz 2.7: Hinreichende Bedingung für lokale Extrema ohne Nebenbedingung
Es sei eine
-Funktion und
ein stationärer Punkt von
. Dann folgt:
positiv definit: lokales Minimum
negativ definit: lokales Maximum
indefinit: Sattelpunkt
Beweis:
Der Sachverhalt wird einsichtig, wenn man nach der mehrdimensionalen Taylorformel in
durch eine Schmiegequadrik approximiert: Zu jedem
gibt es ein
auf der Strecke von
nach
, so dass
Da ein stationärer Punkt ist, gilt
und damit auch
. Wir erhalten also:
Wenn ein lokales Minimum ist, muss also gelten:
. Dies ist genau dann erfüllt, wenn
negativ definit ist, da dann aufgrund der Stetigkeit der zweiten Ableitung auch
negativ definit ist. Analoges gilt für Maximum und Sattelpunkt.
2.5 Extremum mit Gleichungs-Nebenbedingung
Selten wird in der Praxis nach einem Extremum gefragt, ohne dass weitere einschränkende Nebenbedingungen gestellt werden. Wir betrachten zuerst Nebenbedingungen in Gleichungsform:
Sei offen,
,
. Wir suchen das Minimum von
unter der Nebenbedingung
, also:
Die Nebenbedingungen definieren eine Teilmenge von :
löst das Minimierungsproblem mit Nebenbedingung genau dann, wenn es eine Umgebung
gibt mit
.
Sehen wir uns dazu erst einmal eine einzige Nebenbedingung an. Wie wir wissen, zeigt der (negative) Gradient einer Funktion in die Richtung des steilsten Anstiegs (Abstiegs) von Funktionswerten. Im folgenden Bild hat einen Anteil orthogonal zu
und damit tangential zur Höhenlinie (Niveaulinie, contour line)
:
Das bedeutet, dass man längs der Höhenlinie noch zu Werten
und
kommt. Also kann
kein lokales Extremum sein. Anders im Punkt
: Dort sind die Gradienten
und
kollinear. Die Höhenlinien von
und
berühren sich tangential. Von diesem Punkt aus gelangt man zu größeren oder kleineren Funktionswerten von
nur dann, wenn man die Nebenbedingung
verlässt.
ist somit ein lokales Extremum.
Der eben entwickelten Anschauung nach erwartet man eine Aussage der Form (noch ganz ohne Voraussetzungen formuliert): “Ist ein lokales Extremum von
unter der Nebenbedingung
, dann gibt es ein
so, dass
.”
Im folgenden Satz wird diese Aussage präzise formuliert, und zwar gleich für den Fall mehrerer Nebenbedingungen.
Satz 2.8: Lagrange-Multiplikatoren
Sei offen und
sowie
seien
-Funktionen. Ist
ein lokales Extremum von
unter der Nebenbedingung
und sind weiterhin die Gradienten
linear unabhängig, dann gibt es einen Vektor
, die sogenannten Lagrange-Multiplikatoren, so dass
Mit der Lagrange-Funktion
lässt sich dies schreiben als , wobei
bedeutet, dass der Gradient nur bezüglich
genommen wird.
Die Bedingung besagt, dass man zur Vergrößerung oder Verkleinerung von Funktionswerten
von
aus in eine Richtung gehen müsste, die notwendig mindestens eine Nebenbedingung verletzen würde.
Vorausgesetzt wird die lineare Unabhängigkeit der Gradienten im lokalen Extremum. Dies nennt man Regularitätsbedingung. Die Regularitätsbedingung wird beim Beweis des Satzes benötigt, um zu zeigen, dass man im Extremum “die Nebenbedingungen linearisieren” (durch den Tangentialraum ersetzen) kann.
Der Satz gibt eine notwendige Bedingung für lokale Extrema , die der Regularitätsbedingung genügen. Ex könnte jedoch durchaus lokale Extrema geben, die der Regularitätsbedingung nicht genügen. Für solche Extrema lässt sich im Allgemeinen die Existenz von Lagrange-Multiplikatoren nicht beweisen.
Aus Unbekannten
und
Nebenbedingungen
erhalten wir so
Gleichungen
und
Gleichungen für die Nebenbedingungen. Insgesamt haben wir also
Gleichungen und
Unbekannte. Das resultierende nichtlineare Gleichungssystem kann z.B. mit Newton numerisch gelöst werden. Nicht reguläre Stellen müssen daneben noch gesondert untersucht werden.
Beispiel 2.9: Lagrange-Multiplikatoren
Der Quader hat das Volumen
. Gesucht wird das Maximum von
udNB
. Der Quader soll also innerhalb des durch
,
und
festgelegten Ellipsoids liegen.
Es muss das folgende Gleichungssystem ausgewertet werden:
Wir erhalten daraus die Gleichungen:
Dies sind 4 Gleichungen für 4 Unbekannte, nämlich ,
,
und
. Wir können auflösen:
Es gilt , da sonst das Volumen 0 wäre. Wir kürzen:
2.6 Extremum mit Ungleichungs-Nebenbedingung
Nebenbedingungen kommen nicht nur in Gleichungsform vor, sondern auch als Ungleichungen. Wir haben dann ein Problem der Form:
Sei offen und
,
und
seien
-Funktionen.
Minimierungsaufgabe:
Nebenbedingung:
Hier ist komponentenweise zu lesen (Vektoren können nicht geordnet werden).
Menge der Punkte, die alle Nebenbedingungen erfüllen:
Zur Veranschaulichung betrachten wir zunächst eine einzige Nebenbedingung in Ungleichungsform und sehen uns dazu die folgende Skizze an:
Offenbar kommt es hier darauf an, welche Art von Extremum wir suchen. Wenn minimiert werden soll, so haben wir in
ein lokales Minimum gefunden: Zur Verkleinerung von Funktionswerten über
hinaus müsste man von
in Richtung des negativen Gradienten
gehen. Dann würde man aber den zulässigen Bereich verlassen.
In Punkt hingegen hat
einen zu
orthogonalen Anteil. Man kann also den Funktionswert von
durch einen Schritt in einer Richtung verringern, der die Nebenbedingung nicht verletzt.
Der Beweis des folgenden Satzes beruht wiederum auf einer Linearisierung von Nebenbedingungen, allerdings nur jener, die im Optimum zum Tragen kommen. Dazu definieren wir wie folgt.
Definition 2.10: Regularität von Nebenbedingungen
Es seien offen und
,
und
seien
-Funktionen. Es sei weiterhin
.
Für jedes sei
die Indexmenge aktiver Ungleichungsnebenbedingungen.
Ein heißt regulär, wenn die Gradienten
und
linear unabhängig sind für
.
In der Menge werden die Indizes aller in
aktiven Nebenbedingungen versammelt. Wenn
ist, bedeutet dies
. Wegen der Stetigkeit von
bleibt diese Nebenbedingung dann auch noch in einer Umgebung von
erfüllt.
Satz 2.11: Satz von Kuhn-Tucker
Es seien offen und
,
und
seien
-Funktionen. Es sei weiterhin
.
sei Lösung der Minimierungsaufgabe. Dann existieren
so, dass
Die Bedingung bedeutet, dass der Multiplikator
, der zu einer inaktiven Nebenbedingung
gehört, verschwindet.
Der Satz von Kuhn-Tucker ist offensichtlich eine Verallgemeinerung des Satzes 2.8 über die Lagrange-Multiplikatoren und beinhaltet diesen als Spezialfall.
Die Frage nach hinreichenden Bedingungen für Extrema unter Nebenbedingungen lassen wir an dieser Stelle offen. Sie wird in allgemeinerem Rahmen bei der Optimierung in Funktionenräumen wieder aufgegriffen.