La notion de dualité est un peu utilisée à tort et à travers en optimisation, par exemple en gestion de portefeuille. Histoire de remettre les idées au clair, je voulais faire un court billet sur le sujet,

• cas de la programmation linéaire

Dans le cas de l’optimisation linéaire, on s’intéresse au problème d’optimisation suivant

où ici

.

On parlera alors de “problème primal“. La version duale (appelé “problème dual“) s’écrit alors tout simplement

et ici

.

Pour diverses raisons, il peut parfois être plus simple de résoudre le problème dual que le problème primal. Et l’intérêt de cette réécriture est que les deux problèmes sont étroitement liés. En particulier, sous quelques hypothèses d’existence de solution, on a alors un résultat de la forme suivante (que l’on appelle parfois théorème de Minkowski-Farkas). Une solution au problème primal est optimale si et seulement si il existe une solution au problème dual vérifiant

.

Ce théorème est parfois abordé dans les cours sur la convexité… autrement dit, ce résultat doit être très liés à des propriétés de fonctions convexes, et c’est ce qu’on va voir ensuite… Je renvoie au livre de Yadolah Dodge d’Optimisation Appliquée (chapitre 7) pour ceux qui veulent des exemples.

• la dualité dans un cas plus général (mais convexe)

Cette dualité, qui permet de résoudre un problème d’optimisation parfois plus simple ne marche toutefois que sous certaines hypothèses. Considérons pour cela le problème relativement général suivant,

où toutes les fonctions sont supposées convexes, et on suppose de plus que est un ensemble convexe, compact. On parle alors de programme convexe (cf wiki). Ce problème est équivalent au problème suivant,

autrement dit, la résolution de ce problème se fait en passant par le Lagrangien,

Le principe de dualité consiste alors à permuter les min et les sup, et la version duale (le “problème dual“) s’écrit alors tout simplement

On peut montrer que cette fonction est alors une fonction concave. On alors le résultat suivant

• en programmation linéaire ou pour un programme convexe,

• pour un programme non-convexe,

Autrement dit, si l’on supprime l’hypothèse de convexité, alors les deux problèmes ne sont plus équivalents. Pour expliquer de manière heuristique l’avantage de l’optimisation sur des fonctions convexes, on peut considérer le dessin ci-dessous (emprunté sur http://convexoptimization.com/…),

où on voit clairement que minimiser f sous la contrainte de maximiser g est équivalent à permuter l’ordre de l’optimisation.

• la dualité dans un cas plus général non convexe

En fait, on peut montrer (ce sont des résultats montrés par Jean-Pierre Aubin et Ivar Ekeland en 1976, dans Applied nonlinear analysis) quelques résultats afin de contrôler l’écart entre les deux optimums,

Sous quelques conditions techniques, on peut alors majorer l’écart entre les solutions des deux problèmes,

en introduisant la distance entre la fonction à maximiser et son enveloppe convexe. Pour aller (beaucoup) plus loin, il existe un petit livre de Tyrrell Rockafellar sur ce sujet, conjugate duality and optimization. Je peux aussi renvoyer vers le site http://meboo.convexoptimization.com/ (et le livre associé, ici). Côté applications, elles sont nombreuses, en économie mais aussi en finance. En particulier, je renvoie à un papier que l’on avait fait avec Abder Oulidi sur l’optimisation de portefeuilles sous contraintes de VaR (ici). La VaR n’étant pas convexe, l’optimisation est un problème plus compliqué (d’où l’intérêt évoqué par certains de minimiser des mesures de risques convexes).