www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Nichtlineare Gleichungen" - Lagrange-Muliplikator
Lagrange-Muliplikator < Nichtlineare Gleich. < Numerik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Nichtlineare Gleichungen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Lagrange-Muliplikator: Hey
Status: (Frage) überfällig Status 
Datum: 16:53 So 08.07.2012
Autor: looney_tune

Aufgabe
Das Problem, den Punkt x auf einer Hyperebene {x l Ax= b, A hat vollen Zeilenrang} zu finden, der den kleinsten Abstand zu einem gegebenen Punkt [mm] x_{0} [/mm] hat, lässt sich als folgendes quadratisches Programm formulieren:

min [mm] \bruch{1}{2} [/mm] (x- [mm] x_{0})^T (x-x_{0}) [/mm]
s.t. Ax= b

a) Zeigen sie, dass der optimale Lagrange-Multiplikator gegeben ist durch
[mm] \lambda^{*}= (AA^T)^{-1}(b-Ax_{0}) [/mm]
und dass die Lösung gegeben ist durch
[mm] x^{*} [/mm] = [mm] x_{0}+ A^T(AA^T)^{-1}(b-Ax_{0}) [/mm] .

b) Betrachten sie den Spezialfall, dass A ein Zeilenvektor ist. Zeigen sie, dass dann der kürzeste Abstand von [mm] x_{0} [/mm] zur Lösungsmenge von Ax= b gegeben ist durch
[mm] \bruch{|b-Ax_{0}|}{||A||_{2}} [/mm]

zu a) Lagrangefunktion sieht so aus:

[mm] L(x,\lambda) [/mm] = [mm] \bruch{1}{2}(x-x_{0})^T(x-x_{0})-\lambda^T(Ax-b) [/mm]

sonst weiß ich nicht, wie ich das zeigen kann?

zu b)
hier weiß ich gar nicht, wie ich das zeigen soll.

Kann mir jemand weiterhelfen?

Lieber Gruß

        
Bezug
Lagrange-Muliplikator: zu a)
Status: (Antwort) fertig Status 
Datum: 00:16 Mo 09.07.2012
Autor: barsch

Hallo,


> Das Problem, den Punkt x auf einer Hyperebene {x l Ax= b, A
> hat vollen Zeilenrang} zu finden, der den kleinsten Abstand
> zu einem gegebenen Punkt [mm]x_{0}[/mm] hat, lässt sich als
> folgendes quadratisches Programm formulieren:
>  
> min [mm]\bruch{1}{2}[/mm] (x- [mm]x_{0})^T (x-x_{0})[/mm]
>  s.t. Ax= b
>  
> a) Zeigen sie, dass der optimale Lagrange-Multiplikator
> gegeben ist durch
>  [mm]\lambda^{*}= (AA^T)^{-1}(b-Ax_{0})[/mm]
>  und dass die Lösung
> gegeben ist durch
>  [mm]x^{*}[/mm] = [mm]x_{0}+ A^T(AA^T)^{-1}(b-Ax_{0})[/mm] .
>  
> b) Betrachten sie den Spezialfall, dass A ein Zeilenvektor
> ist. Zeigen sie, dass dann der kürzeste Abstand von [mm]x_{0}[/mm]
> zur Lösungsmenge von Ax= b gegeben ist durch
>  [mm]\bruch{|b-Ax_{0}|}{||A||_{2}}[/mm]
>  zu a) Lagrangefunktion sieht so aus:
>  
> [mm]L(x,\lambda)[/mm] = [mm]\bruch{1}{2}(x-x_{0})^T(x-x_{0})-\lambda^T(Ax-b)[/mm]

Ja.

> sonst weiß ich nicht, wie ich das zeigen kann?

Schreibe dir mal die notwendigen Bedingungen 1. Ordnung (KKT-Bedingungen) auf! Dann springt dir die Lösung fast ins Auge.

