Forum:  Numerik & Optimierung
Thema: Lineare Optimierung auf einer konvexen Hülle
Themen-Übersicht
episqaure
Junior
Dabei seit: 21.07.2014
Mitteilungen: 13
Aus:
Themenstart: 2020-09-24 00:04

Hallo,

ich habe ein paar Fragen zur linearen Optimierung auf einer konxeven Hülle.


Betrachten wir das folgende LP:

$\max \{ p \in \mathbb{Q} \mid 0 \leq p \leq \sqrt{2}\}$,

dann ist klar dass es keine Optimallösung gibt.

Nun habe ich im Vorlesungsskript gesehen dass als nächstes folgendes Optimierungsproblem betrachtet wird:

Sei $S = \{ (x,y) \in \mathbb{Z}^2 \mid -\sqrt{2}x+y \leq 0,  x \geq 1, y \geq 0 \}$

Wir betrachten das Maximierungsproblem
$\max \{ -\sqrt{2}x+y \mid (x,y) \in S\}$.


Nun meine Fragen:

1.) Warum kann dieses Optimierungsproblem nun keine Optimallösung haben ?
Ich habe versucht es auf das erste Optimierungsproblem zurückzuführen.

Angenommen $p_\mathrm{opt} = (x_\mathrm{opt},y_\mathrm{opt})$ sei Optimallösung.

Für $p = (x,y)$, sei $f(p):= -\sqrt{2}x+y$.

Dann gilt $f(p_\mathrm{opt}) \geq f(p)$.

Wäre $f(p_\mathrm{opt}) = 0$, so gilt $\sqrt{2} = \frac{y}{x}$. Widerspruch!

Also kann noch $f(p_\mathrm{opt}) < 0$ gelten.


Fall 1:

Ist $x_\mathrm{opt} \leq x$, dann gilt

$\frac{f(p)}{x} \leq \frac{f(p_\mathrm{opt})}{x} \leq \frac{f(p_\mathrm{opt})}{x_\mathrm{opt}}$.


Sei nun $S' = \{(x,y) \in S \mid x_\mathrm{opt} \leq x \}$.

Also gilt
 $-\sqrt{2}+\max_{p \in S'}\frac{y}{x} = \max_{p \in S'} -\sqrt{2}+\frac{y}{x} = \max_{p \in S'} \frac{f(p)}{x} \leq \frac{f(p_\mathrm{opt})}{x_\mathrm{opt}} < 0 $.
und damit $\max_{p \in S'}\frac{y}{x} < \sqrt{2}$.

Nun kann aber $\sqrt{2}$  beliebig genau durch einen Bruch approximiert werden kann.
Allerdings lasse ich nicht beliebige Brüche zu, sondern fordere $(x,y) \in S'$. Habe ich trotzdem einen Widerspruch ?


Fall 2:
$ x \leq x_\mathrm{opt}$ und $y \geq y_\mathrm{opt}$.


Hier gilt $f(p) = -\sqrt{2}*x+y \geq -\sqrt{2}*x_\mathrm{opt}+y \geq -\sqrt{2}*x_\mathrm{opt}+y_\mathrm{opt} = f(p_\mathrm{opt})$.

Also muss hier $f(p) = f(p_\mathrm{opt})$ gelten, da $f(p_\mathrm{opt})$ maximal ist.

Hier hätte ich also weitere Optimallösungen, und komme nicht zu einem Widerspruch.


Fall 3.
$ x \leq x_\mathrm{opt}$ und $y \leq y_\mathrm{opt}$.

Hier weiß ich auch nicht wie ich vorgehen könnte.

Ich habe das Gefühl, dass man das ganze viel einfacher zeigen kann.
Es wäre super wenn mir da jemand helfen kann.


Frage 2:

Warum gilt $\max \{c^T p \mid p \in S\} = \max \{c^T p \mid p \in \mathrm{conv}(S)\}$ ?

Trivialerweise gilt $\max \{c^T p \mid p \in S\} \leq \max \{c^T p \mid p \in \mathrm{conv}(S)\}$, da $S \subset \mathrm{conv}(S)$.

Wie aber zeigt man die andere Ungleichung?
Das Problem $\max \{c^T p \mid p \in \mathrm{conv}(S)\}$ kann doch eine Lösung hab, wo $p$ irrationale Einträge hat.

Ist $S$ ein Polytop, dann ist die Lösung auf einer Ecke (und damit in S). Wie zeigt man dass aber allgemein, falls $S \subset \mathbb{Q}^{n}$ gilt?

Frage 3:
Wenn $S':= S \cap \mathbb{Z}^{n} \subset \mathbb{R}^n$ eine beschränkte Menge ist, warum ist dann $\mathrm{conv}(S')$ ein Polytop in $\mathbb{Q}^{n}$ ? Die Konvexkombinationen sollten doch auch irrationale Vektoreinträge erzeugen können.


Frage 4:
Wenn $C \subset \mathbb{R}^{n}$ ein rationaler Kegel ist, warum gilt dann $C = \mathrm{conv}\{x \in C \mid x \in \mathbb{Z}^{n} \}$ ?


Ist $C = \mathrm{cone}(E)$ für $E \subset \mathbb{Q}^{n}$, dann können wir $E' \subset \mathbb{Z}^{n}$ konstruieren mit $C = \mathrm{cone}(E')$.

Für $x \in C$ gilt also $x = \sum_{i} \lambda_{i} x_{i}$, $\lambda_{i} \geq 0$ und $x_{i} \in E' \subset \mathbb{Z}^{n}$.  

