Lokale Extrema dieser Funktion bestimmen

Aufrufe: 1467     Aktiv: 27.05.2021 um 16:13

0
Hallo,
ich habe folgende Aufgabe:

Normalerweise berechnet man die Extremstellen ja, indem man den Gradienten berechnet und dann = 0 setzt und die Gleichungen löst. Mein Problem ist, dass ich nicht wirklich weiß, wie ich die Funktion f ableiten soll. Das Skalarprodukt kann ich ja nicht bestimmen, da ich nicht weiß, wie A aussieht. Die Info, dass A positiv definit ist, sagt doch, dass alle Eigenwerte von A positiv sind (?).
Kann ich dadurch A bestimmen? Oder muss ich A gar nicht bestimmen?
 Außerdem sagt es aus, dass es ein lokales Minimum gibt. Aber ich muss ja auch den Punkt angeben, an dem dieses lokale Minimum angenommen wird.
Ich wäre dankbar für einen kleinen Denkanstoß. LG
Diese Frage melden
gefragt

Student, Punkte: 119

christian_strack hat 27.05.2021 um 16:13 bearbeitet

 
Kommentar schreiben
1 Antwort
1
Hallo,

du hast hier 2 Möglichkeiten. Entweder du schreibst alles ganz allgemein auf rechnest das Skalarprodukt aus und leitest es dann nach jeder Unbekannten ab. Das ist sehr aufwendig und wird schnell unübersichtlich. 

Andere Möglichkeit ist, wir fassen die Funktion \( f \) als Funktion in Abhängigkeit der einzigen Variablen \( \vec x \) auf. Das wird wesentlich übersichtlicher und vor allem weniger Arbeit sowohl für die a) als auch für die b). 

Den Gradienten kann man auffassen als

