Suchwörter   (werden UND-verknüpft)
Keines der folgenden   keine eigenen Beiträge
Name des Autors 
resp. Themenstellers 

nur dessen Startbeiträge
auch in Antworten dazu
Forum 
 Suchrichtung  Auf  Ab Suchmethode  Sendezeit Empfehlungbeta [?]
       Die Suche erfolgt nach den angegebenen Worten oder Wortteilen.   [Suchtipps]

Link auf dieses Suchergebnis hier

Forum
Thema Eingetragen
Autor

Theoretische Informatik
Universität/Hochschule 
Thema eröffnet von: episqaure
Quadratisches Problem NP-Schwer  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-12-27
episqaure
J

Hallo,


ich habe ein binäres quadratisches Problem der Form


$\min_{\mathbf{x} \in C} \sum_{v} c_{v} x_{v} + \sum_{v,w} \frac{1}{2}q_{v,w}x_{v}x_{w}$,

wobei $C := \{0,1\}^{n}$ gelten soll.

Ich möchte nun zeigen, dass das allgemeine Problem für beliebige Kosten $c$ und $q$ NP-schwer ist.

Kann ich dazu den Speziallfall $q_{v,w} = 0$, für all $v,w$ betrachten? Dadurch hätte ich als Teilproblem ein binäres lineares Problem, für das ich bereits weiß, dass es NP-Schwer ist.

Kann ich damit nun folgern, dass das ursprüngliche Problem auch NP-Schwer ist ?


Theoretische Informatik
Universität/Hochschule 
Thema eröffnet von: episqaure
Komplexität von Optimierungsproblemen  
Beitrag No.2 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-10-13
episqaure
 

Vielen Dank für die Antwort, das hat mir schonmal geholfen.


Ein paar Anmerkungen noch:

1.) Nach www.tcs.ifi.lmu.de/lehre/ws-2015-16/kompl/bovetcrescenzi
wird Komplexitätstheorie bezüglich einer Sprache definiert, und nicht bezüglich einem Entscheidungsproblem.

Ein Entscheidungsproblem wird dort definiert als ein Tripel $P:=(I,S,\pi)$,  wobei $I$ eine Menge von Wörter ist, $S$ eine Abbildung die jedes $x \in I$ auf eine endliche Menge abbildet und $\pi$ ein Prädikat. Dann ist das Entscheidungsproblem: Bestimme für $x \in I$, ob  $\Phi(x):= \{y \in S(x) \mid \pi(x,y)\}$ nicht leer ist.

Betrachten wir nun $L_{P}:=\{x \in \Sigma^{*} \mid  \Phi(x) \neq \emptyset \}$, dann ist laut Skript $L_{P}$ die zum Entscheidungsproblem zugehörige Sprache.

Es geht insgesamt also darum, ob eine TM $L_{P}$ akzeptiert bzw. entscheidet.
Aber die Theorie wird allgemein für eine Sprache $L \subset \Sigma^{*}$ entwickelt.

Hab ich da was falsch verstanden ?

2.)

Ich sehe ein, dass wenn das Entscheidungsproblem zu einem Optimierungsproblem schwer ist, dass das bereits eine Aussage für die Schwierigkeit des  Optimierungsproblem liefert.

Korrekterweise müsste man dann aber nicht nur ein Entscheidungsproblem betrachten, sondern das schwierigste, richtig?


Beispiel:
"Gibt es im gewichteten Graph G=(V,E,w) eine Rundreise, deren Länge kleiner ist als L?"
Wenn ich effizient ein US berechnen kann, so ist etwa für $L := US-1$ das Entscheidungsproblem ja effizient lösbar.



Theoretische Informatik
Universität/Hochschule 
Thema eröffnet von: episqaure
Komplexität von Optimierungsproblemen  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-10-12
episqaure
 

Hallo,

ich habe eine paar Frage zur Komplexität von Optimierungsproblemen.
Oft ließt man, dass ein Problem in P oder NP liegt, oder sogar NP-schwer ist.

