Extremwertaufgaben

Stellen Sie sich irgendeine Funktion f vor, die gewissen Objekten x eine Zahl zuordnet (man schreibt f(x) für die Zahl, die x zugeordnet wird; z. B.

x ist eine Zahl zwischen 0 und 1 und f(x) = x²

x ist ein Weg von Berlin nach München, f(x) ist die Länge von x

x ein Zahlentripel (a,b,c), und f(x) ist die Temperatur an dem Raumpunkt mit den Koordinaten a,b,c

Abstrakt also im Sinne:

f : M --> R,

wobei R das Symbol für die reellen Zahlen und M eine beliebige Menge ist. Das typische Problem bei vielen Extremwertaufgaben ist: Finde ein x mit größtmöglichem f(x). also ein x, so dass f(x) größer oder gleich f(y) für alle y aus M ist.

Bild

(Manchmal sucht man auch ein x, so dass f(x) kleinstmöglich ist; vgl. das zweite der obigen Beispiele.)

Viele Probleme dieser Welt lassen sich als Extremwertaufgaben formulieren: schnellste Verbindungen, kostengünstigste Herstellung, schonendste Zubereitung, geringste Nebenwirkungen. Klar, dass sich Mathematiker dazu viele Gedanken gemacht haben. Hier einige Infos dazu.

1. Existenz:

Es ist von vorneherein nicht klar, dass es ein x mit größtmöglichem f(x) gibt. Es exisiert z. B. mit Sicherheit kein längster Weg von Berlin nach München, durch eine Umweg ("Extraschlaufe") kann man jeden noch so langen Weg verlängern.

Man muss sich dazu extra Gedanken machen meist kann man schon bekannte Ergebnisse einfach anwenden.

[Ein Beispiel: Ist [a,b] ein abgeschlossenes Intervall und f : [a,b] --> R eine stetige Funktion, so gibt es ein x mit größtmöglichen f(x) garantiert.
Etwas Fortgeschrittenere wissen, dass der Kompaktheitsbegriff dahinter steht, aber das ist für mathematik.de etwas zu schwierig.]

2. Eindeutigkeit:

Fast nie gibt es nur einen einzigen Kandidaten für ein x mit größtmöglichem f(x). (Das ist z. B. in der obigen Skizze der Fall.) Im Extremfall, wenn f konstant ist, kann man sogar alle x einsetzen.

Wie findet man so ein x?

Fall 1: M ist endlich und "nicht zu groß", höchsten vielleicht einige Millionen bis Milliarden Elemente. Dann kann man einen Computer alle f(x) ausrechnen lassen und so ein x mit größtem f(x) ausrechnen lassen. (Leider kommt es auch bei endlichen Mengen oft vor, dass es so nicht geht, sie sind einfach viel zu groß.)

Fall 2: M ist ein Intervall [a,b] und f ist differenzierbar.

Bild

Das hat besonders viele Anwendungen, es wird in der Schule behandelt. Hier ist es so, dass man ein x mit größtmöglichem f(x) so findet:

Bestimme alle x mit f'(x) = 0, also alle x mit waagerechter Tangente. Die sollen x₁, x₂, ..., x_n heißen. Berechne f(a), f(b), f(x₁), ..., f(x_n) und stelle fest, welche dieser Zahlen die größte ist.

Auf diese Weise ist das Extremwertproblem für eine unendliche Menge M (nämlich [a,b]) darauf zurückgeführt, die Gleichung f'(x) = 0 vollständig zu lösen und anschließend noch endlich viele, in der Regel wenige, Kontrollrechnungen durchzuführen.

Fall 3: M ist ein Teilmenge des n-dimensionalen euklidischen Raumes und f ist wieder differenzierbar. Das geht ganz ähnlich wie im vorstehenden Fall, nur muss jetzt die Vektorgleichung (grad f)(x) = 0 gelöst werden (Einzelheiten würden hier nun zu weit gehen).

Fall 4: Wenn man keinerlei Differenzierbarkeit voraussetzen darf und man nur so etwas wie einen "schwarzen Kasten" zur Verfügung hat, der aus der Eingabe x die Ausgabe f(x) macht, kann man es immer noch mit Zufallsmethoden versuchen.

Denken Sie zum Vergleich an einen Wanderer, der im dichten Nebel in hügeligem Gelände unterwegs ist und den höchsten Punkt erreichen möchte. Er könnte doch so vorgehen:

Er macht versuchsweise einen Schritt in eine zufällig gewählte Richtung. Geht es da bergauf, so macht er den Schritt wirklich, anderenfalls bleibt er ersteinmal, wo er ist. Und dann das ganze nocheinmal,...

Klar ist, dass er so immer nur aufwärts gehen wird und dass er, sollte der Gipfel (=Extremwert) erreicht sein, sich nicht mehr von der Stelle rühren wird. Allerdings ist auch sofort zu sehen, dass man in relativen Extremwerten hängen bleiben kann: Wenn der Hauptgipfel 200m hoch ist und man zufällig auf einen Hügel von 100m Höhe spaziert ist, kommt man da nicht mehr weg.

Deswegen ist das Verfahren verfeinert worden, die Anweisung an den Wanderer wird modifiziert:

Wenn es bei dem Testschritt bergab gehen sollte, entscheide durch einen Zufallsmechanismus -- etwa das Werfen einer Münze -- ob der Schritt trotzdem ausgeführt wird.

Durch Einstellen der Parameter (Schrittgröße, Wahrscheinlichkeit für das Ausführen eines bergab führenden Schgrtittes) kann die Wanderung unseres Spaziergängers stark beeinflusst werden, in vielen Fällen so, dass er mit hoher Wahrscheinlichkeit wirklich zum Gipfel kommt. Das Verfahren ist erst einige Jahrzehnte alt. Es heißt simulated annealing und erfreut sich bei vielen Anwendern von Mathematik großer Beliebtheit. (Es handelt sich übrigens um ein interessantes Beispiel dafür, dass man den Zufall zum Lösen konkreter Probleme einsetzt. Man spricht dann auch von Monte-Carlo-Verfahren.)