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

10

Considérez les programmes linéaires

D u a l : cy T A

Primal:AxbmaxcTx
Dual:cyTAminyTb

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 {c} ^ T \ vec {x} \ leq \ vec {y} ^ TA \ vec {x} \ leq \ vec {y} ^ T \ vec {b } .y c Txy Tb c Txy TAxy TbxycTxyTbcTxyTAxyTb

Le fort théorème de la dualité déclare que si le x est une solution optimale pour le primal alors il y a y qui est une solution pour le dual et cTx=yTb .

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

Kaveh
la source
1
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:

3

Probablement pas. Voici un argument conceptuel basé sur

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

  1. x 0Axb etx0
  2. y T b < 0yTA0 etyTb<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.ϵ >δϵ>0AAcTbbδϵ

Le système n'a pas de solution. Par Farkas, il y a un tel que:Axby=(y,α)

yTAαc et .yTb<α(δ+ϵ)

Notez que si nous sommes dans l'autre alternative de Farkas. Par conséquent .ϵ=0α>0

Mettez échelle telle sorte que . est double possible. La dualité faible implique . α = 1 y δ y T b < δ + ϵyα=1yδyTb<δ+ϵ

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
2
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