$$ \mathrm{grad}(f(x_1,x_2)) = (f'(\vec x))^T $$

mit \( \vec x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \). Betrachten wir also erstmal deine Funktion. Ich setze im folgenden \( \vec x = x \), um mir etwas Schreibarbeit zu sparen.

$$ f(x) = \left< x , \frac 1 2 Ax + b \right> $$

Diese Gleichung können wir erstmal etwas schöner aufschreiben. Nutze die Linearität, um die Gleichung in eine Summe von 2 Skalarprodukten zu schreiben. 

Nun gehe ich davon aus, dass hier das Standardskalarprodukt gemeint ist. Es gilt

$$ \left< x,y \right> = x^T \cdot I \cdot y = x^T \cdot y $$

Mit \(I \) der Einheitsmatrix. So wirst du die Skalarprodukte los. 

Wir haben nun eine Gleichung die von \( x \) abhängt. Diese können wir "einfach" ableiten. Wir müssen aber aufpassen, denn es kommt auch \( x^T \) in der Gleichung vor. Wie gehen wir damit um?

Betrachten wir mal folgende Funktion

$$ g(u,v) = u^T \cdot A \cdot v $$

Nach \(v \) können wir simpel ableiten. 

$$ g_v(u,v) = u^T \cdot A $$

Wie sieht es nun mit der Ableitung nach \( u \) aus? Die Funktion \( g\) bildet einen Vektor auf ein Skalar ab (genau wie unser \(f\)). Es gilt somit \( g^T = g \). Dies nutzen wir aus

$$ g(u,v) = (A \cdot v)^T \cdot u $$

Das können wir nun nach \(u \) ableiten

$$ g_u (u,v) = ( A \cdot v)^T $$

Wenn wir nun \( u = v = x \) setzen, kannst du die Ableitung bestimmen.

Wenn wir nun diese Ableitung transponieren, erhalten wir den Gradienten. Diesen kannst du nun ganz allgemein nach Null umstellen. Hier kommt uns schon zu gute, dass die Matrix \( A \) positiv definit ist. Was sagt uns das nämlich über die Determinante? Was folgt daraus für \(A \)?

Nun bestimmen wir noch die Hesse Matrix. Es gilt

$$ H_f(x) = ((f'(x))^T)' $$

Wir leiten also den Gradienten nochmal nach \( x \) ab. Wieder können wir die positive Definitheit nutzen, um unseren kritischen Punkt als Extremum zu identifizieren. Was liegt vor?

Für das Taylorpolynom musst du nun nur noch einsetzen.

Versuch dich mal. Falls Fragen aufkommen, melde dich nochmal. Ich gucke auch am Ende gerne nochmal drüber.

Grüße Christian
Diese Antwort melden
geantwortet

Sonstiger Berufsstatus, Punkte: 29.81K

 

Schonmal vielen Dank für die ausführliche Antwort!! Ich setze mich später dran!   ─   felix1220 24.05.2021 um 13:44

Sehr gerne ;)
Alles klar. Wenn du nicht weiter kommst, melde dich gerne jederzeit
  ─   christian_strack 24.05.2021 um 13:45

Sooo ich bin jetzt hier: https://imgur.com/a/1C2CM8B
Habe ich die Linearität korrekt verwendet? Und ich bin mir nicht sicher, ob ich das Skalarprodukt nach dem 1/2 korrekt aufgelöst habe. Vielleicht komme ich deshalb nicht weiter bei der Auflösung der ^T
  ─   felix1220 24.05.2021 um 15:08

Die Funktion ist schon mal richtig, aber du hast die Funktion dann nach \( \vec b \) abgeleitet. Du musst aber nach \( \vec x \) ableiten. \( \vec b \) kannst du wie eine Konstante behandeln.
Man sieht auch leider nicht ganz, wie deine Transposition der Funktion aussieht.
Hier zum Vergleich:
$$ x^T \cdot b + \frac 1 2 (Ax)^T x = b^T \cdot x + \frac 1 2 x^T Ax $$
  ─   christian_strack 24.05.2021 um 15:25

Okay, das habe ich auch. Aber auf der rechten Seite ist ja immer noch ein x^T. Muss ich das nicht auch noch irgendwie wegbekommen?   ─   felix1220 24.05.2021 um 16:04

Ich habe nach b abgeleitet, da wir für den Gradienten doch 2 partielle Ableitungen benötigen oder nicht?   ─   felix1220 24.05.2021 um 16:05

So sähe meine Ableitung nach x aus https://imgur.com/a/Hmrn11O   ─   felix1220 24.05.2021 um 16:29

Der Gradient ist ja der Vektor, wenn wir nach jeder Variable (\(x_1, \ldots , x_n\)) einzeln ableiten. Wir fassen hier aber den Vektor \( \vec x = \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} \) als einzige Variable auf. Deshalb können wir hier (fast) wie in 1D ableiten. Wir müssen uns nur darüber im klaren sein, wie man einen transponierten Vektor ableitet.

Der Summand \( b^T \cdot x \) nach \( x \) abgeleitet ist? (hier können wir wirklich wie in 1D vorgehen.

Wie der Summand mit dem transponierten \(x\) abgeleitet wird, hatte ich oben angedeutet, aber vielleicht ist das etwas zu abstrakt. Machen wir das Schritt für Schritt.

$$ x^T A x = \begin{pmatrix} x_1 & x_2 \end{pmatrix} \cdot \begin{pmatrix} a_{11} & a_{12} \\ a_{12} & a_{22} \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = a_{11} x_1^2 + 2a_{12} x_1 x_2 + a_{22}x_2^2 $$
Das können wir nun einmal nach \( x_1 \) und einmal nach \( x_2 \) ableiten und erhalten
$$ \mathrm{grad}(x^T A x) = \begin{pmatrix} 2a_{11}x_1 + 2a_{12} x_2 \\ 2a_{22} x_2 + 2a_{12} x_1 \end{pmatrix} = 2 A \cdot x $$
Also haben wir insgesamt
$$ \mathrm{grad}(f) = \frac 1 2 \mathrm{grad}(x^T Ax) + b = A \cdot x + b $$
Ist das nachvollziehbar?

Allgemein gilt
$$ \left( x^T \cdot A \cdot x\right)^\prime = (Ax)^T + x^T A = x^T A^T + x^T A = x^T (A + A^T)$$
Da unsere Matrix symmetrisch ist, gilt \( A = A^T\) und wir erhalten
$$ f'(x) = \frac 1 2 \cdot x^T (A+ A^T) + b^T = \frac 1 2 \cdot 2 x^T A + b^T = x^T A + b^T $$
Nun gilt für den Gradienten
$$ \mathrm{grad}(f) = (f'(x))^T = Ax + b $$

Ist das alles nachvollziehbar?
  ─   christian_strack 24.05.2021 um 16:40

Hat etwas gedauert, aber jetzt hab ichs. Ich habe beim Transponieren der Ableitung immer ans Transponieren eines konkreten Vektors gedacht. Die Eigenschaft (x^T)^T = x habe ich nicht bedacht. Vielen Dank! Ich versuche mal weiterzumachen   ─   felix1220 25.05.2021 um 11:02

Ja das geht auch Hand in Hand.
Die Ableitung ist ein Zeilenvektor, der Gradient liefert uns einen Spaltenvektor. Sie führen aber beide die selbe Art der Operation durch. Deshalb können wir mit Hilfe der Transposition eine Zusammenhang herstellen. Warum bei der Ableitung ein Zeilenvektor herauskommt müsste ich mir mal genau überlegen. Das der Gradient einen Spaltenvektor liefert ist ja gerade so definiert.

Wichtig ist, diese Eigenschaft gilt natürlich nur bei Skalaren oder symmetrischen Matrizen. Du hast jetzt hier \( (x^T)^T = x \) geschrieben. Wenn du das auf den Vektor \(x \) aus den obigen Rechnungen meinst, stimmt das nicht.

Alles klar :) noch als Tipp: bedenke, dass \(A \) positiv definit ist. Was sagt uns das über die Determinante von \( A \)? Damit kannst du sehr einfach die kritischen Punkte berechnen. Die zweite Ableitung (die Hesse Matrix) sollte nun nicht mehr so schwer sein, da kein transponiertes \(x \) mehr vorkommt. Um die Art der kritischen Punkte zu bestimmen, muss die Definitheit der Hesse Matrix bestimmt werden. Diese lässt sich wieder aus der Definitheit von \( A \) ableiten.
  ─   christian_strack 25.05.2021 um 11:27

Die Determinante muss nach der Definitheit positiv sein. Ich habe das hier mal soweit aufgeschrieben https://imgur.com/a/BrRsYgm (das b1 muss negativ sein bei der umgestellten Gleichung)
Ich habe nun 2 Gleichungen, von denen ich ja die Extremstelle/n herausfinden kann. Ich habe die erste Gleichung mal nach X1 umgestellt und wollte das jetzt in die 2. Gleichung einsetzen. (das "einsetzen" in der Aufzeichnung ignorieren) Ist das zu kompliziert? Und ich bin mir leider noch nicht sicher wie ich die Erkenntnis der positiven Determinante hier verwenden kann.
  ─   felix1220 25.05.2021 um 12:28

Genau sie muss positiv sein, also ist sie insbesondere nicht Null!! Das bedeutet, dass die Matrix \( A \) invertierbar ist. Somit folgt für den Gradienten
$$ A x + b = 0 \Rightarrow x = -A^{-1}b $$
Vielleicht siehst du jetzt schon eine Parallele zur b) ;)
Diese Lösung ist tatsächlich sogar eindeutig, denn wir haben hier ein LGS, dass prinzipiell sowieso nur 1, keine oder unendlich viele Lösungen hat. In unserem Fall hat es aber nur eine Lösung und diese können wir wie oben geschrieben sogar angeben.
  ─   christian_strack 25.05.2021 um 12:47

