Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Lineare Optimierung auf einer konvexen Hülle
Druckversion
Druckversion
Autor
Universität/Hochschule J Lineare Optimierung auf einer konvexen Hülle
episqaure
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 21.07.2014
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sonnenschein96
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 26.04.2020
Mitteilungen: 137
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6571
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
episqaure hat die Antworten auf ihre/seine Frage gesehen.
episqaure hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]