Extrema quadratischer Formen < mehrere Veränderl. < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
Sehr geehrte Community,
ich hätte folgende ganz allgemeine Fragen(n) zur Bestimmung von Extremstellen einer quadratischen Form.
Nehmen wir an, [mm] f:x-->x^{T}Ax \ge0 [/mm] (nichtnegativ) und wir wissen, dass es nur einen Kandidaten auf eine Extremstelle gibt (f abgeleitet und gleich 0 gesetzt liefert nur eine Stelle). Können wir daraus automatisch folgern, dass es sich um ein Minimum handelt?
Wenn wir nun die Definitionsmenge [mm] \IR^n [/mm] auf die Menge {x [mm] \in \IR [/mm] | x1 = 1} einschränken (dh die erste Komponente soll gleich 1 sein), können wir auch hier schlussfolgern, dass ein Minimum vorliegt, wenn wir wieder voraussetzen, dass [mm] x^{T}Ax\ge0 [/mm] und es nur einen einzigen Kandidaten auf eine Extremstelle gibt.
Meine Vermutung besagt mir, dass dies gelten sollte, ich bin mir allerdings etwas unsicher, weil es in mehreren Dimensionen auch Ausnahmen geben kann, die im 2(3)-dimensionalen Fall nicht auftreten würden.
Ich würde mich über eure Tipps sehr freuen.
LG, Cauchy
PS: Es handelt sich bei A um eine symmetrische Matrix, die nicht nur den gleichen Wert in jedem Koeffizienten annimmt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:57 Do 15.08.2013 | | Autor: | Marcel |
Hallo Cauchy,
> Sehr geehrte Community,
so förmlich müssen wir aber nicht bleiben. 
> ich hätte folgende ganz allgemeine Fragen(n) zur
> Bestimmung von Extremstellen einer quadratischen Form.
>
> Nehmen wir an, [mm]f:x-->x^{T}Ax \ge0[/mm] (nichtnegativ) und wir
> wissen, dass es nur einen Kandidaten auf eine Extremstelle
> gibt (f abgeleitet und gleich 0 gesetzt liefert nur eine
> Stelle). Können wir daraus automatisch folgern, dass es
> sich um ein Minimum handelt?
>
> Wenn wir nun die Definitionsmenge [mm]\IR^n[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
auf die Menge {x
> [mm]\in \IR[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| x1 = 1} einschränken (dh die erste Komponente
> soll gleich 1 sein), können wir auch hier schlussfolgern,
> dass ein Minimum vorliegt, wenn wir wieder voraussetzen,
> dass [mm]x^{T}Ax\ge0[/mm] und es nur einen einzigen Kandidaten auf
> eine Extremstelle gibt.
>
> Meine Vermutung besagt mir, dass dies gelten sollte, ich
> bin mir allerdings etwas unsicher, weil es in mehreren
> Dimensionen auch Ausnahmen geben kann, die im
> 2(3)-dimensionalen Fall nicht auftreten würden.
>
> Ich würde mich über eure Tipps sehr freuen.
Na, jedenfalls, wenn Du $f(x)=x^TAx$ mit [mm] $A\,$ [/mm] symmetrisch hast, so ist doch die
Jakobi-Matrix einfach [mm] $(2Ax)^T\,.$ [/mm]
(Für nichtsymmetrisches [mm] $A\,$ [/mm] wäre das falsch - rechne das einfach mal für $A [mm] \in \IR^{2 \times 2}$ [/mm]
nach!)
(Je nach Definition der Jacobi-Matrix auch ohne das "transponiert" - dann
wäre das der Gradient.)
Die Hesse-Matrix wäre dann (nach der mir bekannten Definition) einfach
nichts anderes als [mm] $2A\,.$
[/mm]
Nach Voraussetzung ist [mm] $A\,$ [/mm] positiv semidefinit, so dass wegen ![[]](/images/popup.gif) Satz 20.21
(klick!) folgt:
Die Stelle [mm] $x_0$ [/mm] mit [mm] $2{x_0}^T*A^T=0$ [/mm] kann, wenn sie eine Extremstelle ist, dann
nur eine (lokale) Minimalstelle sein. (Es kann halt auch einfach sein, dass
sie gar keine Extremstelle ist ! Du brauchst aber jedenfalls nicht mehr zu
prüfen, ob sie eine Maximalstelle ist: Wäre sie eine Maximalstelle, so folgte
aus Satz 20.21 in notwendiger Weise, dass dann [mm] $2A\,$ [/mm] und damit auch [mm] $A\,$ [/mm] negativ
semidefinit sein müsste...).
Wenn es sich nun um eine konkret gegebene Funktion handelt, deren Matrix
[mm] $A\,$ [/mm] dann hoffentlich auch symmetrisch ist, so würde ich mir dann tatsächlich
mal Gedanken machen, ob man [mm] $f\,$ [/mm] auf einer (genügend) kleinen Umgebung
von [mm] $x_0$ [/mm] mit [mm] $f(x_0)$ [/mm] vergleichen kann...
Wenn es eine (genügend kleine) Umgebung von [mm] $x_0$ [/mm] gibt, auf der $f$ stets
[mm] $\ge f(x_0)$ [/mm] ist, dann ist [mm] $x_0$ [/mm] halt eine (lokale) Minimalstelle.
Nimmt [mm] $f\,$ [/mm] auf jeder Umgebung von [mm] $x_0$ [/mm] auch Werte $< [mm] f(x_0)$ [/mm] an, so kann
[mm] $x_0$ [/mm] nicht lokale Minimalstelle sein!
Gruß,
Marcel
|
|
|
| |
|
Hallo Marcel,
vielen Dank für deine Antwort.
"Wenn es sich nun um eine konkret gegebene Funktion handelt, deren Matrix
$ [mm] A\, [/mm] $ dann hoffentlich auch symmetrisch ist"
das habe ich auch vorausgesetzt. Die Voraussetzung habe ich in meiner Frage etwas unglücklich - ganz unten angegeben.
"Wenn es eine (genügend kleine) Umgebung von $ [mm] x_0 [/mm] $ gibt, auf der $ f $ stets
$ [mm] \ge f(x_0) [/mm] $ ist, dann ist $ [mm] x_0 [/mm] $ halt eine (lokale) Minimalstelle.
Nimmt $ [mm] f\, [/mm] $ auf jeder Umgebung von $ [mm] x_0 [/mm] $ auch Werte $ < [mm] f(x_0) [/mm] $ an, so kann
$ [mm] x_0 [/mm] $ nicht lokale Minimalstelle sein! "
ich nehme an, dass du hier zum Fall übergegangen bist, wo ich x1=1 vorausgesetzt habe. Denn sonst liegt wie schon erwähnt ein eindeutiger globaler Kandidat vor. Ich habe mir überlegt, wenn wir den eingeschränkten Fall mit x=1 betrachten und unter dieser Bedingung die Existenz eines einzigen Kandidaten für die Extremstelle voraussetzen (das ist nicht derselbe Kandidat, den man erhält, wenn man die Funktion ohne Einschränkung betrachtet, sondern der Kandidat unter der gegebenen Einschränkung), dann können uns nur drei Fälle vorliegen: Ein Maximum, ein Minimum, die Indefinitheit. Es ist nun die Frage, ob die Indefinitheit und ein Maximum überhaupt vorliegen können, wenn doch gilt: xtAx>=0. Denn man muss ja bedenken, dass die Funktion f stetig ist, und sich wie eine quadratische Form verhält.
Ich glaube mit dem Satz, auf den du verlinkt hast, auch das zweite Problem identisch gelöst wird: wegen xTAx>=0 (positiv semidefinit) (ohne Einschränkung) folgt nach Satz, dass es sich um ein Minimum handelt. Die Indefinitheit wird ausgeschlossen, weil xTAx keine negative Werte einnimmt. Daraus folgern wir die Positive Definitheit der Matrix A. Für das Unterproblem (mit x1=1) muss damit auch gelten: xTAx>0, und damit sollte im Fall eines eindeutigen Kandidaten (im eingeschränkten Fall) ein Minimum liegen, oder stimmt die letzte Folgerung nicht mehr?
Grüße, Cauchy.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:29 Fr 16.08.2013 | | Autor: | Marcel |
Hi Cauchy,
warum willst Du Dich denn auf den Fall beschränken, dass [mm] $x_1=1$?
[/mm]
(Für $f [mm] \colon \IR^n \to \IR$ [/mm] müßtest Du diese Menge übrigens so schreiben:
[mm] $\{x=(x_1,...,x_n)^T \in \IR^\red{n}:\;\;x_1=1\}$.)
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:24 Fr 16.08.2013 | | Autor: | Cauchy123 |
Hallo Marcel,
ich beschränke mich auf diesen Fall, weil in meinem Fall dieser Fall vorliegt 
Mich interessiert also nur dieser Fall!
Grüße.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Sa 17.08.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:30 Fr 16.08.2013 | | Autor: | felixf |
Moin zusammen,
> Na, jedenfalls, wenn Du [mm]f(x)=x^TAx[/mm] mit [mm]A\,[/mm] symmetrisch
Dass man $A$ immer als symmetrisch annehmen kann hatten wir schon hier. :)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:08 Fr 16.08.2013 | | Autor: | Marcel |
Moin Felix,
> Moin zusammen,
>
> > Na, jedenfalls, wenn Du [mm]f(x)=x^TAx[/mm] mit [mm]A\,[/mm] symmetrisch
>
> Dass man [mm]A[/mm] immer als symmetrisch annehmen kann hatten wir
> schon hier. :)
Danke - ich hatte das gestern schon vermutet, war mir aber nicht sicher.
(Irgendwie habe ich das aber schonmal gesehen.)
Sehe ich das richtig, dass Du folgendes meinst:
Wenn [mm] $A\,$ [/mm] nicht symmetrisch ist, so betrachten wir anstelle von [mm] $f(x)=x^T [/mm] A x$
die Funktion [mm] $g(x)=x^T \frac{A+A^T}{2}x\,,$ [/mm] denn die beiden Funktionen haben
an den gleichen Stellen Extremalstellen (und auch jeweils von gleicher Art).
Vielleicht kann man auch der Einfachheit wegen direkt dann
[mm] $h(x)=x^T(A+A^T)x$
[/mm]
betrachten. (Der Faktor [mm] $1/2\,$ [/mm] sollte ja keine wesentlichen Auswirkungen haben.)
(Denn: [mm] $A+A^T$ [/mm] ist symmetrisch; und wenn [mm] $x^T [/mm] A x [mm] \ge [/mm] 0$ für alle [mm] $x\,,$ [/mm] dann auch
[mm] $(x^T [/mm] A [mm] x)^T=x^T A^T [/mm] x [mm] \ge [/mm] 0$ für alle [mm] $\,x;$ [/mm] insbesondere also auch [mm] $x^T Ax+x^T A^T [/mm] x [mm] \ge [/mm] 0$ für alle [mm] $x\,$
[/mm]
und damit ist [mm] $A+A^T$ [/mm] auch positiv semidefinit.
Passt doch, oder? Jaja, irgendwie vergisst man im Laufe der Jahre doch
die elemtarsten Dinge aus der L.A. ... )
Für Cauchy:
http://de.wikipedia.org/wiki/Definitheit#Symmetrischer_Anteil_bei_allgemeinen_Matrizen
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:15 Fr 16.08.2013 | | Autor: | felixf |
Moin Marcel,
> > > Na, jedenfalls, wenn Du [mm]f(x)=x^TAx[/mm] mit [mm]A\,[/mm] symmetrisch
> >
> > Dass man [mm]A[/mm] immer als symmetrisch annehmen kann hatten wir
> > schon hier. :)
>
> Danke - ich hatte das gestern schon vermutet, war mir aber
> nicht sicher.
> (Irgendwie habe ich das aber schonmal gesehen.)
>
> Sehe ich das richtig, dass Du folgendes meinst:
> Wenn [mm]A\,[/mm] nicht symmetrisch ist, so betrachten wir anstelle
> von [mm]f(x)=x^T A x[/mm]
> die Funktion [mm]g(x)=x^T \frac{A+A^T}{2}x\,,[/mm]
genau das meine ich.
> denn die beiden Funktionen haben
> an den gleichen Stellen Extremalstellen (und auch jeweils
> von gleicher Art).
Nicht nur das: die Funktionen sind sogar identisch.
> Vielleicht kann man auch der Einfachheit wegen direkt dann
>
> [mm]h(x)=x^T(A+A^T)x[/mm]
>
> betrachten. (Der Faktor [mm]1/2\,[/mm] sollte ja keine wesentlichen
> Auswirkungen haben.)
Ich wuerd einfach sagen: "O.B.d.A. sei $A$ symmetrisch." :)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 03:03 Sa 17.08.2013 | | Autor: | Marcel |
Hi Felix,
> Moin Marcel,
>
> > > > Na, jedenfalls, wenn Du [mm]f(x)=x^TAx[/mm] mit [mm]A\,[/mm] symmetrisch
> > >
> > > Dass man [mm]A[/mm] immer als symmetrisch annehmen kann hatten wir
> > > schon hier. :)
> >
> > Danke - ich hatte das gestern schon vermutet, war mir aber
> > nicht sicher.
> > (Irgendwie habe ich das aber schonmal gesehen.)
> >
> > Sehe ich das richtig, dass Du folgendes meinst:
> > Wenn [mm]A\,[/mm] nicht symmetrisch ist, so betrachten wir
> anstelle
> > von [mm]f(x)=x^T A x[/mm]
> > die Funktion [mm]g(x)=x^T \frac{A+A^T}{2}x\,,[/mm]
>
> genau das meine ich.
>
> > denn die beiden Funktionen haben
> > an den gleichen Stellen Extremalstellen (und auch
> jeweils
> > von gleicher Art).
>
> Nicht nur das: die Funktionen sind sogar identisch.
mhm, okay:
[mm] $x^T [/mm] A [mm] x+x^T A^T x=x^T [/mm] A [mm] x+(x^T [/mm] A [mm] x)^T=2x^T [/mm] A [mm] x\,,$
[/mm]
denn [mm] $x^T [/mm] A x$ ist ja eine $1 [mm] \times [/mm] 1$-Matrix bzw. damit einfach eine relle Zahl.
(Und damit ist sie gleich ihrer transponierten Matrix.)
![[bonk]](/images/smileys/bonk.gif "[bonk]")
Hättest Du das aber nicht extra gesagt, so hätte ich das nun nicht mehr
nachgerechnet.
> > Vielleicht kann man auch der Einfachheit wegen direkt dann
> >
> > [mm]h(x)=x^T(A+A^T)x[/mm]
> >
> > betrachten. (Der Faktor [mm]1/2\,[/mm] sollte ja keine wesentlichen
> > Auswirkungen haben.)
>
> Ich wuerd einfach sagen: "O.B.d.A. sei [mm]A[/mm] symmetrisch." :)
![[grins]](/images/smileys/grins.gif "[grins]") Das meinte ich aber so auch nicht:
Nach dem Durchlauf Deiner ganzen Argumenten: danach geht das hier
schon. Ich dachte, beim Beweis davon, dass [mm] $x^T (A+A^T)/2 [/mm] x$ "gleiches Verhalten"
(im erwähnten Sinne) hat, könnte man anstatt [mm] $g(x)=x^T (A+A^T)/2 [/mm] x$ einfach
[mm] $h(x)=x^T (A+A^T)x$ [/mm] betrachten.
Aber klar: Warum nun [mm] $h=2g=2f\,$ [/mm] betrachten, wenn man auch direkt einfach
[mm] $f\,$ [/mm] passend umschreiben kann...
Ich hoffe mal, dass ich das nun wieder im Gedächtnis für eine etwas
längere Zeit gespeichert haben werde.
Gruß,
Marcel
|
|
|
|
