Preuve courte et lisse du théorème de la forte dualité pour la programmation linéaire

Considérez les programmes linéaires

\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}$

Le théorème de la dualité faible indique que si et satisfont aux contraintes alors . Il a une preuve courte et lisse utilisant l'algèbre linéaire: . $\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}$

Le fort théorème de la dualité déclare que si le $\vec{x}$ est une solution optimale pour le primal alors il y a $\vec{y}$ qui est une solution pour le dual et $\vec{c}^T\vec{x} = \vec{y}^T\vec{b}$ .

Existe-t-il une preuve similaire courte et lisse pour le théorème de la forte dualité?

algorithms reference-request linear-programming linear-algebra duality Kaveh
la source

Le chapitre 4 du cours en ligne du MIT web.mit.edu/15.053/www par Bradley, Hax et Magnanti fournit une preuve raisonnablement courte dans ce sens. C'est ce que vous cherchez?

cody

@cody, eh bien, il semble essentiellement le même que celui de CLRS. Cela peut être bien si vous pouvez l'exprimer de manière algèbre linéaire lisse (c'est-à-dire sans sommes).

Kaveh

Il semble que ce que je voulais n'est probablement pas possible. Les Farkas utilisent la fermeture de l'espace, ce qui signifie qu'il n'y a probablement pas de preuve d'algèbre linéaire pure.

Kaveh

Essayer de trouver moi-même quelque chose de pas trop lourd, de montrer à mes élèves (afin qu'ils n'aient pas à simplement prendre une forte dualité sur la foi), et la plupart de ce que j'ai rencontré est plus dans la catégorie trop lourde. Je viens de trouver un argument dans les notes d'une classe de Dan Spielman, qui est assez court et apparemment simple. Vous ne savez pas si cela cache une certaine complexité ou s'il manque quelque chose? (Je ne l' ai

Magnus Lie Hetland

Ah, je suppose qu'un point central est l'interprétation géométrique de la conférence précédente, qui nous ramène à la famille de preuves Simplex: cs.yale.edu/homes/spielman/BAP/lect11/lect11.pdf

Magnus Lie Hetland

Réponses:

Probablement pas. Voici un argument conceptuel basé sur

Lemme Farkas : Exactement l'une des alternatives suivantes a une solution:

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

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

Soit maintenant la valeur objective optimale du primal. Soit arbitraire. Soit un avec un supplémentaire comme dernière ligne. Supposons que soit avec une valeur supplémentaire comme dernière valeur. $\delta$ $\epsilon > 0$ $A'$ $A$ $-c^T$ $b'$ $b$ $-\delta - \epsilon$

Le système n'a pas de solution. Par Farkas, il y a un tel que: $A'x'\le b'$ $y' = (y,\alpha)$

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

Notez que si nous sommes dans l'autre alternative de Farkas. Par conséquent . $\epsilon = 0$ $\alpha > 0$

Mettez échelle telle sorte que . est double possible. La dualité faible implique . $y'$ $\alpha = 1$ $y$ $\delta \le y^Tb < \delta + \epsilon$

Louis
la source

Je pense que c'est la preuve dans les notes de cours de Jeff Erickson . Je cherche quelque chose qui évite les trucs epsilon (comme l'algèbre linéaire pure).

Kaveh

Ce que JeffE a est un peu différent, et cela explique davantage la géométrie. De toute façon, vous n'allez pas trouver ce que vous voulez, dans le sens où la région réalisable est un polyèdre, pas un espace linéaire, donc quelque chose devra éventuellement en faire usage. (Ici, il se cache à Farkas. Le livre de Gärtner et Matoušek est une très bonne référence pour ce genre de choses. Je suis sûr que cette preuve est là.)

Louis