www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 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
Dt. Schulen im Ausland: Mathe-Seiten:

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 ^
www.vorhilfe.de