Une preuve intuitive / informelle pour LP Duality?

Quelle serait une bonne preuve informelle / intuitive pour «toucher le point» de la dualité LP? Comment montrer au mieux que la fonction objectif minimisée est bien le minimum avec une manière intuitive de comprendre la limite?

La façon dont on m'a enseigné la dualité n'a conduit qu'à une seule compréhension qui, j'en suis sûr, est partagée par BEAUCOUP de personnes que je connais: pour chaque problème de minimisation correspondant, il existe un problème de maximisation équivalent qui peut être dérivé en inversant les contraintes d'inégalité. Période. Cette «conclusion» de la dualité est ce qui semble coller mais pas «pourquoi en est-il ainsi» (c'est-à-dire comment / pourquoi y a-t-il une limite à la solution optimale).

Existe-t-il un moyen de jouer avec les inégalités juste pour «montrer» la borne inférieure / supérieure sur l'optimum qui pourrait être une motivation pour la preuve?

J'ai parcouru le livre de Chvatal ainsi que quelques autres, mais je n'ai rien trouvé qui puisse être compris par les nobles absolus de LP. Le plus proche que j'ai obtenu provenait du livre de Vazirani sur les algorithmes, où il parle de `` multiplier les inégalités avec des nombres magiques qui montrent la limite '' - je ne sais pas comment reproduire l'effet pour un LP arbitraire.

linear-programming primal-dual Doctorat
la source

Dans cette réponse math.SE, je passe par un exemple étape par étape d'où le dual vient - et pourquoi - pour un problème qui a la plupart des différentes possibilités qui peuvent survenir avec un LP. Peut-être que cela peut aider?

Mike Spivey

Je ne sais pas pourquoi vous pensez que l'argument de Vazirani ne fonctionne pas pour un LP général. Personnellement, j'aime le mieux cette explication.

Suresh Venkat

Vous posez des questions sur la dualité faible ou la dualité forte?

Tsuyoshi Ito du

Vous pouvez obtenir une intuition géométrique en visualisant (en 2d, par exemple) ce que signifie prendre une combinaison linéaire de contraintes. Par exemple, tracez les contraintes

x \leq 1

$x \le 1$ et

y \leq 1

$y \le 1$ dans le plan. Les combinaisons linéaires de ces contraintes vous donnent

a x + b y \leq a + b

$ax + by \le a + b$ pour tout

a, b \geq 0

$a,b \ge 0$ . Dessinez ceci pour le voir. Généralement, une combinaison linéaire de contraintes vous donne les demi-espaces de support des polyèdres. Maintenant, demandez-vous, pourquoi est-ce que l'un de ces demi-espaces de soutien suffit toujours, à lui seul, à donner une limite sur le coût? Si vous le voyez, c'est une forte dualité.

Neal Young

@MikeSpivey - J'aimerais que votre commentaire soit une réponse :)

PhD

Réponses:

Selon le souhait de l'OP, voici la réponse math.SE à laquelle je renvoie dans mon commentaire ci-dessus.

Peut-être que cela vaut la peine de parler d'où vient le dual sur un exemple de problème. Cela prendra un certain temps, mais j'espère que le double ne semblera pas si mystérieux lorsque nous aurons terminé.

Supposons que vous ayez un problème primaire comme suit.

P r i m a l = {\begin{matrix} max 5 x_{1} - 6 x_{2} \\ s . t . 2 x_{1} - x_{2} = 1 \\ x_{1} + 3 x_{2} \leq 9 \\ x_{1} \geq 0 \end{matrix}}

$Primal =\begin{Bmatrix} \max \ \ \ \ 5x_1 - 6x_2 \\ \ \ \ s.t. \ \ \ \ 2x_1 -x_2 = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\ \ \ \ \ x_1 \geq 0\\ \end{Bmatrix}$

Supposons maintenant que nous voulions utiliser les contraintes du primal comme moyen de trouver une limite supérieure sur la valeur optimale du primal. Si nous multiplions la première contrainte par

, la deuxième contrainte par

et les additionnons ensemble, nous obtenons

pour le côté gauche et

pour le côté droit. Comme la première contrainte est une égalité et la seconde une inégalité, cela implique

9

$9$

1

$1$

9 (2 x_{1} - x_{2}) + 1 (x_{1} + 3 x_{2})

$9(2x_1 - x_2) + 1(x_1 +3 x_2)$