Beispielsweise ist die Lineare Optimierung in P, die ganzzahlige lineare Optimierung ist aber NP-schwer.

Was genau heißt das aber ?
Wir haben hier doch erstmal kein Entscheidungsproblem, sondern ein Berechnungsproblem.

Meine Fragen daher:

(1) Müsste man nicht transducer Turing maschinen betrachten und dann entsprechend von FP und FNP sprechen ?
(2) Sagt man dann auch FNP-schwer und FNP-vollständig ?
(3) Eine Funktion $f$ heißt berechenbar, wenn es eine deterministiche  transducer Turing maschine $T$ gibt mit $T(x) = f(x)$ für alle $x$ für die $f(x)$ definiert ist. Allerdings ist die Lösung von linearen Optimierungsproblem nicht immer eindeutig, daher wäre hier zusätzlich die Frage, ob es eine Turing maschine gibt, welche genau die Optimallösungen ausgibt, wie $f$.


Ich weiß, dass die Theorie mittels einer Sprache $L \subset \Sigma^{*}$ formalisiert ist und ich zu einem Entscheidungsproblem die Wörter betrachte, welche den Wert "true" haben, was mir also solch eine Sprache $L$ definiert.





Numerik & Optimierung
Universität/Hochschule 
Thema eröffnet von: episqaure
Lineare Optimierung auf einer konvexen Hülle  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-09-24
episqaure
J

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.

Numerik & Optimierung
Universität/Hochschule 
Thema eröffnet von: episqaure
Lineare Optimierung, simpler Algorithmus  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-09-17
episqaure
 

Ok, ein Ansatz wäre,
eine Ecke für das duale Program zu berechnen, also Schritt (3) für das duale Program. Das wären dann "nur" Gleichungssysteme.

(Mir ist klar dass das ganze nicht effizient ist, dass es zu viele Ecken gibt..)

Numerik & Optimierung
Universität/Hochschule 
Thema eröffnet von: episqaure
Lineare Optimierung, simpler Algorithmus  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-09-17
episqaure
 

Hallo,

ich habe eine Frage zu einem simplen Algorithmus zur Lösung von LPs.


Seien die Nebenbedingungen durch $\{x \mid Ax  \leq b, x \geq 0 \}$ gegeben und $rank(A) = m$.

Man weiß:
(1) Gibt es eine zulässige Lösung, dann gibt es endliche viele Ecken.
(2) Falls das LP eine Optimallösung hat, so gibt es eine Ecke welche Optimallösung ist.
(3) Löst man $A'x = b, x \geq 0 $, für jede Matrix A', welche  aus m Unterspalten von $A$ besteht, erhalten wir alle Ecken.

Woher weiß ich aber nun, dass ich die Optimallösung hab (d.h. dass es eine Optimallösung gibt)?

Sobald das duale Programm auch eine zulässige Lösung hat, weiß man ja dass es auch Optimallösungen gibt.


Ich könnte mir die beste Ecke (in Bezug auf die Zielfunktion) des primalen Problems nehmen und müsste also nur noch eine duale Lösung finden.

Habe ich eine Optimallösung gefunden, dann liefert mir der Satz vom komplementären Schlupf, welche Ungleichungen im dualen Problem durch  Gleichheitsbedingungen ersetzt werden müssen, die dann für eine Optimallösung des dualen Programms gelten.

Finde ich also ein $y$ des dualen Programms, welche den Bedingungen des komplementären Schlupfs entspricht, habe ich die optimale duale Lösung gefunden. Damit weiß ich dass die Ecke optimal war.


Wie aber würde ich jetzt (ohne Simplex algorithmus oder öhnlichem) das duale Problem lösen können ? Im Allgemeinen werden im dualen Problem doch immer noch Ungleichungen übrig bleiben, so dass das Lösen des dualen Problems schwierig sein könnte, richtig?


Stochastik und Statistik
Universität/Hochschule 
Thema eröffnet von: episqaure
MAP Problem  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-08-26
episqaure
 

