Lineare Optimierung II

10.11.2006, 00:46

Kleines Fragezeichen

Lineare Optimierung II

Hallo, bin ein wenig verzweifelt, weil ich mit meinen Aufgaben alleine nicht klarkomme und habe beim Recherchieren dieses Board gefunden.

Ich muss drei Beweise führen und finde keinen rechten Ansatz. Die Aufgaben sind folgende:

1) Sei S Teilmenge des R^n und C die Menge aller nichtnegativen (d.h. mit nicht negativen KOeffizienten) Linearkkombinationen von Elementen aus S.
Zeigen sie: C ist der kleinste S enthaltende konvexe Kegel

2) Seien C Teilmenge des R^n konvexe Menge, x Element des ri C, d Element des R^n und G={y:y=wd, w größergleich 0}
Zeigen sie, dass die Halbgerade G den relativen RAnd der Menge C höchstens in einem Punkt schneidet.

3) Seien C Teilmenge des R^n, konvex und a Element C.
Zeigen sie, dass gilt:
a Element int C <=> für alle x ELement R^n \ {a} existiert ein b > 0: a + b ( x - a) Element C

Vielen Dank schon mal im Voraus, liebe Grüße...

10.11.2006, 09:09

Dual Space

Auf diesen Beitrag antworten »

RE: Lineare Optimierung II
Also bei 1) musst du Folgendes zeigen:

$\begin{eqnarray*} S\subseteq C \end{eqnarray*}$
C ist konvex
C ist Kegel
Es gibt keinen konvexen Kegel $\begin{eqnarray*} K \end{eqnarray*}$ mit $\begin{eqnarray*} S\subseteq K\subsetneqq C \end{eqnarray*}$

10.11.2006, 11:05

Kleines Fragezeichen

Auf diesen Beitrag antworten »

RE: Lineare Optimierung II
Hab mit Hängen und WÜrgen die ersten drei Punkte bewiesen...

Beim letzten komm ich allerdings nicht weiter. Ich hab mal angenommen, dass ein solcher konvexer Kegel K existiert und versucht meine Annahme zum Widerspruch zu bringen, was aber nicht so recht geklappt hat. Ist das der richtige Weg? Wie mach ich nach meiner Annahme weiter?

Viele liebe Grüße

10.11.2006, 13:33

Dual Space

Auf diesen Beitrag antworten »

RE: Lineare Optimierung II
Angenommen ein solcher Kegel K existiere. Wähle $\begin{eqnarray*} x\in C\setminus K \end{eqnarray*}$ . Dann besitzt x eine Darstellung

$\begin{eqnarray*} x=\sum_{i=1}^n \alpha_i s_i \end{eqnarray*}$ mit $\begin{eqnarray*} s_i\in S \end{eqnarray*}$ und $\begin{eqnarray*} \alpha_i\geq 0 \end{eqnarray*}$ für alle i. Definiere $\begin{eqnarray*} \alpha:=(\alpha_1,\dots,\alpha_n) \end{eqnarray*}$ . Damit ist

$\begin{eqnarray*} \overline{x}=\sum_{i=1}^n \frac{\alpha_i}{|\alpha|} s_i\in C\setminus K \end{eqnarray*}$

und $\begin{eqnarray*} \overline{x} \end{eqnarray*}$ ist eine Konvexkombination der $\begin{eqnarray*} s_i \end{eqnarray*}$ , aber gleichzeitig $\begin{eqnarray*} \overline{x}\not\in K \end{eqnarray*}$ . Da nun aber K konvex ist, existiert ein $\begin{eqnarray*} s_k \end{eqnarray*}$ mit $\begin{eqnarray*} k=1,\dots,n \end{eqnarray*}$ , so dass $\begin{eqnarray*} s_k\not\in K \end{eqnarray*}$ und somit $\begin{eqnarray*} S\not\subset K \end{eqnarray*}$ .

10.11.2006, 14:52

Kleines Fragezeichen

Auf diesen Beitrag antworten »

RE: Lineare Optimierung II
Danke, dass hab ich verstanden. Den zweiten Beweis hab ich mehr oder weniger hinbekommen.
Hast die vielleicht eine Idee, wie man an die dritte Aufgabe rangehen könnte?

10.11.2006, 16:35

Dual Space

Auf diesen Beitrag antworten »

RE: Lineare Optimierung II
Beginnen wir mit:

$\begin{eqnarray*} a\in \operatorname{int} C \Rightarrow \forall x\in\mathbb{R}^n\setminus \{a\} ~\exists \xi>0: a+\xi(x-a)\in C \end{eqnarray*}$

Beweis (Skizze): Sei also $\begin{eqnarray*} a \in \operatorname{int} C \end{eqnarray*}$ , d.h. es gibt eine Kugel mit dem Radius $\begin{eqnarray*} \delta>0 \end{eqnarray*}$ und Mittelpunkt a, $\begin{eqnarray*} U_\delta(a) \end{eqnarray*}$ , die ganz in C liegt. Dann ist

$\begin{eqnarray*} a+\xi(x-a)\in C \end{eqnarray*}$ für jedes $\begin{eqnarray*} \xi<\frac{\delta}{|x-a|}. \end{eqnarray*}$

Um das zu Verstehen hilft eine Skizze.

Versuch nun mal die andere Richtung.

10.11.2006, 21:10

Kleines Fragezeichen

Auf diesen Beitrag antworten »

RE: Lineare Optimierung II
Das kann ich nachvollziehen, allerdings wär ich da nie selbst drauf gekommen... Vielen vielen Dank. Versuch mich mal selbst an der Rückrichtung. Muss ich noch irgendwas ergänzen (Zwischenschritte oder so?) weil du "Beweisskizze" geschrieben hast?

11.11.2006, 10:18

Dual Space

Auf diesen Beitrag antworten »

RE: Lineare Optimierung II

Zitat:

Original von Kleines Fragezeichen
Muss ich noch irgendwas ergänzen (Zwischenschritte oder so?) weil du "Beweisskizze" geschrieben hast?

Naja sicher wär es schön, wenn man ein wenig ausführlicher ausrechnet, wie groß $\begin{eqnarray*} \xi \end{eqnarray*}$ sein darf.

12.03.2007, 22:38

Matheloser :(

Auf diesen Beitrag antworten »

Ich weiß, auf Dauer nerv ich xD

Ich hab nur mal eine Frage zum grafischen Lösen:
Muss ich meine Gleichungen einfach nach y umstellen und diese dann zeichnen? Ich habe die Aufgabe (Max(2,3)x udN x>=0 im Gleichungssysthem
1x+2x2<=4
x+x2<=3

und die Zielfunktion umgestellt? Wäre das richtig oder habe ich (so blöde, wie ich bin xD) mal wieder etwas übersehen?

edit (Abakus): das ist in Lineare Optimierung - Simplex gelöst

Neue Frage »

Antworten »

Lineare Optimierung II

Verwandte Themen