9 (1) + 1 (9)

$9(1) + 1(9)$

Mais puisque

, il est également vrai que

, et donc

Par conséquent, ,

est une limite supérieure de la valeur optimale du problème primal.

19 x_{1} - 6 x_{2} \leq 18.

$19x_1 - 6x_2 \leq 18.$

x_{1} \geq 0

$x_1 \geq 0$

5 x_{1} \leq 19 x_{1}

$5x_1 \leq 19x_1$

5 x_{1} - 6 x_{2} \leq 19 x_{1} - 6 x_{2} \leq 18.

$5x_1 - 6x_2 \leq 19x_1 - 6x_2 \leq 18.$

18

$18$

$9$ $1$ $y_1$ $y_2$

5 x_{1} - 6 x_{2} \leq y_{1} (2 x_{1} - x_{2}) + y_{2} (x_{1} + 3 x_{2}) \leq y_{1} (1) + y_{2} (9) .

$5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9).$

$y_1$ $y_2$

$5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2)$

$x_1$ $x_2$ $x_1$ $5$ $5$ $x_1 \geq 0$ $5$ $x_1$ $2y_1 + y_2 \geq 5$

$x_2$ $x_2$ $-6$ $x_2$ $-6$ $x_2$ $-6$ $x_2$ $x_2$ . $-y_1 + 3y_2 = -6$

La seconde inégalité :

y_{1} (2 x_{1} - x_{2}) + y_{2} (x_{1} + 3 x_{2}) \leq y_{1} (1) + y_{2} (9)

$y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9)$

$y_1$ $y_2$ $y_1$ $y_1$ $y_1$ $y_2$ $y_2$ $y_2 \geq 0$

$y_1 + 9y_2$

$y_1$ $y_2$

\begin{aligned} Minimize y_{1} + 9 y_{2} \\ subject to 2 y_{1} + y_{2} & \geq 5 \\ - y_{1} + 3 y_{2} & = - 6 \\ y_{2} & \geq 0. \end{aligned}

$\begin{align*} \text{Minimize }\:\:\:\:\: y_1 + 9y_2& \\ \text{subject to }\:\:\:\:\: 2y_1 + y_2& \geq 5 \\ -y_1 + 3y_2& = -6\\ y_2 & \geq 0. \end{align*}$

Et c'est le double.

Il vaut probablement la peine de résumer les implications de cet argument pour toutes les formes possibles du primal et du dual. Le tableau suivant est extrait de p. 214 de Introduction à la recherche opérationnelle , 8e édition, par Hillier et Lieberman. Ils appellent cela la méthode SOB, où SOB signifie Sensible, Odd ou Bizarre, selon la probabilité que l'on trouve cette contrainte particulière ou restriction variable dans un problème de maximisation ou de minimisation.

             Primal Problem                           Dual Problem
             (or Dual Problem)                        (or Primal Problem)

             Maximization                             Minimization

Sensible     <= constraint            paired with     nonnegative variable
Odd          =  constraint            paired with     unconstrained variable
Bizarre      >= constraint            paired with     nonpositive variable

Sensible     nonnegative variable     paired with     >= constraint
Odd          unconstrained variable   paired with     = constraint
Bizarre      nonpositive variable     paired with     <= constraint

Mike Spivey
la source

$x$ $x = B$ $x$ $x \leq C$ $C$ $B \leq \min C$ $B$ $B = \min C$ $B$ $B$

$f$ $f$ $S,O$ $f(S) \geq (1-1/e) f(O)$ $f$ $f$ $f(O) = 1$ $f(S)$ $\min f(S) = 1-1/e$ $1-1/e$ $f(S) \geq 1-1/e$

Cela laisse ouverte la question de savoir pourquoi une forte dualité tient réellement. Il existe deux preuves de ce fait pour la programmation linéaire, l'une impliquant l'algorithme simplex, l'autre le lemme de Farkas. Le lemme de Farkas est probablement la façon «correcte» de comprendre la situation, réduisant tout à un fait géométrique intuitif. Cependant, j'avoue que cette intuition me dépasse.

Dans des situations plus générales (disons une programmation semi-définie), vous devez utiliser les conditions plus générales de Karush-Kuhn-Tucker (une forme de multiplicateurs de Lagrange) pour obtenir le double et les conditions d'une forte dualité. Ceci est traité dans les textes sur l'optimisation non linéaire ou convexe.

Yuval Filmus
la source