> zu b)
>  hier weiß ich gar nicht, wie ich das zeigen soll.
>  
> Kann mir jemand weiterhelfen?
>  
> Lieber Gruß

Gruß
barsch


Bezug
                
Bezug
Lagrange-Muliplikator: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:54 Mo 09.07.2012
Autor: looney_tune

ich weiß nicht genau, wie die ableitung der lagrangefunktion ist, die brauche ich ja für die kkt-bdg.

Bezug
                        
Bezug
Lagrange-Muliplikator: Antwort
Status: (Antwort) fertig Status 
Datum: 17:16 Mo 09.07.2012
Autor: barsch

Hallo,


> ich weiß nicht genau, wie die ableitung der
> lagrangefunktion ist, die brauche ich ja für die kkt-bdg.

wie du in deiner 1. Frage richtig erkannt hast, ist [mm]L(x,\lambda)= \bruch{1}{2}(x-x_{0})^T(x-x_{0})-\lambda^T(Ax-b) [/mm]

Jetzt bestimme

[mm]L_x=\bruch{\partial \ L}{\partial \ x}[/mm] und [mm]L_\lambda=\bruch{\partial \ L}{\partial \ \lambda}[/mm]. Letzters dürfte nicht allzu schwer sein.

Wenn du nicht weißt, wie du den Teil [mm](x-x_0)^T*(x-x_0)[/mm] nach x ableiten sollst, dann mache dir doch erst einmal klar, wie du [mm]x^T*x[/mm] nach x ableitest. Wobei [mm]x\in\IR^n[/mm], also ein Vektor! Du kannst es dir ja mal an n=2 oder n=3 konkret verdeutlichen.

Gruß
barsch



Bezug
                                
Bezug
Lagrange-Muliplikator: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:42 Mo 09.07.2012
Autor: looney_tune

[mm] L_x=\bruch{\partial \ L}{\partial \ x} [/mm] = [mm] x^T+x-x_{0}-x_{0}^T-\lambda^TA [/mm]
= [mm] 2x-2x_{0}-\lambda^TA [/mm]

[mm] L_\lambda=\bruch{\partial \ L}{\partial \ \lambda}= [/mm] -Ax+b

stimmt das so?

Bezug
                                        
Bezug
Lagrange-Muliplikator: Antwort
Status: (Antwort) fertig Status 
Datum: 22:39 Mo 09.07.2012
Autor: barsch

Hallo!


> [mm]L_x=\bruch{\partial \ L}{\partial \ x}[/mm] = [mm]x^T+x-x_{0}-x_{0}^T-\lambda^TA[/mm] = [mm]2x-2x_{0}-\lambda^TA[/mm]

Leider nein!

> [mm]L_\lambda=\bruch{\partial \ L}{\partial \ \lambda}=[/mm] -Ax+b

korrekt!

>  
> stimmt das so?

Lass' uns einmal konkret [mm]f:\IR^3\to\IR, \ f(z)=\bruch{1}{2}z^T*z[/mm] betrachten. Das bedeutet [mm]z=\vektor{z_1 \\ z_2 \\ z_3}[/mm] und somit [mm]f(z)=\bruch{1}{2}z^T*z=\bruch{1}{2}*(z_1,z_2,z_3)*\vektor{z_1 \\ z_2 \\ z_3}=\bruch{1}{2}*(z_1^2+z_2^2+z_3^2)[/mm].

Dann ist [mm]\bigtriangledown f(z)=\bruch{1}{2}*\vektor{2*z_1 \\ 2*z_2 \\ 2*z_3}=\vektor{z_1 \\ z_2 \\ z_3}=z[/mm].


Das geht analog für [mm]z=x-x_0[/mm].

Und jetzt bestimme noch einmal [mm] $L_x$. [/mm]

Gruß
barsch


Bezug
        
Bezug
Lagrange-Muliplikator: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:20 Mi 11.07.2012
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Nichtlineare Gleichungen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]