Im Grunde haben wir von Anfang an Variationsaufgaben mit Nebenbedingungen betrachtet: In Aufgabe (A) etwa war bereits gefordert, dass Lösungen feste Randwerte annehmen. Ebenso hatten wir schon den Fall, dass eine Lösungskurve eine vorgegebene Kurve erreichen soll – dies hatte zur Transversalitätsbedingung geführt. Diese Arten von Nebenbedingungen ließen sich durch geeignete Wahl von Ansatzfunktionen abhandeln.
In diesem Abschnitt soll es um zwei andere Arten von Nebenbedingungen gehen, die in der Praxis wichtig sind. Zuerst betrachten wir sogenannte isoperimetrische Probleme. Bei diesen wird gefordert, dass die gesuchte Lösung gewisse Integralbedingungen erfüllen muss – der Prototyp hierfür ist das Problem der Dido. Die andere Art sind Nebenbedingungen in Gleichungsform, bei denen nicht nur wie in (A) eine Festlegung für einzelne (End)punkte der Lösung getroffen wird, sondern die Lösung in allen Punkten Nebenbedingungen erfüllen muss.
6.1 Isoperimetrische Probleme
Es seien mit
. Es seien
und
Funktionen wie die Lagrange-Funktion in Satz 3.7 (also stetig und stetig differenzierbar in den beiden letzen Variablen). Dann ist eine Lösung
des Problems
gesucht, die die Nebenbedingungen und
mit einer Konstanten erfüllt.
Zunächst wird gezeigt, dass das berühmte Problem der Dido die Form von Aufgabe (C) hat. Das Problem der Dido lautet folgendermaßen:
Es seien mit
und
. Gesucht ist eine Kurve vorgegebener Länge
, die
mit
verbindet und dabei mit der Strecke
die größte Fläche einschließt.
Wir vereinfachen die Aufgabe, indem wir voraussetzen, die gesuchte Kurve sei durch eine -Funktion
gegeben. Dann haben wir das folgende Problem.
Definition: Problem der Dido
Maximiere das Funktional
unter allen Funktionen , die die Nebenbedingungen
sowie
erfüllen.
Diese Aufgabe ist in der Tat von der Form der Aufgabe (C). Als Funktion haben wir hier
(in einer mathematisch zweifelhaften, aber suggestiven Schreibweise, in der und
die Doppelbedeutung von Funktionen und Variablen haben).
Für Optimierungsprobleme im mit Nebenbedingungen in Form von Gleichungen und Ungleichungen hatten wir in den Sätzen 2.8 und 2.11 notwendige Optimalitätsbedingungen formuliert.
Auch bei der Optimierung in Funktionenräumen gibt es eine Lagrange-Theorie und es kann unter gewissen Regularitätsbedingungen die Existenz von Lagrange-Multiplikatoren wie im Satz von Kuhn-Tucker gezeigt werden. Solche Aussagen sind allerdings schwierig zu beweisen und erfordern einen Einstieg in die funktionalanalytische Theorie der Dualräume. Es ist andererseits sehr einfach möglich, die Idee eines Lagrange-Ansatzes zu motivieren. Grundlage dabei ist das folgende Lemma.
Lemma 6.1: Lagrange-Lemma
Es sei eine beliebige Menge und
,
und
. Die Funktion
ist auf der sogenannten Restriktionsmenge
zu minimieren.
Es seien und
so, dass
eine Minimallösung der Funktion
auf ist. Dann ist
eine Minimallösung von
auf
.
Bemerkungen
- Die Menge
kann insbesondere eine Teilmenge eines Funktionenraums sein, z.B.
im Fall von Variationsaufgabe (C).
- Das Lagrange-Lemma behandelt einen viel allgemeineren Fall als den von Variationsaufgabe (C):
- Die Menge
kann auch eine Menge von Kurven und nicht nur von skalaren Funktionen sein. Ebenso ist das Auftreten höherer Ableitungen oder mehrerer unabhängiger Variablen erlaubt
- es können mehrere Nebenbedingungen vorkommen
- Ungleichungsnebenbedingungen sind erlaubt
- Nebenbedingungen müssen nicht die Integralform wie das Funktional
in (C) haben
- Die Menge
- Spezialisierung des Lemmas auf Gleichungsnebenbedingungen: Setze alle
, insbesondere
. Die Menge
wird nicht mehr benötigt.
- Anwendung auf die Variationsaufgabe (C): Setze
und
als einzige Gleichungsnebenbedingung.
Beweis von Lemma 6.1
Für beliebiges haben wir wegen der Voraussetzungen an
und mehr ist nicht zu zeigen.
Der Beweis ist deswegen so einfach, weil die Aussage des Lagrange-Lemmas nicht sehr weit reicht: Sowohl die Existenz der Multiplikatoren wird vorausgesetzt (und nicht etwa deren Existenz vorhergesagt) als auch die Existenz einer Minimallösung , die alle Nebenbedingungen erfüllt.
Trotz seiner Einfachheit beinhaltet das Lagrange-Lemma die großartige Idee, die Nebenbedingungen direkt an die zu minimierende Funktion zu koppeln. Man kann deswegen das Lemma 6.1 in Form eines Ansatzes für den gesuchten Minimierer verwenden.
Zur Anwendung des Lagrange-Lemmas bei der Lösung von Variationsaufgabe (C) geht man nach folgendem Rezept vor:
- Man bilde die erweiterte Lagrange-Funktion
mit einer noch unbekannten Konstanten
.
- Man versuche, das zugehörige Funktional
zu minimieren. Dazu ist in der Regel die Lösung der Euler-Gleichung
erforderlich.
- Man versuche, den Parameter
so zu bestimmen, dass der Minimierer von
(die Extremalen von
) auch noch die Nebenbedingung erfüllen. Das bedeutet, dass neben der Euler-Gleichung noch eine weitere Gleichung für die zusätzlich ins Spiel gebrachte Unbekannte zu lösen ist.
Gelingt die Ausführung dieser Schritte, dann hat man nach Lemma 6.1 die Gewähr, einen Minimierer von gefunden zu haben, der die Nebenbedingung erfüllt.
Umgekehrt sagt das Lemma 6.1 jedoch nicht, dass diese Vorgehensweise immer funktioniert. Insbesondere wird nicht ausgesagt, dass es immer eine Konstante so gibt, dass der Minimierer von
unter der Nebenbedingung
unter den Extremalen von
zu finden ist. Tatsächlich lässt sich die Existenz eines solchen
beweisen, wenn die Nebenbedingung eine gewisse Regularitätsbedingung erfüllt.
Beispiel 6.2: Lösung des Problems der Dido
Wir können die Menge definieren als
.
Die Randbedingungen stecken damit bereits in und wir können mit der Notation von Lemma 6.1
und
setzen. Die Maximierung, die beim Problem der Dido gefordert ist, lässt sich ebenso ausdrücken als Minimierung von
auf der Restriktionsmenge
.
Gemäß dem Lagrange-Lemma suchen wir ein so, dass ein
Minimallösung von
auf
ist.
minimiert also
auf . Dies ist eine Variationsaufgabe wie Aufgabe (A). Die zugehörige Lagrange-Funktion lautet
und ist für jedes feste und
konvex in
(so wie auch
eine konvexe Menge ist), so dass ein Erfüllen der Euler-Gleichung für
bereits hinreichend für eine Minimallösung ist.
Die Lagrange-Funktion hängt nicht explizit von ab – ein Fall, den wir schon in Beispiel 3.9 hatten und der auf Gleichung (11), nämlich
mit einer Konstanten
, geführt hatte. Diese Gleichung lautet jetzt für unser konkretes
.
Multiplikation mit liefert
,
was wir zu
zusammenfassen und in der Form
schreiben können mit einer neuen Konstanten . Durch Quadrieren kommen wir auf
An dieser Stelle rechnen wir erst einmal “drauf los” und bringen (29) in die Form einer separierbaren DGL, nämlich
,
deren implizite Lösung
lautet mit einer weiteren Konstanten . Dies führt auf
Diese Rechnung war allerdings ziemlich sorglos: Wurzelziehen und Dividieren sollte man mathematisch absichern. Geht man zurück zu (29), dann lässt sich jetzt im Licht von (30) der Ansatz
motivieren, aus dem
folgt: Mit diesem Ansatz erhalten wir als Lösungen Kreisbögen in
mit Mittelpunkt
und Radius
. Damit die Bedingung
erfüllt ist, muss
gelten.
Im Fall könnte der Mittelpunkt
unterhalb oder oberhalb der
-Achse liegen, je nachdem ob
oder
gilt. Im ersten Fall ist
und im zweiten Fall ist
, also kommt für eine Optimallösung nur
in Frage.
Im besagten Fall bekommt man dann gerade wieder (30) zurück – woraus man sieht, dass der Ansatz berechtigt war. Aus der Nebenbedingung
ergibt sich dann
. Schließlich erhält man
aus dem Satz von Pythagoras:
.
Ungemütlicher wird es im Grenzfall , denn dann ist die Lösung (30) ein voller Halbkreis und keine
-Funktion mehr, sondern enthält Singularitäten – wie wir es schon von der Brachistochrone kennen.
Aufgabe (C) lässt sich verallgemeinern: Wir können Extremalkurven statt skalarer Funktionen
suchen und mehrere statt einer Nebenbedingung stellen. Diese Fälle sind im Lagrange-Lemma 6.1 eingeschlossen, wie bereits oben bemerkt. Die allgemeine isoperimetrische Aufgabe lautet
wobei und
Lagrange-Funktionen analog wie in Aufgabe (C) und die
Konstanten sind. Der Lagrange-Ansatz gemäß Lemma 6.1 besteht dann darin, die Funktion
zu minimieren. Ungleichungs-Nebenbedingungen können nach demselben Muster mit Lagrange-Multiplikatoren behandelt werden, siehe das Lagrange-Lemma.
6.2 Nebenbedingungen in Gleichungsform
Jetzt geht es um Nebenbedingungen, die den Verlauf der Lösungskurve in allen Punkten einschränken. Wir betrachten die folgende Variationsaufgabe.
Aufgabe (D): Variationsaufgabe mit Nebenbedingungen in Gleichungsform
Es seien mit
und
stetige Funktionen, in den beiden letzten (vektorwertigen) Komponenten stetig partiell differenzierbar. Dann ist eine
-Kurve
zu finden, die das folgende Problem
unter der Nebenbedingung
löst.
Beispiel 6.3: Algebraische Gleichung als Nebenbedingung
Die Nebenbedingung kann eine algebraische Gleichung für sein, etwa mit
:
.
Das wäre die Forderung, dass zur Konkurrenz nur Kurven auf der Einheitssphäre im zugelassen sind. Mit
bedeutet das: Gesucht sind kürzeste Entfernungen auf der dreidimensionalen Einheitssphäre. Kürzeste Kurven nennt man Geodätische.
Eine andere Form der Nebenbedingung wäre eine Differentialgleichung für . Diese Art der Nebenbedingung ist typisch für die Steuerungstheorie und wir werden sie in Abschnitt 7 aufgreifen.
Auch zur Lösung der Aufgabe (D) wird wieder die Lagrange-Idee herangezogen, wie sie in Lemma 6.1 zum Ausdruck kam. Der wesentliche Punkt dabei war der, das zu minimierende Funktional (das sogenannte Zielfunktional) zu ergänzen um den Ausdruck
,
der auf der durch die Nebenbedingungen definierten Menge konstant gleich null ist. Der Ansatz geht bei Gleichungs-Nebenbedingungen glatt durch, wenn man statt der ersten Summe eine allgemeinere Ergänzung wählt. Hier die offizielle Formulierung.
Lemma 6.4: Allgemeines Lagrange-Lemma
Es sei eine beliebige Menge und
und
. Die Funktion
ist auf der Restriktionsmenge
zu minimieren.
Es sei eine Funktion, die auf der Menge
konstant gleich null ist:
. Außerdem sei
so gewählt, dass eine Lösung
von
in liegt:
. Dann ist
eine Minimallösung von
auf
.
Beweis
Für beliebiges haben wir wegen der Voraussetzungen an
und damit ist schon alles gezeigt.
Die Bemerkungen zu Lemma 6.1 gelten auch hier:
- Die Menge
kann insbesondere eine Teilmenge eines Funktionenraums sein, z.b.
im Fall von Variationsaufgabe (D)
- Das allgemeine Lemma von Lagrange behandelt einen viel allgemeineren Fall als den von Variationsaufgabe (D):
- die Menge
kann Funktionen mit höheren Ableitungen oder mehreren unabhängigen Variablen beinhalten
- es können mehrere Nebenbedingungen vorkommen
- die Menge
- Anwendung auf die Variationsaufgabe (D): Setze
und
als einzige Gleichungsnebenbedingung
Beispiel 6.5: Variable Lagrange-Multiplikatoren
Man kann statt konstanter Faktoren Funktionen
ansetzen, also
und die Funktion von der folgenden Form wählen:
.
Dies ist die naheliegendste Erweiterung der “klassischen” Methode der Lagrange-Multiplikatoren.
Beispiel 6.6: Variable Multiplikatoren für Aufgabe (D)
In diesem Fall ist . Mit einer stetigen Funktion
definieren wir
Der Vorteil hiervon ist, dass die Erweiterungsfunktion nun ebenfalls die Integralform von
besitzt. Die Optimierung der Funktion
führt damit wieder auf die Euler-Gleichung für die erweiterte Lagrange-Funktion
wie wir es schon bei der isoperimetrischen Aufgabe hatten.
Es sind natürlich auch Varianten von (31) möglich. So könnten wir statt mit mit Funktionen
hantieren – dies würde nichts Grundsätzliches ändern. Genauso kann man bei Aufgabe (D) mehrere Nebenbedingungen gleichzeitig behandeln:
. Dann ist auch
als vektorwertige Kurve
zu wählen und aus (31) wird
.
Das allgemeine Lagrange-Lemma 6.4 in Form des Ansatzes aus Beispiel 6.6 wird also nach dem gleichen Rezept angewandt wie das Lemma 6.1:
- Man bildet die erweiterte Lagrange-Funktion (32) und damit das erweiterte Funktional
mit einer noch unbekannten Funktion
.
- Man versucht, das erweiterte Funktional
zu minimieren und gleichzeitig die Funktion
so zu wählen, dass der Minimierer die Nebenbedingung erfüllt.
Analog geht man bei mehreren Nebenbedingungen vor. Gelingt die Ausführung dieser Schritte, hat man nach Lemma 6.4 einen Minimierer von unter der Nebenbedingung
gefunden.
Wiederum sagt Lemma 6.4 nichts darüber aus, ob es die gesuchte Funktion (bzw. bei mehreren Nebenbedingungen die Funktionen
) tatsächlich gibt bzw. ob es immer ein
so gibt, dass sich der Minimierer von
unter der Nebenbedingung
unter den Extremalen von
befindet. Eine entsprechende Existenzaussage gilt jedoch tatsächlich, wenn die Nebenbedingung(en) eine gewisse Regularitätsvoraussetzung erfüllen.
Die bekannteste konkrete Aufgabe vom Typ (D) ist es, geodätische Kurven zu finden, zum Beispiel kürzeste Entfernungen auf Sphären wie in Beispiel 6.3. Wir wollen stattdessen den in Beispiel 6.6 formulierten Ansatz anwenden, um ein Beispiel aus der Signalverarbeitung zu lösen.
Beispiel 6.7: Optimaler Nyquist-Entzerrer
Wir betrachten folgendes Modell einer Übertragungsstrecke für ein Basisband-Signal, bei dem eine gesuchte Funktion ist:
Dazu folgende – sehr knapp gehaltene- Erklärungen (vergleiche “Digital Communication, 3rd Edition” von John R. Barry, Edward A. Lee und David G. Messerschmidt, Springer Verlag, 2003).
Ein zu übertragendes digitales (d.h. diskretes) Signal durchläuft im Transmitter (TX) einen sogenannten pulse shaping filter. Mathematisch bedeutet dies, dass ein analoges Signal der Form
erzeugt wird mit . Das Signal
soll übertragen werden. Bei der Übertragung kommt es zur Mehrwegausbreitung, das heißt das Signal wird mit zeitlich versetzten, gewichteten Kopien seiner selbst überlagert. Dieser Effekt lässt sich als Faltung mit einer Funktion
beschreiben, das heißt der Übertragungskanal verzerrt das Signal
zu
.
Hier ist der delay spread oder die “Länge des Kanals” (maximale Verzögerung) und
ist die Kanalimpulsantwort (channel impulse response – CIR), die man erhält, wenn man einen Diracimpuls sendet.
Eine zusätzliche Störung erfährt das Signal durch sogenanntes additives weißes Rauschen. Hierbei handelt es sich nicht um eine auf Zufallseinflüssen basierende Störung, die man in der Wahrscheinlichkeitstheorie durch stochastische Prozesse beschreibt. Wir können an dieser Stelle keine Erörterung stochastischer Prozesse einflechten, insbesondere keine des mathematisch überhaupt nicht trivialen weißen Rauschens. Man kann sich den Einfluss des Rauschens aber so vorstellen, dass zum Signal additiv ein weiteres Signal
hinzukommt. Im Empfänger kann man niemals
separat beobachten, sondern stets nur
.
Aufgabe des Empfängers ist es, das originale Signal zu rekonstruieren – in der Sprache der Statistik: zu schätzen – wobei nur das Signal
zur Verfügung steht und vorausgesetzt wird,
sowie
seien bekannt. Wir schreiben vor, dass die Schätzung in zwei Stufen ablaufen soll. Erstens soll
einen weiteren Filter durchlaufen (der Schätzer soll linear sein)
,
mit einem zu bestimmenden Filterkern . Zweitens wird
abgetastet, also in eine diskrete (digitale) Zahlenfolge
verwandelt. Es ist
,
wobei wie oben der Abstand zwischen zwei Samples (Abtastwerten)
und
ist.
Wir können formal jeden Abtastwert in der Form
schreiben mit
und
.
Es entspricht also dem deterministischen Wert, der durch den Einfluss der Filter
,
und
zustande kommt und
dem Einfluss, der durch das zufällige Rauschen und anschließende Filterung mit
zustande kommt.
Wir wollen offenbar erreichen, doch genügt diese Forderung alleine noch nicht. Da wir nämlich niemals Zugriff auf das Signal
bekommen, sondern immer nur auf
, bekommen wir auch immer nur “gestörte” Werte
zu Gesicht. Wir müssen uns deswegen darum kümmern, dass die Anteile
“klein werden”.
Es ist günstig, diese Aufgabenstellung “im Frequenzraum” exakt zu formulieren. Dazu einige weitere Erläuterungen: Die Fourier-Transformierte einer Funktion ist definiert durch
,
wobei die imaginäre Einheit ist. An dieser Stelle kümmern wir uns nicht um Voraussetzungen, unter denen die Fourier-Transformierte oder andere der folgenden Rechenoperationen definiert sind. Die Beziehung zwischen einer Funktion und ihrer Transformierten drücken wir wie üblich durch
aus und folgen dabei der Konvention, dass die Zeitfunktion mit einem kleinen und die Fourier-Transformation mit einem großen Buchstaben bezeichnet wird. Wir können annehmen, dass genau dann bekannt ist, wenn
bekannt ist.
Die drei Filter ,
und
hintereinander wirken wir ein einziger Filter mit Kern
, welcher die Fourier-Transformierte
hat. Aus der Nachrichtentechnik ist bekannt, dass , wenn das sogenannte Nyquist-Kriterium erfüllt ist:
Gleichzeitig soll so gewählt sein, dass der störende Einfluss der Samples
so klein wie möglich gemacht wird. Ein dafür oft herangezogenes Kriterium ist das der Minimierung der Rauschenergie. Die Rauschenergie ergibt sich zu
wobei die Energie des additiven weißen Rauschens ist.
Wir können nun weiter voraussetzen, sei ein bandbeschränkter Filter. Das heißt, dass
für
mit einem
. Eine solche Einschränkung besteht in der Praxis immer, weil in jedem Übertragungsstandard vorgeschrieben ist, dass nur ein bestimmtes Frequenzband zur Signalübertragung genutzt werden darf. Dann können wir aber ebenso voraussetzen, dass
bandbeschränkt mit Bandbreite
ist. Man macht sich schnell klar (siehe etwa “Digital Communications”, 4th Edition, John G. Proakis, McGraw-Hill, S. 556 ff.), dass dann das Nyquist-Kriterium nur erfüllbar ist, wenn
und genau dies wollen wir ab jetzt auch voraussetzen.
Durch die Bandbeschränktheit werden der Integrationsbereich in (34) und die Summation in (33) endlich. Wir dürfen zum Beispiel ohne Weiteres
schreiben.
Das beschriebene Problem soll nun in die Fassung der Aufgabe (D) gebracht werden. Wir schreiben dazu im Folgenden für die gesuchte Funktion
. Da wir komplexe Zahlen als Vektoren in
auffassen können, suchen wir eine Kurve
,
wobei für den Realteil und
für den Imaginärteil von
steht. Für die uns bekannte komplexwertige Funktion
haben wir ebenfalls
für
und schreiben für
abkürzend
, fassen diese komplexwertige Funktion also ebenfalls als reellwertige Kurve auf.
Mit der Regel der komplexen Multiplikation wird aus (33) die Nebenbedingung mit
und
und das Zielfunktional hat die Form
Unsere Aufgabe besteht darin, das Funktional unter Beachtung der Nebenbedingung
zu minimieren und das ist gerade eine Aufgabe vom Typ (D). Zur Lösung machen wir einen Ansatz gemäß Beispiel 6.6 mit einer variablen Multiplikatorfunktion
. Wir bekommen dann wie in Beispiel 6.6 die Lagrange-Funktion gemäß (32), wobei wir abkürzend
schreiben:
Diese Lagrange-Funktion ist konvex in und jede Lösung der Euler-Gleichung ist damit ein Minimierer.
Da nicht von
abhängt, lauten die Euler-Gleichungen ganz einfach
oder ausgeschrieben:
Das lässt sich einfacher schreiben, wenn wir auch als komplexe Zahl auffassen mit Realteil
und Imaginärteil
. Dann bekommen wir nämlich
,
wobei wir mit die zu
konjugiert komplexe Zahl bezeichnen. Dies lässt sich erfüllen durch die Wahl
.
Setzen wir diese Gleichung in die Nebenbedingung ein, dann erhalten wir
.
Daraus bekommen wir schließlich die gesuchte Lösung
oder ausgeschrieben
.
Im Sonderfall, dass “kein Kanal” vorhanden ist, also , ergibt sich wegen des Nyquist-Kriteriums
dass
.
Der optimale ist in diesem Sonderfall der matched filter.