Lagrange-Muliplikator < Nichtlineare Gleich. < Numerik < Hochschule < Mathe < Vorhilfe
|
| 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ß
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
|
|
|
| |
|
ich weiß nicht genau, wie die ableitung der lagrangefunktion ist, die brauche ich ja für die kkt-bdg.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
[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?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Mi 11.07.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