Hallo,

ich habe eine Frage wie man ein Wahrscheinlichkeitsmaß richtig definiert.

In der Arbeit wird ein MAP Problem definiert (Es sollen in einem Video Trajektorien berechnet werden). Dabei verstehe ich nicht, warum das Wahrscheinlichkeitsmaß wie angegeben definiert werden kann.

Ich fasse es mal zusammen:

Wir betrachten eine Sequenz bestehend aus $T$ Bildern.

Für $t =1,\ldots,T$, bezeichnet $X_{t} \subset \mathbb{R}^{n}$ eine endliche Menge (alle Detektionen zum Zeitpunkt $t$).
$X = \cup_{t = 1}^{T} X_{t}$ sind alle Detektionen.

$T \subset X$ heißt Trajektorie, falls zu jedem Zeitpunkt maximal eine Detektion verwendet wird: $|T \cap X_{t}| \leq 1$, für alle $t = 1,\ldots, T$.

Es sind nun die  wahrscheinlichsten Trajektorien gesucht, gegeben den Detektionen:

$\begin{align}
\mathcal{T}^{\star} &= \arg \max_{\mathcal{T}}P(\mathcal{T} \mid X) \\
&= \arg \max_{\mathcal{T}}P(X \mid \mathcal{T})P(\mathcal{T}) \\
&= \arg \max_{\mathcal{T}} \prod_{i} P(\mathbf{x}_{i} \mid \mathcal{T})P(\mathcal{T}) \\
\end{align}$

Dabei ist $\mathcal{T}$ eine Menge von Trajektorien, und das Maximum wird berechnet über alle möglichen Trajektorien.  Der Schritt von (2) zu (3) ist unter der Annahme der bedingten Unabhängigkeit.

In der Arbeit wird  nun modeliert dass
$\begin{align}P(\mathbf{x}_{i} \mid \mathcal{T}) = \begin{cases} 1 - \beta_{i}, &\exists T \in \mathcal{T}: \mathbf{x}_{i} \in T \\
\beta_{i} & \text{otherwise.}
\end{cases}\end{align}
$


Nun zu meinen konkreten Fragen:

1,) $P(\mathbf{x}_{i} \mid \mathcal{T})$ soll die Wahrscheinlichkeit modelieren, dass $\mathbf{x}_{i}$ eine korrekte Detektion eines Objekts ist, also kein falsch-positiv.
Wenn ich jetzt einen Wahrscheinlichkeitsraum $(\Omega,\epsilon,P)$ für die Observationen und Trajektorien habe, $\Omega$ endlich annehme,
und $\beta_{1} = \beta_{2} = \beta_{3} = 0.5$ setze, dann gilt doch für $\mathcal{T} = \{ \{\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3}\} \}$
dass $1.5 = P(\mathbf{x}_{1} \mid \mathcal{T})+P(\mathbf{x}_{2} \mid \mathcal{T})+P(\mathbf{x}_{3} \mid \mathcal{T}) \leq \sum_{\mathbf{x}_{i} \in \Omega} P(\mathbf{x}_{i} \mid \mathcal{T}) = P(\Omega \mid \mathcal{T}) = 1$

Und das kann ja nicht sein.

Wie kann man das ganze also richtig interpretieren? Denn das $P$ in  $P(\mathbf{x}_{i} \mid \mathcal{T})$ sollte doch auf dem gleichen Wahrscheinlichkeitsraum definiert sein wie $P(\mathcal{T} \mid X)$.


2.) Was ist eigentlich der zugehöriger Wahrscheinlichkeitsraum $(\Omega,\epsilon,P)$ bzw was sind die Ereignisse ?