Okay, hab ich soweit verstanden. Noch eine kurze Frage. Das x ist ja immer noch ein Vektor. Heißt dass, dass unsere Extremstelle (x1,x2) heißt? (bzw. x1 ist dann die obere Zeile des Produktes von -A^-1*b) Oder ist einfach x die Extremstelle. Ich weiß noch nicht so richtig, in welchem Format wir uns hier bewegen.
Und der nächste Schritt wäre dann Hesse-Matrix bilden und den Punkt einsetzen?
  ─   felix1220 25.05.2021 um 17:22

Genau \( x \) ist immer noch ein Vektor. Unser kritischer Punkt (wir müssen ja noch herausfinden ob wirklich ein Extremum vorliegt) ist ein Punkt aus \( x_1 \) und \( x_2 \) Koordinate. Wir könnten unsere Lösung oben auch exakter hinschreiben, aber so ist es am saubersten. Aber da wir eine 2x2 Matrix haben, gilt
$$ A^{-1} = \frac 1 {a_{11}a_{22} - a_{12}^2} \begin{pmatrix} a_{22} & - a_{12} \\ -a_{12} & a_{11} \end{pmatrix} $$
und somit ist
$$ x_1 = -\frac {a_{22}b_1 - a_{12}b_2} { a_{11}a_{22} - a_{12}^2} $$
und
$$ x_2 = -\frac {a_{11}b_2 - a_{12}b_1} { a_{11}a_{22} - a_{12}^2} $$

