Antworte auf:  Lineare Optimierung auf einer konvexen Hülle von episqaure
Forum:  Numerik & Optimierung, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 

Erledigt J


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6603
Herkunft: Niedersachsen
 Beitrag No.2, eingetragen 2020-09-24 09:15    [Diesen Beitrag zitieren]

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.


sonnenschein96
Senior
Dabei seit: 26.04.2020
Mitteilungen: 211
Herkunft:
 Beitrag No.1, eingetragen 2020-09-24 02:59    [Diesen Beitrag zitieren]

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.


episqaure
Junior
Dabei seit: 21.07.2014
Mitteilungen: 13
Herkunft:
 Themenstart: 2020-09-24 00:04    [Diesen Beitrag zitieren]

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.


 
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]