Optimisation en Finance

Clément W. Royer

M2 MIAGE - Université Paris Dauphine-PSL

Version du 3 octobre 2022

C. W. Royer Optimisation en Finance MIAGE 22-23 1

Ressources utiles

Links
Page du cours :
[Link] croyer/[Link]
Transparents de cours (mis à jour régulièrement).

L’enseignant
Clément ROYER;
Maître de conférences à Dauphine depuis 2019;
Chercheur au LAMSADE en optimisation;
Email : [Link]@[Link]

C. W. Royer Optimisation en Finance MIAGE 22-23 2

Organisation

Emploi du temps
Par créneaux de 3h (8h30-11h45 ou 13h45-17h).
Premier bloc (mardis matins) 20/09, 27/09, 04/10, 11/10, 18/10;
Second bloc : 18/11 matin+après-midi, 22/11 matin.

C. W. Royer Optimisation en Finance MIAGE 22-23 3

Organisation

Emploi du temps
Par créneaux de 3h (8h30-11h45 ou 13h45-17h).
Premier bloc (mardis matins) 20/09, 27/09, 04/10, 11/10, 18/10;
Second bloc : 18/11 matin+après-midi, 22/11 matin.

Attendus
Ponctualité.
Participation.
Toute remarque est la bienvenue.

C. W. Royer Optimisation en Finance MIAGE 22-23 3

Évaluation

50% Examen + 50% Projet

Examen
13 décembre, 10h-12h.
Autorisé : Une feuille A4 recto-verso de notes manuscrites ou
imprimées.

Projet
Date de rendu : À venir.
Projet individuel.
Inspiré par les exercices et TP.

C. W. Royer Optimisation en Finance MIAGE 22-23 4

Optimisation en finance

Modèles
Modélisation : passer d’une problématique de finance à un problème
d’optimisation mathématique;
But : présenter les modèles les plus courants, et justifier leur
pertinence.

Utilisation
Résolution de problèmes d’optimisation.
Interprétation des résultats obtenus.

C. W. Royer Optimisation en Finance MIAGE 22-23 5

Décomposition prévue du cours

1 Bases de l’optimisation (modèles, outils mathématiques);

2 Programmation linéaire en finance;
3 Programmation quadratique en finance et gestion de portefeuille;
4 Programmation stochastique et problèmes de gestion de risque;
5 Optimisation robuste et applications en finance.

C. W. Royer Optimisation en Finance MIAGE 22-23 6

Table des matières

1 À propos du cours

2 Introduction

3 Bases d’optimisation
Notations et éléments mathématiques
Un problème d’optimisation

4 Programmation linéaire

C. W. Royer Optimisation en Finance MIAGE 22-23 7

Table des matières

1 À propos du cours

2 Introduction

3 Bases d’optimisation
Notations et éléments mathématiques
Un problème d’optimisation

4 Programmation linéaire

C. W. Royer Optimisation en Finance MIAGE 22-23 8

Notations

Cadre restreint
Optimisation sur des variables réelles;
En dimension finie;
On utilisera la structure d’espace classique.

Mes notations pour aujourd’hui

Scalaires : a, b, c, . . .
Vecteurs : a, b, c, . . .
Matrices : A, B, C , . . .
Ensembles : A, B, C, . . .

C. W. Royer Optimisation en Finance MIAGE 22-23 9

Algèbre linéaire

Rn : ensemble des vecteurs à n ≥ 1 coordonnées réelles;

Pour tous x ∈ Rn et i ∈ {1, . . . , n}, xi ∈ R est la i-ème coordonnée
de x : x = [xi ]1≤i≤n ;
 
x1
On représente x ∈ Rn en colonnes : x =  ... ;
 

xn
On utilise des vecteurs lignes comme “transposés” de vecteurs
colonnes : x T := [x1 · · · xn ];

C. W. Royer Optimisation en Finance MIAGE 22-23 10

Algèbre linéaire

Rn : ensemble des vecteurs à n ≥ 1 coordonnées réelles;