Wie gesagt, du könntest hier jedes mal alles genau aufschreiben. Habe ja oben den Gradienten auch einmal durch aufschreiben der Koeffizienten bestimmt und einmal indem ich die Funktion sofort nach \( \vec{x} \) abgeleitet habe. Es geht beides. Wenn du dich sicherer mit den Koeffizienten fühlst, dann nutze auf jeden Fall den Weg. Es ist etwas mehr Schreibarbeit, aber dann der sicherere Weg für dich. Das mit dem transponierten Vektor ableiten und so bedarf Übung, weil es ein neues Konzept ist. Geht aber, wenn man den Dreh einmal raus hat, schneller.

Genau für die Hesse Matrix gilt
$$ H_f(x) = (\mathrm{grad}(f(x)))' = (Ax+b)' $$
wir müssen also diese Gleichung noch einmal nach \(x\) ableiten. Hier liegt jetzt aber kein transponierter Vektor mehr vor. Deshalb kannst du hier "einfach" nach \(x \) ableiten. Du kannst aber auch die Definition der Hesse Matrix nutzen
$$ H_f(x) = \begin{pmatrix} \frac {\partial f } {\partial x_1 \partial x_1} & \frac {\partial f } {\partial x_1 \partial x_2} \\ \frac {\partial f } {\partial x_2 \partial x_1} & \frac {\partial f } {\partial x_2 \partial x_2} \end{pmatrix} $$
Da wir aber den Gradienten schon haben, können wir auch die Hesse Matrix über den Gradienten definieren
$$ H_f(x) = \begin{pmatrix} \frac{ \partial \mathrm{grad}(f(x))_1} {\partial x_1} & \frac{ \partial \mathrm{grad}(f(x))_1} {\partial x_2} \\ \frac{ \partial \mathrm{grad}(f(x))_2} {\partial x_1} & \frac{ \partial \mathrm{grad}(f(x))_2} {\partial x_2} \end{pmatrix} $$
Denn der Gradient hat ja eben in der ersten Komponente die Ableitung nach \( x_1 \) und in der zweiten Komponente die Ableitung nach \( x_2 \).
Welchen Weg du hier nimmst ist egal. Überall kommt das selbe heraus.
  ─   christian_strack 25.05.2021 um 18:19

Danke für den Tipp mit der Schreibweise der Inverse als 1/determinante... darüber hatte ich auch schon nachgedacht, war mir aber nicht sicher.

Ich habe nun als Hessematrix genau wieder A raus. Die erste Komponente des Gradienten (a11x1+a12x2+b1) abgeleitet nach x1 und x2 ergeben ja für die erste Zeile der Hesse-Matrix a11 und a12. Analog wäre das ja für die 2. Komponente des Gradienten. Und über A haben wir ja schon die Information, dass sie positiv definit ist, woraus wir schließen können, dass am Punkt (x1,x2) ein lokales Minimum vorliegt. Also A = Hess(A) (?)
  ─   felix1220 25.05.2021 um 19:06

Genau so ist es :)

Noch einmal falls es dich interessiert, der Weg in Vektorschreibweise (ansonsten ignoriere es einfach):
Wir leiten die Funktion
$$ f(x) = Ax + b $$
ab. \(b \) ist ein konstanter Vektor und \( A \) kann man sich wie eine Sammlung von Vorfaktoren vorstellen. Also kann man hier sowas wie die Faktorregel der Ableitung anwenden (alles etwas salopp gesprochen). Daraus folgt
$$ f'(x) = (Ax+b)' = (Ax)' + (b)' = A(x)' + 0 = A $$

Wie sieht nun die Taylorentwicklung aus? Du hast jetzt eigentlich alles berechnet und musst nur noch einsetzen.
  ─   christian_strack 25.05.2021 um 19:47

Und gerne für den Tipp. Es gilt allgemein, dass das Inverse einer Matrix gleich der Adjunkten der Matrix geteilt durch die Determinante ist. Für eine 2x2 Matrix heißt das
$$ M^{1} = \begin{pmatrix} a & b \\ c & d \end{pmatrix}^{-1} = \frac 1 {\mathrm{det}(M)} \mathrm{adj}(M)= \frac 1 {ad-bc} \begin{pmatrix} d & -b\\ -c & a \end{pmatrix} $$
  ─   christian_strack 25.05.2021 um 19:51

