Lineare Optimierung < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:59 Mi 04.07.2012 | | Autor: | Jan87 |
Hallo zusammen, ich habe ein schwerwiegendes Problem. Für ein Seminar muss ich einen Vortrag halten (schon geschehen, hat super geklappt) und zusätzlich eine Belegaufgabe lösen. Beides bezieht sich auf das Buch „Convex optimiziation“ von Boyd/Vandenberghe. Leider sitze ich jetzt schon mehrere Tage an dieser Belegaufgabe (5.6) und komme auf keinen grünen Zweig.
Aufgabe 5.6
minimiere ||Ax-b|| (Maximumsnorm)
mit A aus Rmxn und rang(A)=n
Sei xch eine optimale Lösung. Das Tschebyscheff Problem hat keine Lösung in geschlossener Form, aber das entsprechende Problem der kleinsten Quadrate hat eine.
Definiere: xls=argmin ||Ax-b||2 = (ATA)-1ATb
a) Zeige, dass die untere Schranke
||Axls –b||Max <= sqrt(m) ||Axch –b||Max
ist, benutze dabei, dass für alle z in Rm
1/sqrt(m) ||z||2 <= ||z||Max <= ||z||2 (euklidische Norm)
b) maximiere bTv
u.d.N. ||v||1 <=1 und ATv=0 (xx)
Alle möglichen v entsprechen einer unteren Schranke bTv auf ||Axch –b||Max, bezeichne den Rest der kleinsten Quadrate als rls=b-Axls. Unter der Annahme rls ist ungleich 0, zeige dass
v1=-rls/||rls||1 und v2=rls/||rls||1
beide in (xx) möglich sind. Mit Dualität von bTv1 und bTv2 sind untere Schranken auf ||Axch-b||Max definiert, welche ist die bessere Schranke? Wie wirken sich diese Schranken verglichen mit der in Teil a) erhaltenen Schranke?
Bis jetzt konnte ich bloß zeigen, dass sowohl v1 als auch v2 die Bedingung ||v||1<=1 erfüllen.
Ich denke wenn ich die Lösung der Aufgabe b) habe, kann die a) nicht mehr so schwer sein.
Das müsste doch am Ende mit der schwachen Dualität cTx<=bTv Funktionieren, aber ich kann „minimiere ||Ax-b||Max“ nicht so umschreiben, dass ich es als Standardproblem mit einem cTx da stehen haben.
Herzlichen Dank für die Hinweise im Voraus,
Gruß Jan
Ps. das T bedeudet Transponiert
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:http://www.onlinemathe.de/forum/Lineare-Optimierung-Convex-optimization
|
|
| |
|
a) Schätze [mm]\lVert Ax_{ch}-b\rVert_{\max}[/mm] erst mit der gegebenen Ungleichung ab. Dann verwende dass [mm]\lVert Ax_{ch}-b\rVert_{2}\geq \lVert Ax_{ls}-b\rVert_{2}[/mm] gilt.
b) Ist da jetzt bei dir noch etwas offen?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:29 Mo 09.07.2012 | | Autor: | Jan87 |
Dankeschön wiescho,
Aufgabenteil a) hab ich mittlerweile lösen können, da [mm] x_l_s =argmin \begin{Vmatrix}
Ax-b
\end{Vmatrix}_2 [/mm]nach Vorgabe gilt, folgt [mm] \begin{Vmatrix}
Ax_l_s -b
\end{Vmatrix}_2 \le \begin{Vmatrix}
Ax_c_h -b
\end{Vmatrix}_2 [/mm] und der Rest ist ja dann mit dem Hinweis aus der Angabe nicht mehr schwer.
Bei Aufgabenteil b) hab ich mittlerweile gezeigt, dass sowohl [mm] v_1 [/mm] als auch [mm] v_2 [/mm] zulässig sind.
Ich vermute, dass der Unterschied zwischen der Schranke aus a) und denen aus b) darin besteht, dass die Schranke aus a) eine obere Schranke ist, während die Schranken aus b) alle untere Schranken sind.
Stimmt das???
Probleme hab ich noch bei dem letzten Teil von b), wie kann ich zeigen welche die bessere Schranke ist (also größer) [mm] b^Tv_1 [/mm] oder [mm] b^Tv_2 [/mm]?
Ich hab rumprobiert und komme auf:
[mm] b^Tv_1= \frac{-\begin{vmatrix}
b
\end{vmatrix}^2 + b^TXb}{\begin{Vmatrix}
r_l_s
\end{Vmatrix}_1}[/mm]
[mm] b^Tv_2 = \frac{\begin{vmatrix}
b
\end{vmatrix}^2 - b^TXb}{\begin{Vmatrix}
r_l_s
\end{Vmatrix}_1}[/mm]
Wobei X eine idempotente Matrix mit [mm] X=A(A^TA)^-^1A^T [/mm] ist, somit sind alle ihre Eigenwerte 0 oder 1 und die Matrix folglich positiv semidefinit. Daraus folgt, dass [mm] b^TXb \ge 0 [/mm]
Also stellt sich bloß noch die Frage, ob [mm]\begin{vmatrix}
b
\end{vmatrix}^2 [/mm] oder [mm]b^TXb[/mm] größer ist und somit welche Schranke ([mm]b^Tv_1[/mm] oder [mm]b^Tv_2 [/mm]) positiv und welche negativ ist, die positive ist dann die bessere. Oder???
Gruß Jan
|
|
|
| |
|
Aus [mm]x_{ls}=(A^TA)^{-1}A^Tb[/mm] folgt
[mm]A^Tr_{ls}=A^T(b-A(A^TA)^{-1}b)=A^Tb-A^Tb=0[/mm]
Also [mm]A^Tv_i=0[/mm].
Jetzt ist
[mm]b^Tv_1=\frac{-b^Tr_{ls}}{\lVert r_{ls}\rVert_1}=\frac{(Ax_{ls}-b)^Tr_{ls}}{\lVert r_{ls}\rVert_1}=-\frac{\lVert r_{ls}\rVert_2^2}{\lVert r_{ls}\rVert_1}[/mm]
und [mm]b^Tv_2=-b^Tv_1[/mm].
Um zu zeigen, dass die untere Schranke besser als die Schranke von der vorherigen Teilaufgabe ist musst du zeigen, dass
[mm]\frac{1}{\sqrt{m}}\lVert r_{ls}\rVert_{\infty}\leq \frac{\lVert r_{ls} \rVert_2^2}{\lVert r_{ls} \rVert_1}[/mm]
edit:" .... gilt." 
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 10:25 Di 10.07.2012 | | Autor: | Jan87 |
Da [mm] b^Tv_1 \ge [/mm] 0 und [mm] b^Tv_2 \le [/mm] 0 gilt ist [mm] b^Tv_1 [/mm] somit die bessere Schranke.
[mm] \frac{\begin{Vmatrix}r_l_s \end{Vmatrix}_2^2}{\begin{Vmatrix} r_l_s \end{Vmatrix}_1} \ge \frac{\begin{Vmatrix}r_l_s \end{Vmatrix}_\infty^2}{\begin{Vmatrix} r_l_s \end{Vmatrix}_1} [/mm] = [mm] \frac{\begin{Vmatrix}r_l_s \end{Vmatrix}_\infty}{\begin{Vmatrix} r_l_s \end{Vmatrix}_1}\begin{Vmatrix}r_l_s \end{Vmatrix}_\infty \ge \frac{x_m_a_x}{m*x_m_a_x}\begin{Vmatrix}r_l_s \end{Vmatrix}_\infty [/mm] = [mm] \frac{1}{m}\begin{Vmatrix}r_l_s \end{Vmatrix}_\infty \ge \frac{1}{\sqrt{m}}\begin{Vmatrix}r_l_s \end{Vmatrix}_\infty
[/mm]
Somit wäre die untere Schranke aus Teil b) größer (also besser) wie die aus Teil a).
Wie wäre dann die Antwort auf die Frage:
"Wie wirken diese Schranken (von b) verglichen mit der in Teil a) erhaltenen Schranke?"
Weil sie sind ja anscheinend doch alles untere Schranken. Aber die des dualen Problems sind nicht alle besser wie die des primalen Problems.
Letzte Frage, dann hab ich alles:
Wie kommst du auf [mm] b^T=(Ax_l_s -b)^T???
[/mm]
Jan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:45 Mi 11.07.2012 | | Autor: | Jan87 |
Also ich hab das ganze jetzt verstanden.
Da aus dem Beweis von [mm]A^T v_1 =0 [/mm]folgt[mm] A^T r_l_s =0 [/mm] gilt:[mm]
-b^T r_l_s = x_l_s^T*0 -b^T r_l_s =x_l_s^T A^T r_l_s -b^T r_l_s =(Ax_l_s -b)^T r_l_s = || r_l_s ||_2^2 \ge 0 [/mm]
Dankeschön für die Hilfe
Gruß Jan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Sa 14.07.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
