Category Archives: Maths

Optimisation et dualité

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

où on s’intéresse à maximiser la fonction dite objectif.

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).

Multiplication des pains et risk management


Pour continuer un peu mes élucubrations bibliques, après Jonas et la baleine (ici), je vais rebondir sur la multiplication des pains*. Hier soir je traînais sur le (très bon) blog http://eljjdx.canalblog.com/ (alias Choux romanesco, Vache qui rit et intégrales curvilignes) et j’ai dévoré l’article sur c’est mon choix, qui revenait sur le “paradoxe” de Stefan Banach et Alfred Tarski.
Ce paradoxe dit simplement qu’
il est possible de couper une boule de mathbb R^3 en un nombre fini de morceaux et de réassembler ces morceaux pour former deux boules identiques à la première. C’est un résultat purement mathématique, qui n’a aucun sens physique (ou tout du moins en physique classique, où “rien ne se perd, rien ne se crée, tout se transforme” selon la maxime attribuée – injustement – à Lavoisier car on peut la retrouver chez le philosophe présocratique Anaxagore de Clazomènes).

Ce résultat repose sur le concept d’équidécomposabilité: deux ensembles sont donc équidécomposables si on peut couper le premier en morceaux et reconstruire le deuxième simplement en déplaçant les morceaux (c’est-à-dire en leur appliquant une isométrie). Bref, on joue au puzzle. Et pour revenir à notre problème, un ensemble est dédoublable s’il est équidécomposable à une moitié de lui-même. L’autre point important dans le paradoxe est l’idée de volume (et donc de mesure). Si on veut mesurer un intervalle, on prend sa longueur et si on a un ensemble en plusieurs morceaux, on prend la somme de la longueur de chacun des morceaux.

Et le paradoxe affirme qu’on peut construire des ensembles suffisamment tordus et bizarres pour qu’on ne puisse pas les mesurer, c’est-à-dire qu’on ne peut pas leur associer un volume sans violer les deux propriétés évoquées plus haut. Pour reprendre une image évoqué par wikipedia, “le paradoxe affirme que l’on peut multiplier les petits pois ou transformer une grenouille en quelque chose de plus gros que le bœuf dès l’instant qu’on passe par une étape où elle est coupée en morceaux non mesurables, où le volume perd son sens. Par la suite, on peut réassembler ces morceaux en un objet « plus gros » sans avoir à dire que la grenouille et le bœuf ont le même volume puisque le volume du résultat n’est pas la somme des volumes des morceaux.

Pour ceux qui veulent des compléments mathématiques, il y a un article ici ou , par exemple.

Mais si je parle de Jésus de Nazareth et de paradoxes mathématiques, c’est principalement pour revenir à l’interprétation (très intéressante qu’en donne Paul Embrechts, ici). Paul en avait parlé à plusieurs reprises dans différents exposés (par exemple ici, à partir du slide 29). Je reprendrais plutôt la version en français des slides qu’il avait présenté à session plénière à Ottawa l’été dernier (ici),

dont l’interprétation financière est la suivante,

Peut-être est-ce encore plus clair en anglais,

Autrement dit les financiers ont réussi le miracle de mettre en pratique le théorème de Banach et Tarski, à savoir la multiplication des risques à l’infini….

 

* si je reprends l’évangile selon Marc,Et il leur dit: Combien avez-vous de pains? Allez voir. Ils s’en assurèrent, et répondirent: Cinq, et deux poissons. Il prit les cinq pains et les deux poissons et, levant les yeux vers le ciel, il rendit grâces. Puis, il rompit les pains, et les donna aux disciples, afin qu’ils les distribuassent à la foule. Il partagea aussi les deux poissons entre tous. Tous mangèrent et furent rassasiés, et l’on emporta douze paniers pleins de morceaux de pain et de ce qui restait des poissons. Ceux qui avaient mangé les pains étaient cinq mille hommes.

[30/03/2009] Juste pour poursuivre dans mes élucubrations bibliques, je voulais juste mettre un lien (ici), voire deux (), pour une lecture assez orientée théorie des jeux du sacrifice de Salomon  (ou du “jugement de Salomon”, rappelé ici). Des billets plus anciens parle de cette lecture (ici, ou ) ou mieux encore, le chapitre de John Moore, téléchargeable ici.


Hasard et uniformité, le paradoxe des enveloppes

Suite au billet de ce matin sur la loi de Benford, et sur l’erreur commune consistant à assimiler hasard et uniformité, Mathieu Rosenbaum m’a rappelé un petit paradoxe que je donnais quand je faisais la formation au concours Administrateur de l’INSEE. C’est parfois appelé le paradoxe des deux enveloppes: “Deux enveloppes contiennent chacune un chèque. On sait que l’un des chèques porte un montant double de l’autre. Le candidat choisit une des enveloppes. On lui donne la possibilité d’ouvrir l’enveloppe et de regarde le chèque, puis on lui demande s’il souhaite changer d’enveloppe. Que fait-il ?“.

Essayons de raisonner…Supposons qu’il tombe sur un chèque d’un montant X en ouvrant. Il y a deux cas possibles :

  • une chance sur deux que l’autre enveloppe contienne un chèque deux fois plus important (donc de valeur 2X);
  • une chance sur deux que l’autre enveloppe contienne un chèque deux fois plus petit (donc de valeur X/2).

L’espérance de gain (si on oublie l’utilité et les aspects économiques du problème) si on change d’enveloppe paraît donc être 0,5 * 2X + 0,5 * X/ 2, soit 1,25X, qui est (strictement) supérieur à X. Il faudrait donc à tout coup changer d’enveloppe. Moralité, quel que soit le montant, on a toujours intérêt à changer…. “Étonnant, non ?“. Il était d’ailleurs inutile de regarder le montant… et tant qu’à faire, si la stratégie optimale est de toujours changer d’enveloppe, pourquoi ne pas l’avoir fait plus tôt… Dès qu’on veut prendre une enveloppe, il faut prendre l’autre… enfin non, l’autre, enfin,…. bref, que fait-on ?

Il y a plein d’explications de ce paradoxe, ici par exemple. Personnellement, je retiendrais celle qui est liée à ce que je racontais sur la loi de Benford… Quand on fait le calcul des probabilités, prendre 1/2 et 1/2, c’est suppose que P(2X)=P(X/2)… et ce quel que soit X… autrement dit, on prend une loi uniforme sur l’ensemble des réels positifs (ou des entiers positifs si on suppose que le chèque est un compte rond). Mais une telle mesure de probabilité n’existe pas…

[20/03/2009] Sur le paradoxe des enveloppes et plusieurs autres “phénomènes curieux en probabilités et statistiques” je renvoie vers un cours article de Michel Emery, ici.