Pour tous x ∈ Rn et i ∈ {1, . . . , n}, xi ∈ R est la i-ème coordonnée
de x : x = [xi ]1≤i≤n ;
 
x1
On représente x ∈ Rn en colonnes : x =  ... ;
 

xn
On utilise des vecteurs lignes comme “transposés” de vecteurs
colonnes : x T := [x1 · · · xn ];

Opérations vectorielles
Addition dans Rn : x + z := [xi + zi ]1≤i≤n ;
Multiplication d’un vecteur de Rn par un réel : λx := [λxi ]1≤i≤n .

C. W. Royer Optimisation en Finance MIAGE 22-23 10

Algèbre linéaire (2)

Norme euclidienne sur Rn

La norme euclidienne (ou norme `2 ) d’un vecteur x ∈ Rn est donnée par
v
u n
uX
kxk := t xi2 .
i=1

Produit scalaire sur Rn

Pour tous x, z ∈ Rn , défini par
n
X
x T z := xi zi .
i=1

On a ainsi x T z = z T x et x T x = kxk2 .

C. W. Royer Optimisation en Finance MIAGE 22-23 11

Algèbre linéaire (3)

Matrices
Rn×m : matrices à n lignes et m colonnes;
Rn×1 ' Rn .

Matrice transposée
Soit A = [Aij ] ∈ Rn×m . La matrice transposée de A, notée AT , est la
matrice à d lignes et n colonnes telle que
 T
∀i = 1, . . . , n, ∀j = 1, . . . , m, A ij = Aji .

C. W. Royer Optimisation en Finance MIAGE 22-23 12

Algèbre linéaire (3)

Matrices
Rn×m : matrices à n lignes et m colonnes;
Rn×1 ' Rn .

Matrice transposée
Soit A = [Aij ] ∈ Rn×m . La matrice transposée de A, notée AT , est la
matrice à d lignes et n colonnes telle que
 T
∀i = 1, . . . , n, ∀j = 1, . . . , m, A ij = Aji .

Matrices carrées
AT ∈ Rn×n ;
A est dite symétrique si A = AT .

C. W. Royer Optimisation en Finance MIAGE 22-23 12

Algèbre linéaire (4)

Inversion et singularité
Une matrice A ∈ Rn×n est dite inversible s’il existe B ∈ Rn×, telle que
BA = AB = In , avec In matrice identité de Rn×n .
Dans ce cas, B est l’unique matrice vérifiant cette propriété : on
l’appelle l’inverse de la matrice A et on la note A−1 .

C. W. Royer Optimisation en Finance MIAGE 22-23 13

Algèbre linéaire (4)

Inversion et singularité
Une matrice A ∈ Rn×n est dite inversible s’il existe B ∈ Rn×, telle que
BA = AB = In , avec In matrice identité de Rn×n .
Dans ce cas, B est l’unique matrice vérifiant cette propriété : on
l’appelle l’inverse de la matrice A et on la note A−1 .
Une matrice A ∈ Rm×n est singulière s’il existe x ∈ Rn non nul tel que
Ax = 0.
Une matrice non singulière est dite de rang plein min{m, n}.

C. W. Royer Optimisation en Finance MIAGE 22-23 13

Algèbre linéaire (4)

Inversion et singularité
Une matrice A ∈ Rn×n est dite inversible s’il existe B ∈ Rn×, telle que
BA = AB = In , avec In matrice identité de Rn×n .
Dans ce cas, B est l’unique matrice vérifiant cette propriété : on
l’appelle l’inverse de la matrice A et on la note A−1 .
Une matrice A ∈ Rm×n est singulière s’il existe x ∈ Rn non nul tel que
Ax = 0.
Une matrice non singulière est dite de rang plein min{m, n}.

Caractère (semi)-défini positif

Une matrice symétrique A ∈ Rn×n est dite semi-définie positive si

∀v ∈ Rn , v T Av ≥ 0.

Elle est définie positive lorsque v T Av > 0 pour tout vecteur v non nul.

C. W. Royer Optimisation en Finance MIAGE 22-23 13

Références

De nombreuses notes de cours disponibles;

Annexes de nombreux ouvrages d’optimisation !

Mes recommandations
En français :
[Link] carlier/[Link]
En anglais :
[Link] (Chapitres 1-3)

C. W. Royer Optimisation en Finance MIAGE 22-23 14

Table des matières

1 À propos du cours

2 Introduction

3 Bases d’optimisation
Notations et éléments mathématiques
Un problème d’optimisation

4 Programmation linéaire

C. W. Royer Optimisation en Finance MIAGE 22-23 15

Optimisation ?

Recherche opérationnelle;
Prise de décision;
Sciences de la décision;
Programmation mathématique;
Optimisation mathématique.
⇒ Tous ces concepts peuvent correspondre à de l’optimisation.

C. W. Royer Optimisation en Finance MIAGE 22-23 16

Optimisation ?

Recherche opérationnelle;
Prise de décision;
Sciences de la décision;
Programmation mathématique;
Optimisation mathématique.
⇒ Tous ces concepts peuvent correspondre à de l’optimisation.

Ma définition
Le but de l’optimisation est de prendre la meilleure décision parmi un
ensemble de possibilités.

C. W. Royer Optimisation en Finance MIAGE 22-23 16

Formulation d’un problème d’optimisation

Un problème de minimisation sur n paramètres réels s’écrit sous la forme :

minimiser
n
f (x) s. c. x ∈ X
x∈R

x representé les variables de décision;

n est la dimension du problème (on prendra toujours n ≥ 1);
f (·) est la fonction objectif/de coût/de perte;
X est l’ensemble réalisable/admissible regroupant les contraintes sur
les variables de décision.

Maximiser f revient à minimiser −f .

C. W. Royer Optimisation en Finance MIAGE 22-23 17

Premières définitions

minimiser
n
f (x) s. c. x ∈ X
x∈R

x ∈ Rn est dit admissible ou réalisable si x ∈ X .

x ∗ ∈ Rn est une solution du problème si

x∗ ∈ X et f (x) ≥ f (x ∗ ) ∀x ∈ X .

L’ensemble des solutions du problème est noté

argmin {f (x) | x ∈ X } .
x∈Rn

La valeur optimale du problème est notée

min {f (x) | x ∈ X } .
x∈Rn

C. W. Royer Optimisation en Finance MIAGE 22-23 18

Premières définitions (2)

minimiser
n
f (x) s. c. x ∈ X
x∈R

Le problème est dit irréalisable si l’ensemble des contraintes est vide :

X = ∅. Dans ce cas, on a par convention

argmin {f (x) | x ∈ X } = ∅ et min {f (x) | x ∈ X } = +∞.

x∈Rn x∈Rn

Si X n’est pas vide, le problème est dit réalisable.

Le problème est dit non borné lorsque X est non vide mais que f
n’est pas minorée sur X . Dans ce cas, on note

argmin {f (x) | x ∈ X } = ∅ et min {f (x) | x ∈ X } = −∞.

x∈Rn x∈Rn

Pour un problème de minimisation (resp. de maximisation), on parlera

de problème non minoré (resp. non majoré).
C. W. Royer Optimisation en Finance MIAGE 22-23 19
Quels modèles d’optimisation ?

Idée principale : Les modèles les plus utilisés sont ceux dont on sait
calculer des solutions de manière efficace.

C. W. Royer Optimisation en Finance MIAGE 22-23 20

Quels modèles d’optimisation ?

Idée principale : Les modèles les plus utilisés sont ceux dont on sait
calculer des solutions de manière efficace.

Cas fondamental : Programmation convexe

Minimiser une fonction f convexe :

∀(x, y ) ∈ (Rn )2 , ∀α ∈ [0, 1], f (αx +(1−α)y ) ≤ αf (x)+(1−α)f (y )

Sous contraintes convexes :

∀(x, y ) ∈ X 2 , ∀α ∈ [0, 1], αx + (1 − α)y ∈ X .

En général, possible de calculer efficacement des solutions,

potentiellement pour des milliers de variables !

C. W. Royer Optimisation en Finance MIAGE 22-23 20

Quels modèles d’optimisation ? (2)

minimiser
n
f (x) s. c. x ∈ X .
x∈R

Programmation mixte
Certaines variables ne peuvent prendre que des valeurs entières
(dans Z).
Ces problèmes peuvent être résolus, parfois avec un fort coût de calcul.
La modélisation de ces problèmes, notamment via X , est
particulièrement importante.

C. W. Royer Optimisation en Finance MIAGE 22-23 21

Quels modèles d’optimisation ? (2)

minimiser
n
f (x) s. c. x ∈ X .
x∈R

Programmation mixte
Certaines variables ne peuvent prendre que des valeurs entières
(dans Z).
Ces problèmes peuvent être résolus, parfois avec un fort coût de calcul.
La modélisation de ces problèmes, notamment via X , est
particulièrement importante.

Programmation stochastique
Prend en compte l’incertitude sur le problème.
Pas toujours simple à résoudre, mais très souvent employée.

C. W. Royer Optimisation en Finance MIAGE 22-23 21

Trois approches en optimisation

Mathématique : Prouver l’existence de solutions, le côté bien posé

d’une formulation souvent complexe.
Logicielle : Programmer un algorithme pour résoudre une classe de
problèmes en pratique.
Numérique : Élaborer des algorithmes, établir des garanties
théoriques et valider leur implémentation.

C. W. Royer Optimisation en Finance MIAGE 22-23 22

Trois approches en optimisation

Mathématique : Prouver l’existence de solutions, le côté bien posé

d’une formulation souvent complexe.
Logicielle : Programmer un algorithme pour résoudre une classe de
problèmes en pratique.
Numérique : Élaborer des algorithmes, établir des garanties
théoriques et valider leur implémentation.

On traitera essentiellement des deux dernières catégories.

C. W. Royer Optimisation en Finance MIAGE 22-23 22

Résoudre un problème

Résolution
Théorique : On détermine des conditions vérifiées par la solution, voire
une formule explicite.

C. W. Royer Optimisation en Finance MIAGE 22-23 23

Résoudre un problème

Résolution
Théorique : On détermine des conditions vérifiées par la solution, voire
une formule explicite.
Numérique : On détermine une solution approchée, souvent avec un
certificat d’optimalité.

C. W. Royer Optimisation en Finance MIAGE 22-23 23

Résoudre un problème

Résolution
Théorique : On détermine des conditions vérifiées par la solution, voire
une formule explicite.
Numérique : On détermine une solution approchée, souvent avec un
certificat d’optimalité.

Exemples
Conditions d’optimalité;
Certificat de dualité.

C. W. Royer Optimisation en Finance MIAGE 22-23 23

Du côté machine

Langages typiques des optimiseurs

C/C++/Fortran (calcul à hautes performances)
Matlab/Octave, Python, Julia (interprétés).

C. W. Royer Optimisation en Finance MIAGE 22-23 24

Du côté machine

Langages typiques des optimiseurs

C/C++/Fortran (calcul à hautes performances)
Matlab/Octave, Python, Julia (interprétés).

Langages de modélisation
GAMS, AMPL, CVX, Pyomo sont génériques;
MATPOWER, PyTorch sont spécifiques à un domaine;
La plupart peuvent être interfacés avec les langages ci-dessus.

C. W. Royer Optimisation en Finance MIAGE 22-23 24

Langages/Logiciels pour ce cours

Microsoft Excel
Propriétaire;
Outil de base en finance et entreprise;
Dispose d’un solveur d’optimisation (non inclus dans la licence de
Dauphine...)

Package cvx
Développé par Stanford, bon en programmation convexe.
Version originelle sous MATLAB (outil propriétaire, mais dispose d’une
toolbox de finance très fournie);
Version Python : cvxpy.

C. W. Royer Optimisation en Finance MIAGE 22-23 25

De quels problèmes parle-t-on ?

Avertissement : Je ne suis pas un financier

Certains problèmes seront simplifiés.
D’autres correspondent à de véritables pratiques.

C. W. Royer Optimisation en Finance MIAGE 22-23 26

De quels problèmes parle-t-on ?

Avertissement : Je ne suis pas un financier

Certains problèmes seront simplifiés.
D’autres correspondent à de véritables pratiques.

Ex) Gestion de portefeuille

Cours dédié en MIAGE IF.
Ce qui nous intéresse : Problème d’optimisation associé, et bénéfices
de cette reformulation.

C. W. Royer Optimisation en Finance MIAGE 22-23 26

De quels problèmes parle-t-on ? (2)

Ex) Gestion des risques

Crucial en finance : une mauvaise gestion des risques conduit à des
catastrophes (Lehman Brothers, 2007-2008).
Règlementation : Niveaux de risques (contraintes).
Optimisation : Maximiser le retour sur investissement sous contraintes
sur les niveaux de risques.

C. W. Royer Optimisation en Finance MIAGE 22-23 27

De quels problèmes parle-t-on ? (2)

Ex) Gestion des risques

Crucial en finance : une mauvaise gestion des risques conduit à des
catastrophes (Lehman Brothers, 2007-2008).
Règlementation : Niveaux de risques (contraintes).
Optimisation : Maximiser le retour sur investissement sous contraintes
sur les niveaux de risques.

Ex) Gestion des actifs (assets) et des dettes (liabilities)

Rendement soumis à l’aléatoire;
Différents niveaux de modélisation.

C. W. Royer Optimisation en Finance MIAGE 22-23 27

Conclusions : Objectifs du cours

Comprendre les caractéristiques des modèles d’optimisation les plus

classiques en finance.
Connaître les grands principes derrière la résolution de ces modèles et
les informations à en tirer.
Étudier des exemples de problèmes en finance et leur modélisation via
des outils d’optimisation.

C. W. Royer Optimisation en Finance MIAGE 22-23 28

Références-clés

Optimization Methods in Finance, Second Edition, G. Cornuéjols, J.

Peña et R. Tütüncü, Cambridge University Press, 2018.
Convex Optimization, S. Boyd et L. Vandenberghe, Cambridge
University Press, 2004.

C. W. Royer Optimisation en Finance MIAGE 22-23 29

Table des matières

1 À propos du cours

2 Introduction

3 Bases d’optimisation

4 Programmation linéaire
Bases de la programmation linéaire
Solutions d’un programme linéaire
Algorithmes et logiciels pour la programmation linéaire

C. W. Royer Optimisation en Finance MIAGE 22-23 30

Table des matières

1 À propos du cours

2 Introduction

3 Bases d’optimisation

4 Programmation linéaire
Bases de la programmation linéaire
Solutions d’un programme linéaire
Algorithmes et logiciels pour la programmation linéaire

C. W. Royer Optimisation en Finance MIAGE 22-23 31

Programmation linéaire

Historique
Développé par George Dantzig dans les années 1960;
Fondement des mathématiques appliquées;
Outil de modélisation classique et populaire de par sa simplicité.

Définition
Un programme linéaire consiste à minimiser ou maximiser une fonction
linéaire des variables de décision sous la contrainte que ces variables
appartiennent à un ensemble décrit par des équations et inéquations
linéaires.

C. W. Royer Optimisation en Finance MIAGE 22-23 32

Formulation mathématique

minimiserx∈Rn f T x
s.c. Ax = b
Cx ≥ d.
avec A ∈ Rm×n , b ∈ Rm , C ∈ R`×n , d ∈ R` , f ∈ Rn .

Forme standard
minimiserx∈Rn f T x
s.c. Ax = b
x ≥ 0,

Tout programme linéaire peut se mettre sous cette forme.

Les contraintes d’intervalle x ≥ 0 peuvent ne concerner qu’une partie
des variables.

C. W. Royer Optimisation en Finance MIAGE 22-23 33

Exemple: Allocation de fonds (Cornuéjols et al. 2018)

On considère un ensemble de quatre fonds d’investissement ayant les

propriétés suivantes:
Fonds Fonds 1 Fonds 2 Fonds 3 Fonds 4
Part capitalisation haute 50% 30% 25% 60%
Part capitalisation moyenne 30% 10% 40% 20%
Part capitalisation basse 20% 60% 35% 20%
Retour sur investissement 10% 15% 16% 8%
On souhaite allouer 80000¤ parmi cet ensemble, de sorte à avoir
Au moins 35% de l’allocation en capitalisation haute;
Au moins 30% de l’allocation en capitalisation moyenne;
Au moins 15% de l’allocation en capitalisation basse.
On suppose que l’on ne peut investir que positivement dans un fonds
(long-only positions).
But: Trouver l’allocation qui maximise le retour sur investissement.

C. W. Royer Optimisation en Finance MIAGE 22-23 34

Formulation de l’exemple d’allocation

Variables et conventions
xi : Investissement dans le fonds i (en k¤).
Problème de maximisation sur x = [xi ]i=1..4 .

Le programme linéaire
maximiserx∈R4 0.1x1 + 0.15x2 + 0.16x3 + 0.08x4
s.c. 0.5x1 + 0.3x2 + 0.25x3 + 0.6x4 ≥ 28
0.3x1 + 0.1x2 + 0.4x3 + 0.2x4 ≥ 24
0.2x1 + 0.6x2 + 0.35x3 + 0.2x4 ≥ 12
x1 + x2 + x3 + x4 = 80
x ≥ 0.

C. W. Royer Optimisation en Finance MIAGE 22-23 35

Questions principales (d’après l’exemple)

Résolution d’un programme linéaire :

Comment identifier une allocation optimale ?
Comment la calculer numériquement ?
Sensibilité d’un programme linéaire :
Comment change la solution si le budget diminue ?
Que se passe-t-il si l’on modifie les contraintes de capitalisation ?

C. W. Royer Optimisation en Finance MIAGE 22-23 36

Table des matières

1 À propos du cours

2 Introduction

3 Bases d’optimisation

4 Programmation linéaire
Bases de la programmation linéaire
Solutions d’un programme linéaire
Algorithmes et logiciels pour la programmation linéaire

C. W. Royer Optimisation en Finance MIAGE 22-23 37

Cadre

Forme standard
 minimiserx∈Rn f T x


(P) s.c. Ax = b
x ≥ 0,


Hypothèses (simplificatrices)
A ∈ Rm×n est de rang plein.
Les contraintes de positivité s’appliquent à tous les xi .

C. W. Royer Optimisation en Finance MIAGE 22-23 38

Conditions d’optimalité

Théorème : Conditions de Karush-Kuhn-Tucker (KKT)

x ∗ ∈ Rn est une solution de (P) si et seulement si il existe y ∗ ∈ Rm et
s ∗ ∈ Rn tels que (x ∗ , y ∗ , s ∗ ) vérifie le système
 T ∗ ∗
 A ∗y + s = c

 Ax = b


(KKT ) x∗ ≥ 0
 s

 ∗ ≥ 0

 ∗ ∗
xi si = 0 ∀i = 1, . . . , n.

Les vecteurs y ∗ et s ∗ sont les multiplicateurs de Lagrange associés aux

contraintes d’égalité et de positivité.
Autres noms : variables duales, coûts fictifs ou réduits.

C. W. Royer Optimisation en Finance MIAGE 22-23 39

Problème dual

Problème dual
Le problème dual du problème (P) est
T

 maximisery ∈Rmn b y

s∈R
(D) s.c. AT y + s = c

s ≥ 0,


Conditions d’optimalité
Si (y ∗ , s ∗ ) est une solution de (D), il existe x ∗ ∈ Rn tel que (x ∗ , y ∗ , s ∗ )
vérifie les conditions de KKT !

C. W. Royer Optimisation en Finance MIAGE 22-23 40

Dualité et solutions

Théoème : On considère les problèmes (P) et (D)

1 Soit les deux problèmes sont irréalisables;
2 Soit (P) est irréalisable et (D) est non borné;
3 Soit (D) est irréalisable et (P) est non borné;
4 Soit les deux problèmes sont réalisables.

Outil : Théorème des alternatives

Soient A ∈ Rm×n et b ∈ Rm . Alors, les alternatives suivantes sont
mutuellement exclusives :
Soit ∃x, Ax = b, x ≥ 0, soit ∃y , AT y ≤ 0, b T y > 0.
Soit ∃x, Ax = 0, x 0, soit ∃y , AT y > 0.
Soit ∃x, Ax = 0, x > 0, soit ∃y , AT y 0.

C. W. Royer Optimisation en Finance MIAGE 22-23 41

Théorèmes de dualité

Dualité faible
Pour tout (y , s) admissible pour (D) et tout x admissible pour (P), on a
b T y ≤ c T x.

Dualité forte
Si les deux problèmes sont réalisables, alors il existe (x ∗ , y ∗ , s ∗ ) tel que :
x ∗ est solution de (P);
(y ∗ , s ∗ ) est solution de (D);
(x ∗ , y ∗ , s ∗ ) vérifie (KKT );
bT y ∗ = c T x ∗ .

Pour résoudre un problème linéaire, on peut donc chercher une solution

primale (de (P)) ainsi qu’une solution duale (de (D)) en résolvant (KKT ).

C. W. Royer Optimisation en Finance MIAGE 22-23 42

Analyse de sensibilité

Intérêt des variables duales

Décrire la sensibilité de la valeur optimale par rapport à une contrainte.
Permet d’analyser ce que donnerait une perturbation du second
membre de ces contraintes.

Résultat fondamental
Soit y une variable duale associée à une contrainte. Alors, pour tout ∆
suffisamment petit en valeur absolue, un changement de second membre
dans la contrainte induit un changement en valeur optimale de y · ∆.
Certain solveurs (de type simplexe) peuvent quantifier ce ∆.
En dehors des contraintes linéaires, on considère une interprétation
plus générale.

C. W. Royer Optimisation en Finance MIAGE 22-23 43

Interprétation

Problème perturbé
Partant du problème (P), on définit :

p(u, v ) = minn c T x Ax = b + u, x ≥ ‘v .

x∈R

Théorème
Si (y ∗ , s ∗ ) sont les variables duales du problème de départ, alors pour tous
u et v , on a
p(u, v ) ≥ p(0, 0) − (y ∗ )T u + (s ∗ )T v .

Chaque variable duale est un prix d’équilibre pour la ressource

représentée par la contrainte.
Ex) Si si∗  1 et v > 0, alors la valeur optimale augmente.

C. W. Royer Optimisation en Finance MIAGE 22-23 44

Table des matières

1 À propos du cours

2 Introduction

3 Bases d’optimisation

4 Programmation linéaire
Bases de la programmation linéaire
Solutions d’un programme linéaire
Algorithmes et logiciels pour la programmation linéaire

C. W. Royer Optimisation en Finance MIAGE 22-23 45

Logiciels : Tableurs

Solver sur Microsoft Excel

Basé sur une méthode de simplexe;
Fournit une analyse de sensibilité détaillée, avec notamment un
intervalle (plus ou moins interprétable) de valeurs dans lequel
l’approximation via les multiplicateurs est valide.

Fonctionnement similaire pour

Solveur dans LibreOffice/OpenOffice Calc;
Google Solve et OpenSolver sur Google Sheets.
Pas de marges de validité.

C. W. Royer Optimisation en Finance MIAGE 22-23 46

Logiciels : Programmation

CVX (Matlab)/CVXPy (Python)

Basés sur les points intérieurs;
Permet de toujours renvoyer les variables duales.

Gurobi/CPLEX/Mosek
Les meilleurs solveurs (commerciaux) du marché;
Basés sur une approche mixte simplexe/points intérieurs.

C. W. Royer Optimisation en Finance MIAGE 22-23 47