Wenn $\Omega$ die Menge aller möglichen Observationen ist dann ist damit $X \subset \Omega$ ein Ereignis. Insbesondere ist auch eine Trajektorie ein Ereignis. Allerdings ist $\mathcal{T}$ eine Menge von Trajektorien, und damit $\mathcal{T} \not \subset \Omega$. Genauer $\mathcal{T} \in  \mathrm{IP}(\mathrm{IP}(\Omega))$, wobei $\mathrm{IP}(A)$ die Potenzmenge von $A$ bezeichnen soll. Das passt also auch nicht zusammen.


3.) In der Arbeit wird $P(\mathbf{x}_{i} \mid \mathcal{T})$ als Likelihood Funktion bezeichnet. Demnach wäre ist es kein Wahrscheinlichkeitsmaß.
Aber kann ich einfach das Wahrscheinlichkeitsmaß durch die Likelihood-Funktion ersetzen?

Stochastik und Statistik
Universität/Hochschule 
Thema eröffnet von: episqaure
Definition deterministische Abbildung  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-08-26
episqaure
 

Hallo,

im Buch  Foundation on Machine Learning wird eine Menge $\mathcal{X}$ betrachtet (Sample Raum), sowie ein zugehöriger Labelraum $\mathcal{Y}$.

In supervised learning  wird meißt  eine Abbildung $c:  \mathcal{X} \rightarrow \mathcal{Y}$ betrachtet, welche approximiert werden soll.

Wir betrachten nun einen Wahrscheinlichkeitsraum $(\mathcal{X},\Sigma,P)$.
Manchmal kann man die labels nicht deterministisch angeben (Beispiel: aus Farbe, Höhe, maximale Geschwindigkeit eines Autos soll die Auto-Marke gefunden werden. Dann gibt es zu zu einem Sample $x \in \mathcal{X}$ mehrere mögliche Labels, und man betracht die Verteilung.)

Ebenso wird es in Wikipedia betrachtet.

Daher nehmen wir also an, dass es eine Wahrscheinlichkeitsverteilung $P_{\mathrm{Verbund}}(x,y)$ auf $\mathcal{X} \times \mathcal{Y}$ gibt.

Meine Frage ist nun, wie kommt man vom allgemeinen Fall (mit den Labels als Zufallsvariable) zum Fall, dass die Labels durch eine Abbildung deterministisch beschrieben werden können.

Im Buch Foundation on Machine Learning steht für den deterministischen Fall,  dass man annimmt, dass es eine messbare Abbildung $f:\mathcal{X} \rightarrow \mathcal{Y}$ gibt, welche jedem Punkt $x \in \mathcal{X}$ mit Wahrscheinlichkeit $1$ ein Label $y \in \mathcal{Y}$ eindeutig zuordnet.


Wie kann man das mathematisch ausdrücken ?
Heißt das übersetzt:

$\forall x \in \mathcal{X} \exists! y \in \mathcal{Y}: P(y|x) = 1$ und $f(x):= \arg \max_{y} P(y \mid x)$.


Hat jemand eine Idee wie das genau zu verstehen ist?

Mehrdim. Differentialrechnung
Universität/Hochschule 
Thema eröffnet von: episqaure
Höherdimensionale Ableitung im Produktraum und im Matrizenraum  
Beitrag No.2 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2016-10-14
episqaure
 

Danke für die Antwort.

Die verallgemeinerte Definition für einen endlich-dim Vektorraum V ist doch
fed-Code einblenden
Wie zeige ich dann, dass die entsprechende Abbildung auf dem IR^n differenzierbar ist ?

Weil V endlich dimensional ist, kann ich
fed-Code einblenden
Hier weiß ich jetzt nicht weiter.

Ich hatte mich in dem Beispiel vertippt,
gemeint war

fed-Code einblenden
Wie kann mir das Differential berechnen ? (Ohne meinen Weg zu gehen)

Mehrdim. Differentialrechnung
Universität/Hochschule 
Thema eröffnet von: episqaure
Höherdimensionale Ableitung im Produktraum und im Matrizenraum  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2016-10-13
episqaure
 

fed-Code einblenden


Matrizenrechnung
Universität/Hochschule 
Thema eröffnet von: episqaure
Ausdrücken mittels Laplace-Matrix  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2015-03-15
episqaure
 

