Minimierungsproblem < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 15:32 Do 17.05.2012 | | Autor: | looney_tune |
| Aufgabe | Zeigen sie:
seien A [mm] \in \IR^{m x n} [/mm] mit m [mm] \ge [/mm] n, und b [mm] \in \IR^n [/mm] , Rang A= n. Dann löst [mm] x^{*}genau [/mm] dann die lineare [mm] l_{1} [/mm] - Ausgleichsaufgabe
min [mm] \parallel [/mm] Ax-b [mm] \parallel_{1} [/mm] = [mm] \summe_{i=1}^{m}|(Ax-b)|_{i}, [/mm] x [mm] \in \IR^n [/mm] , wenn [mm] \lambda^ [/mm] {*} [mm] \in \IR^m [/mm] existiert, so dass
[mm] A^T \lambda [/mm] ^{*} = 0 , [mm] |\lambda_{i}^{*}| \le [/mm] 0
[mm] \lambda_{i}^{*} [/mm] = 1, falls [mm] (Ax^{*} -b)_{i} [/mm] < 0
[mm] \lambda_{i}^{*} [/mm] = - 1, falls [mm] (Ax^{*} -b)_{i} [/mm] > 0 |
In der Aufgabe habe ich versucht das Problem in eine lineare Programmierung zu transformiern, das sieht dann so aus:
min s
s.t. Ax-b [mm] \le [/mm] s
b-Ax [mm] \le [/mm] b
Hier muss ich die Lagrangefunktion aufstellen.
Sieht die dann so aus:
L(x, [mm] \lambda, \mu) [/mm] = s + [mm] \lambda^T [/mm] (Ax-b-s) [mm] -\mu^T [/mm] (b-Ax-b)
stimmt das so und dann müssen die KKT-Bedingungen aufgestellt werden, die kriege ich irgendwie nicht hin.
Und was muss ich weiter noch machen?
Kann mir jemand weiterhelfen
Lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:19 Do 17.05.2012 | | Autor: | barsch |
Hallo,
> Zeigen sie:
> seien A [mm]\in \IR^{m x n}[/mm] mit m [mm]\ge[/mm] n, und b [mm]\in \IR^n[/mm] ,
> Rang A= n. Dann löst [mm]x^{*}genau[/mm] dann die lineare [mm]l_{1}[/mm] -
> Ausgleichsaufgabe
> min [mm]\parallel[/mm] Ax-b [mm]\parallel_{1}[/mm] =
> [mm]\summe_{i=1}^{m}|(Ax-b)|_{i},[/mm] x [mm]\in \IR^n[/mm] , wenn [mm]\lambda^[/mm]
> {*} [mm]\in \IR^m[/mm] existiert, so dass
> [mm]A^T \lambda[/mm] ^{*} = 0 , [mm]|\lambda_{i}^{*}| \le[/mm] 0
> [mm]\lambda_{i}^{*}[/mm] = 1, falls [mm](Ax^{*} -b)_{i}[/mm] < 0
> [mm]\lambda_{i}^{*}[/mm] = - 1, falls [mm](Ax^{*} -b)_{i}[/mm] > 0
>
> In der Aufgabe habe ich versucht das Problem in eine
> lineare Programmierung zu transformiern, das sieht dann so
> aus:
>
> min s
zu minimieren, ist die Summe über die [mm]s_i[/mm]. Das heißt:
[mm]min \ \ \sum{s_i}[/mm]
[mm]s.t. \ \ (Ax-b)_i+s_i\geq{0}[/mm]
[mm]\ \ \ \ -(Ax-b)_i+s_i\geq{0}[/mm]
Jetzt lass' dich nicht irritieren, die Nebenbedingungen entsprechen deinen Nebenbedingingen! Ich hoffe, du siehst das.
> s.t. Ax-b [mm]\le[/mm] s
> b-Ax [mm]\le[/mm] b
Du meinst [mm]\leq{s}[/mm] in der letzten Ungleichung. Ich sehe gerade, du schleppst das falsche b mit. Wie kommst du auf das b?
> Hier muss ich die Lagrangefunktion aufstellen.
> Sieht die dann so aus:
> L(x, [mm]\lambda, \mu)[/mm] = s + [mm]\lambda^T[/mm] (Ax-b-s) [mm]-\mu^T[/mm](b-Ax-b)
Nicht ganz. Anstelle s muss die Summe der [mm] $s_i$ [/mm] genommen werden. Sonst kannst du auch gar nicht addieren. s ist ein Vektor aus [mm] $\IR^n$. [/mm] Die restlichen Summanden sind aber aus [mm] $\IR$. [/mm] Wenn ich meine Formulieren nehme, erhalte ich für die Lagrangefunktion:
[mm]L=\sum{s_i} \ + \ \lambda^T((Ax-b)+s)\ + \ \mu^T*(-(Ax-b)+s)[/mm]
> stimmt das so und dann müssen die KKT-Bedingungen
> aufgestellt werden, die kriege ich irgendwie nicht hin.
Warum nicht? Woran scheitert's?
> Und was muss ich weiter noch machen?
Erst einmal KKT-Bedingungen bestimmen!
> Kann mir jemand weiterhelfen
> Lg
Gruß
barsch
|
|
|
| |
|
[mm] L=\sum{s_i} [/mm] \ + \ [mm] \lambda^T((Ax-b)+s)\ [/mm] + \ [mm] \mu^T\cdot{}(-(Ax-b)+s)
[/mm]
für die KKT-Bedingungen
soll ja
[mm] L_{x} [/mm] (x, [mm] \mu, \lambda) [/mm] = 0 sein
das wäre dann: [mm] \lambda [/mm] A [mm] -\mu [/mm] A = 0
[mm] \lambda [/mm] ^T g(x)= 0, also [mm] \lambda^T [/mm] ((Ax-b)+s) = 0
[mm] \lambda \ge [/mm] 0, g(x) [mm] \le [/mm] 0
so würde ich die KKT-Bedingungen formulieren. Kann das sein?
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:42 Fr 18.05.2012 | | Autor: | barsch |
> [mm]L=\sum{s_i}[/mm] \ + \ [mm]\lambda^T((Ax-b)+s)\[/mm] + \
> [mm]\mu^T\cdot{}(-(Ax-b)+s)[/mm]
>
> für die KKT-Bedingungen
> soll ja
> [mm]L_{x}[/mm] (x, [mm]\mu, \lambda)[/mm] = 0 sein
Es ist [mm]L(x,s,\lambda,\mu)[/mm] - also insbesondere ist L von s abhängig.
> das wäre dann: [mm]\lambda[/mm] A [mm]-\mu[/mm] A = 0
Ja.
Zudem [mm]L_s(x,s,\lambda,\mu)=0[/mm]
> [mm]\lambda[/mm] ^T g(x)= 0, also [mm]\lambda^T[/mm] ((Ax-b)+s) = 0
> [mm]\lambda \ge[/mm] 0, g(x) [mm]\le[/mm] 0
Nebenbei bemerkt, übersichtlich ist was anderes.
Es muss doch zudem gelten:
[mm]((Ax-b)+s) \geq 0[/mm]
[mm](-(Ax-b)+s) \geq 0[/mm]
[mm]\lambda,\mu\geq 0[/mm]
[mm]\lambda^T*((Ax-b)+s) = 0[/mm] (das hast du!)
Aber auch: [mm]\mu^T*(-(Ax-b)+s) = 0[/mm]
Und mit den Ungleichungen musst du ein wenig "spielen", um dein [mm]\lambda^\star[/mm] zu erhalten.
Da fällt mir auf, in deiner Aufgabenstellung soll es doch sicher heißen: [mm]\left | \lambda_i^\star\right |\leq 1[/mm] und nicht [mm]\left | \lambda_i^\star\right |\leq 0[/mm].
> so würde ich die KKT-Bedingungen formulieren. Kann das
> sein?
>
> LG
>
Gruß
barsch
|
|
|
|
