Kurzer und geschickter Beweis des starken Dualitätssatzes für die lineare Programmierung

Betrachten Sie die linearen Programme

\begin{array}{ccc} P r i m a l : & A \vec{x} \leq \vec{b} & max {\vec{c}}^{T} \vec{x} \end{array}

$\begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array}$

\begin{array}{ccc} D u a l : & \vec{c} \leq {\vec{y}}^{T} A & min {\vec{y}}^{T} \vec{b} \end{array}

$\begin{array}{|ccc|} \hline Dual: & \vec{c} \leq \vec{y}^TA \hspace{.5cm} & \min \vec{y}^T\vec{b} \\ \hline \end{array}$

Der schwache Dualitätssatz besagt, dass, wenn und die Bedingungen erfüllen, . Es hat einen kurzen und glatten Beweis unter Verwendung der linearen Algebra: . $\vec{x}$ $\vec{y}$ $\vec{c}^T\vec{x} \leq \vec{y}^T\vec{b}$ $\vec{c}^T\vec{x} \leq \vec{y}^T A \vec{x} \leq \vec{y}^T\vec{b}$

Der Satz der starken Dualität besagt, dass wenn eine optimale Lösung für das Primäre ist, es gibt, eine Lösung für das Duale und . $\vec{x}$ $\vec{y}$ $\vec{c}^T\vec{x} = \vec{y}^T\vec{b}$

Gibt es einen ähnlich kurzen und raffinierten Beweis für den starken Dualitätssatz?

algorithms reference-request linear-programming linear-algebra duality Kaveh
quelle

Kapitel 4 des MIT-Online-Kurses web.mit.edu/15.053/www von Bradley, Hax und Magnanti liefert einen relativ kurzen Beweis in dieser Richtung. Ist es das, wonach du suchst?

Cody

@cody, nun, es scheint im Wesentlichen dasselbe zu sein wie das in CLRS. Es kann in Ordnung sein, wenn Sie es in einer raffinierten linearen Algebra ausdrücken können (dh ohne Summen).

Kaveh

Es scheint, dass das, was ich wollte, wahrscheinlich nicht möglich ist. Die Farkas nutzen die Geschlossenheit des Raumes, was bedeutet, dass es wahrscheinlich keinen reinen linearen Algebra-Beweis gibt.

Kaveh

Der Versuch, selbst etwas zu finden, das nicht zu umständlich ist, um es meinen Schülern zu zeigen (damit sie nicht nur eine starke Dualität im Glauben haben müssen), und das meiste, was mir begegnet ist, ist eher in der Kategorie zu umständlich. Ich habe gerade ein Argument in Notizen einer Klasse von Dan Spielman gefunden, das ziemlich kurz und scheinbar einfach ist. Sie sind sich nicht sicher, ob es eine gewisse Komplexität verbirgt oder ob etwas fehlt? (Ich habe es noch nicht gründlich genug untersucht, um es zu sagen.) Cs.yale.edu/homes/spielman/BAP/lect12.pdf

Magnus Lie Hetland

Ah, ich denke, ein zentraler Punkt ist die geometrische Interpretation in der vorherigen Vorlesung, die uns zurück zur Simplex- Beweisfamilie führt

Magnus Lie Hetland

Antworten:

Wahrscheinlich nicht. Hier ist ein konzeptionelles Argument basierend auf

Farkas Lemma : Genau eine der folgenden Alternativen hat eine Lösung:

$Ax \le b$ und $x \ge 0$

$y^TA\ge 0$ und $y^Tb < 0$

Nun sei der optimale Zielwert des Primalen. Sei beliebig. Let zu mit einer zusätzlichen als die letzten Zeile. Lassen b‘sein mit einem zusätzlichen als letzten Wert. $\delta$ $\epsilon > 0$ $A'$ $A$ $-c^T$ $b'$ $b$ $-\delta - \epsilon$

Das System hat keine Lösung. Bei Farkas gibt es ein so dass: $A'x'\le b'$ $y' = (y,\alpha)$

$y^TA\ge \alpha c$ und . $y^Tb < \alpha (\delta + \epsilon)$

Beachten Sie, dass wir uns bei in der anderen Alternative von Farkas befinden. Daher . $\epsilon = 0$ $\alpha > 0$

Skaliere so, dass . ist doppelt machbar. Die schwache Dualität impliziert . $y'$ $\alpha = 1$ $y$ $\delta \le y^Tb < \delta + \epsilon$

Louis
quelle

Ich denke, dies ist der Beweis in Jeff Ericksons Vorlesungsunterlagen . Ich suche etwas, das das Epsilon-Zeug vermeidet (wie reine lineare Algebra).

Kaveh

Was JeffE hat, ist etwas anders und es erklärt die Geometrie mehr. Wie auch immer, Sie werden nicht finden, was Sie wollen, in dem Sinne, dass die realisierbare Region ein Polyeder ist, kein linearer Raum, also muss irgendwann etwas davon Gebrauch machen. (Hier versteckt es sich in Farkas. Das Buch von Gärtner und Matoušek ist eine wirklich gute Referenz für dieses Zeug. Ich bin mir ziemlich sicher, dass dieser Beweis da ist.)

Louis