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 "Operations Research" - Lineare Optimierung
Lineare Optimierung < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Operations Research"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Lineare Optimierung: Convex Optimization
Status: (Frage) beantwortet Status 
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

        
Bezug
Lineare Optimierung: Antwort
Status: (Antwort) fertig Status 
Datum: 23:00 Sa 07.07.2012
Autor: wieschoo

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?

Bezug
                
Bezug
Lineare Optimierung: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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



Bezug
                        
Bezug
Lineare Optimierung: Antwort
Status: (Antwort) fertig Status 
Datum: 21:16 Mo 09.07.2012
Autor: wieschoo

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."  ;-)




Bezug
                                
Bezug
Lineare Optimierung: Frage (überfällig)
Status: (Frage) überfällig Status 
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

Bezug
                                        
Bezug
Lineare Optimierung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                        
Bezug
Lineare Optimierung: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:20 Sa 14.07.2012
Autor: matux

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


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