Hallo ich hab hier einen Funktion, welchen ich mittels der Laplace-Matrix beschreiben will. Irgendwo habe ich mich glaube ich verrechnet. Kann vielleicht jemand drüber schauen und mir einen Tipp geben.


Danke :)

fed-Code einblenden

Numerik & Optimierung
Universität/Hochschule 
Thema eröffnet von: episqaure
Dantzig-Wolfe-Zerlegung und ganzzahlige lineare Optimierung  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2014-10-28
episqaure
 

Hallo,

ich frage mich gerade wie im am besten ein ganzzahliges lineares Problem mittels Dantzig-Wolfe Zerlegung angehen kann.

Für den nicht-diskreten Fall betrachhte ich ja folgendes:

fed-Code einblenden

Das Master LP welches wir dann zu lösen haben ist:
fed-Code einblenden

Das zu lösende Subproblem ist:

fed-Code einblenden

Der Simplex-Algorithmus liefert zum dann immer ein Extrempunkt als optimalen Punkt (allerdings ist nicht jeder optimale Punkt von X^k ein Extrempunkt, richtig ? )



Wie geht man nun vor, wenn man ein ganzzahliges LP hat.

Man kann natürlich erstmal das relaxiert LP auf diese Weise lösen, bekommt damit eine untere Schranke fürs  ILP. Man kann dann sicher branch-and-bound verwenden um das ILP anzugehen.


Kann man aber auch direkt in der Dantzig-Wolfe Zerlegung ILP s lösen ?

D.h.

fed-Code einblenden

Entsprechend wird das Subproblem nur noch über der diskrete Menge X^k berechnet.




Kann man das so machen ?



Numerik & Optimierung
Universität/Hochschule 
Thema eröffnet von: episqaure
Column generation  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2014-10-27
episqaure
 

Hallo ,

ich habe ein paar Verständnisfragen zur Column Generation, wobei ich nach dem Skript  INTEGER PROGRAMMING LECTURE NOTES gehe.

Der Grundansatz ist der folgende:


fed-Code einblenden

Dazu habe ich nun ein paar Fragen:

(1) Wie genau bestimme ich die duale Variable u ? Wäre x optimale Lösung, dann kann ich ja den Satz vom komplementären Schlupf nutzen um u zu berechen. Da x aber noch nicht optimal ist, ist mir gar nicht klar, wie ich nun u berechnen kann.
(2) Was ist die Idee dahinter, einen Index zu finden, bei dem eine Bedinung des dualen LPs "maximal nicht erfüllt" ist ?
(3) mit a_k ist doch hier der k-te Spaltenvektor von A gemeint, richtig ?
(4) Kann ich beim Basisaustausch die Variable i beliebig wählen ?


Auf Seite 17-18 wird ein Beispiel angegeben.

Das lineare LP sieht dabei wie folgt aus:

fed-Code einblenden

Nun wird ein "Subproblem" definiert als:

fed-Code einblenden


Dabei ist fed-Code einblenden


(5) Auch hier ist mir nicht klar, wie genau man diesen dualen Wert berechnet (es geht hier ja darum nicht das ursprüngliche LP zu lösen sondern mittels des Subproblems das LP zu lösen).

(6) Wie kommt man überhaupt auf diese Zielfunktion ? Wenn ich es richtig verstehe, geht es doch darum die reduzierten Kosten zu berechnen.

Dann hätte ich aber sowas wie:

fed-Code einblenden

Das ganze zielt dann auf den column generation algorithmus ab:

Dazu wird als initialisierung die folgende Menge betrachtet:

fed-Code einblenden

Wenn ich nun nach jeder Iteration das Subproblem löse und die Spaltenmenge J erweitere. Wie kann ich dann effizient das LP lösen ?


Vielen Dank

 [Anzahl der Suchergebnisse: 13]
Link auf dieses Suchergebnis hier

 
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 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]

used time 0.065447