Es ist $x \in \mathrm{conv}(\{x' \in C \mid x' \in \mathbb{Z}^{n} \})$, falls es endliche Koeffizienten $\lambda_{i}$ gibt mit $\sum_{i} \lambda_{i} = 1$ und $x = \sum_{i} \lambda_{i}x_{i}$, wobei jedes $x_{i} \in C \cap \mathbb{Z}^{n}$ ist.  

Die Richtung aus $x \in \mathrm{conv}(\{x' \in C \mid x' \in \mathbb{Z}^{n} \})$ folgt $x \in C$ ist mir klar.

Wie zeigt man die andere Richtung?
Ist $x \in C$, dann haben wir also die Darstellung $x = \sum_{i} \lambda_{i}x_{i}$ wobei $\lambda_{i} \geq 0$ gilt und $x_{i} \in \mathbb{Z}^{n} \cap C$.

Nun muss ich Koeffizienten  $\mu_{j}$ finden mit $\sum_{j} \mu_{j} = 1$ und $x = \sum_{j} \mu_{j} x'_{j}$ und $x'_{j} \in \mathbb{Z}^{n} \cap C$.

Setze ich $\mu_{j} = \frac{\lambda_{j}}{\sum_{i} \lambda_{i}}$ und $x'_{j} = x_{j}(\sum_{i}\lambda_{i})$, dann hab ich zwar ein konvex Kombination, aber die Vektoren $x_{j}'$ sind u.U. nicht mehr ganzzahlig.


sonnenschein96
Senior
Dabei seit: 26.04.2020
Mitteilungen: 222
Aus:
Beitrag No.1, eingetragen 2020-09-24 02:59

Hallo episqaure,

da Dein Beitrag recht lang ist, gehe ich erstmal nur auf Deine ersten beiden Fragen ein.


Dein Ansatz bei Frage 1 ist schon ziemlich gut, die Fallunterscheidung ist allerdings nicht notwendig, denke ich.

Du hast ja schon begründet, dass \(f(p_{\text{opt}})<0\) sein muss. Wie in Deiner Rechnung aus Fall 1 mit \(S\) statt \(S'\) folgt
\[-\sqrt2+\sup_{p\in S}\frac{y}{x}=\sup_{p\in S}(-\sqrt2+\frac{y}{x}) = \sup_{p\in S}\frac{f(p)}{x} \leq \sup_{p\in S}\frac{f(p_{\text{opt}})}{x} = f(p_{\text{opt}}) < 0,\] also \(\sup_{p\in S}\frac{y}{x}<\sqrt2\). Es gilt aber \(\sup_{p\in S}\frac{y}{x} = \sup\mathbb{Q}\cap[0,\sqrt2]=\sqrt2\). Widerspruch.


Zu Deiner 2. Frage: Du hast ja schon begründet, warum \(LHS\leq RHS\) ist. Ist nun \(p\in\operatorname{conv}S\), so ist \(p\) von der Form \(p=\sum_{i=1}^N\lambda_ip_i\) mit \(p_i\in S\) und \(\lambda_i\in[0,1]\) mit \(\sum_{i=1}^N\lambda_i=1\). Es gilt dann \(c^Tp=\sum_{i=1}^N\lambda_i c^Tp_i\leq\sum_{i=1}^N\lambda_i LHS =LHS\). Bildest Du das Maximum, bekommst Du also auch \(RHS\leq LHS\).

Hierbei wurde natürlich angenommen, dass die Maxima existieren. Ansonsten muss da halt das Supremum stehen.

Tatsächlich wird das Maximum genau dann auf der einen Seite angenommen, wenn es auch auf der anderen Seite angenommen wird. Nennen wir den Wert \(M\). Die eine Richtung ist klar. Gibt es andererseits ein \(p=\sum_{i=1}^N\lambda_ip_i\in\operatorname{conv}S\) (wir können \(\lambda_i\neq0\) wählen) mit \(c^Tp=M\), so muss auch \(c^Tp_i=M\) für \(i=1,\ldots,N\) (und damit wird das Maximum in LHS in den \(p_i\) angenommen), denn sonst gilt \(M=c^Tp=\sum_{i=1}^N\lambda_i c^Tp_i<\sum_{i=1}^N\lambda_i M=M\), Widerspruch.


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6616
Aus: Niedersachsen
Beitrag No.2, eingetragen 2020-09-24 09:15

Zu Frage 2)
Ist $p\in conv(S)$, dann ist $p$ eine Konvexkombination von Punkten $p_1,p_2,\dots\in S$.
Wegen der Linearität der Zielfunktion kann nun nicht $c^Tp>c^Tp_1, c^Tp_2, ...$ gelten. Es gibt also ein $p_i\in S$ mit $c^Tp_i\geq c^Tp$. Damit ist die Behauptung bewiesen.
Zu Frage 3)
Warum sollte das ein Polytop in $IQ^n$ sein? Das wäre richtig, wenn man für die Bildung der Konvexkombination nur rationale Faktoren zulassen würde.
Zu Frage 4)
Der Ansatz ist schon ganz gut. Wir haben $x=\sum_i \lambda_ix_i$. Wir setzen $C:=Aufrunden(\sum_i \lambda_i)$.
Damit gilt $x=\sum_i \frac{\lambda_i}{C}(C\cdot x_i) + (1-\sum_i \frac{\lambda_i}{C})\cdot 0$. Das zeigt das Gewünschte.




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=249537=110
Druckdatum: 2020-12-05 23:23