Und hier wäre auch schon mein nächstes Problem. Ich habe folgende allgemeine Formel aufgestellt: https://imgur.com/a/Nu0mY4O

Dort habe ich schonmal die ersten Werte eingesetzt. Ist das richtig? Weil der Term wirkt auf mich viel zu lang und kompliziert.

Der Entwicklungspunkt x0 ist ja gleich x1 und x2, das habe ich in f eingesetzt...
  ─   felix1220 25.05.2021 um 21:33

Ja hier würde es wirklich helfen, die Vektordarstellung zu nehmen, anstatt die Komponentendarstellung.
1) du brauchst das Taylorpolynom 2ter Ordnung, also:
$$ T_{2}f(x;x_0)=f(x_0)+\nabla f(x_0)^{\mathrm {T} }(x-x_0)+{\frac {1}{2}}(x-x_0)^{\mathrm {T} }\operatorname {H} _{f}(x_0)(x-x_0) $$
Setze also einmal \( x_0 = -A^{-1} b \) in
$$ b^T \cdot x + \frac 1 2 x^T Ax $$
ein (\( x_0 \) für \(x\)). Wenn du dann \( x_0 \) in den Gradienten einsetzt, guck dir mal an, was wir als kritischen Punkt erhalten haben. Was kommt also raus wenn wir diesen Entwicklungspunkt in den Gradienten einsetzen?
Wie sieht unsere Hesse Matrix aus? Egal für welchen Punkt?
Das Taylorpolynom wird wesentlich schöner aussehen.
  ─   christian_strack 25.05.2021 um 23:41

So bin grad dabei. Kurze Frage: Eingesetzt beim Gradienten kriege ich A(-A^(-1)*b)+b. A*-A^(-1) ergibt ja die negative Einheitsmatrix. Dann -E * b = -b. Dann bleibt noch -b+b über, was sich auflöst. Wäre das korrekt für den Gradienten? Die Hesse-Matrix bleibt = A, egal für welchen Punkt.   ─   felix1220 26.05.2021 um 20:26

Ja genau, denn unser Entwicklungspunkt ist ja unser Minimum :p und genau die Hesse Matrix bleibt \(A\).
Jetzt brauchst du nur noch \( f(x_0)\). Was kommt heraus?
  ─   christian_strack 26.05.2021 um 20:50

Ahh und unser x ist ja genau -A^(-1)*b. Also ist X-X0 = 0   ─   felix1220 26.05.2021 um 20:51

Ich habe jetzt das: https://imgur.com/a/9gALiCD
Hab aber das Gefühl, dass ich mich noch irgendwo verrechnet habe...
  ─   felix1220 26.05.2021 um 21:06

Nicht ganz.
Matrizen sind nicht kommutativ (also auch nicht Vektoren). Und im allgemeinen ist auch \( b^T \cdot b \neq 1\).
Es ist
$$ b^T (-A^{-1} b) + \frac 1 2 b^T (-A^{-1})^T A (-A^{-1}) b = b^T (-A^{-1} b) + \frac 1 2 b^T (-A^{-1})^T b = -b^T A^{-1} b - \frac 1 2 b^T A^{-1} b = -\frac 3 2 b^T A^{-1} b$$
Ich habe zwischendurch ausgenutzt, dass unsere Inverse auch symmetrisch ist.

Jetzt ist aber \( x-x_0 \) nicht Null, denn \( x \) ist eine Variable.

Das Taylorpolynom lautet

$$ T_2f(x;-A^{-1}b) = -\frac 3 2 b^T A^{-1} b + A (x+ A^{-1}b) $$
  ─   christian_strack 26.05.2021 um 21:25

Okay, ich komme jetzt endlich auch auf das Ergebnis.

Puh, das war eine schwere Geburt. Vielen vielen Dank, dass du dir die Zeit genommen hast, mir zu helfen!!

Ps: Ich hatte gedacht, dass das x in x-x0 ein Vektor ist. In anderen Aufgaben, wo Funktionen gegeben waren, konnte man einfach x als (x,y) betrachten und dann eben kompontenweise den Entwicklungspunkt subtrahieren
  ─   felix1220 27.05.2021 um 14:38

Sehr schön. :)
Ach sehr gerne. Schön das wir den Knoten lösen konnten :p
  ─   christian_strack 27.05.2021 um 14:43

Kommentar schreiben