100% ont trouvé ce document utile (1 vote)

245 vues49 pages

Optimisation Financière: Cours M2 MIAGE

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

100% ont trouvé ce document utile (1 vote)

245 vues49 pages

Optimisation Financière: Cours M2 MIAGE

Transféré par

jmushway

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Optimisation en finance

Clément W. Royer

Notes de cours - M2 MIAGE - 2022/2023

• La version la plus récente de ces notes se trouve à l’adresse :
https://www.lamsade.dauphine.fr/∼croyer/ensdocs/OF/PolyOF.pdf.

• Pour tout commentaire, merci d’envoyer un mail à [email protected].

• Historique du document

– 2022.12.13 : Correction d’une ambiguı̈té dans la partie 2.2.2.

– 2022.12.04 : Version complète.
– 2022.11.15 : Première version.

• Objectifs d’apprentissage

– Comprendre les caractéristiques des modèles d’optimisation les plus classiques en finance.
– Connaı̂tre les grands principes derrière la résolution de ces modèles et les informations à
en tirer.
– Étudier des exemples de problèmes en finance et leur modélisation via des outils d’optimisation.
Sommaire

1 Introduction à l’optimisation 6
1.1 Définition et contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.1 Problème et processus d’optimisation . . . . . . . . . . . . . . . . . . . . . 6
1.1.2 Le contexte de la finance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Logiciels et optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Bases de l’optimisation mathématique . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Formulation générale et premières définitions . . . . . . . . . . . . . . . . . 8
1.4 Conclusion du chapitre 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Optimisation linéaire en finance 10

2.1 Bases de la programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Résolution d’un programme linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Dualité et conditions de KKT . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Analyse de sensibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Algorithmes et logiciels de programmation linéaire . . . . . . . . . . . . . . . . . . . 14
2.3.1 Algorithmes du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 Algorithmes de points intérieurs . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Application : arbitrage et programmation linéaire . . . . . . . . . . . . . . . . . . . 17
2.4.1 Formulation en programme linéaire . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.2 Théorème fondamental de l’arbitrage . . . . . . . . . . . . . . . . . . . . . . 18
2.5 Conclusion du chapitre 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6.1 Solution de l’exercice 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Optimisation quadratique en finance 23

3.1 Bases de la programmation quadratique . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Résolution d’un programme quadratique . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.1 Résolution théorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.2 Résolution algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Application : modèle de Markowitz . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.2 Problèmes d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3.3 Analyse des modèles et de leurs solutions . . . . . . . . . . . . . . . . . . . 27
3.4 Conclusion du chapitre 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2
Optimisation en finance - 2022/2023 3

4 Optimisation stochastique en finance 32

4.1 Formulation générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.1.1 Programmes stochastiques sans et avec recours . . . . . . . . . . . . . . . . 32
4.1.2 Programme linéaire stochastique en deux temps . . . . . . . . . . . . . . . . 33
4.2 Approche par scénarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2.2 Décomposition de Benders pour programmes linéaires stochastiques . . . . . 35
4.3 Mesures de risque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.3.1 Motivation et définition générique . . . . . . . . . . . . . . . . . . . . . . . 36
4.3.2 VaR et CVaR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.4 Conclusion du chapitre 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Annexe A Bases mathématiques 43

A.1 Éléments d’algèbre linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
A.1.1 Algèbre linéaire vectorielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
A.1.2 Algèbre linéaire matricielle . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Avant-propos

Le but de ce cours est de présenter les classes de problème d’optimisation les plus utilisés en finance,
et les algorithmes associés à leur résolution. Il se veut découpé en plusieurs parties suivant le
déroulement des séances de cours.
Ce cours n’est pas un cours de mathématiques, mais il repose sur plusieurs concepts élémentaires
d’algèbre linéaire et de calcul différentiel. Ceux-ci ne seront pas rappelés en détail en cours, mais
sont en revanche détaillés en annexe de ce polycopié. De même, les notations cruciales du polycopié
sont décrites ci-après.

4
Optimisation en finance - 2022/2023 5

Notations
• Les scalaires seront représentés par des lettres minuscules : a, b, c, α, β, γ.
• Les vecteurs seront représentés par des lettres minuscules en gras : a, b, c, α, β, γ.
• Les lettres majuscules en gras seront utilisées pour les matrices : A, B, C.
• Les lettres majuscules cursives seront utilisées pour les ensembles : A, B, C.
• La définition d’une nouvelle quantité ou d’un nouvel opérateur sera indiquée par :=.
• L’ensemble des entiers naturels sera noté N, l’ensemble des entiers relatifs sera noté Z.
• L’ensemble des réels sera noté R. L’ensemble des réels positifs sera noté R+ et l’ensemble des
réels strictement positifs sera noté R++ .
• On notera Rn l’ensemble des vecteurs à n composantes réelles, et on considèrera toujours que
n est un entier supérieur ou égal à 1.
• Un vecteur x ∈ Rn sera pensé (par convention) comme un vecteur colonne.
 On notera xi ∈ R
x1
n  .. 
sa i-ème coordonnée dans la base canonique de R . On aura ainsi x =  . . Étant donné
xn
un vecteur (colonne) x ∈ R , le vecteur ligne correspondant sera noté xT . On aura donc
n

xT = [x1 · · · xn ] et [xT ]T = x.
• Le produit scalaire entre deux vecteurs de Rn est défini√par xT v = v T x = di=1 xi vi . On
P

définit ensuite la norme d’un vecteur x ∈ Rn par kxk = xT x.

• On notera Rm×n l’ensemble des matrices à m lignes et n colonnes à coefficients réels, où m
et n seront des entiers supérieurs ou égaux à 1. Une matrice A ∈ Rn×n est dite carrée (dans
le cas général, on parlera de matrice rectangulaire).
• On identifiera les vecteurs de Rn avec les matrices de Rn×1 .
• Étant donnée une matrice A ∈ Rm×n , on notera Aij le coefficient en ligne i et colonne
j de la matrice. La diagonale de A est formée par l’ensembles des coefficients Aii pour
i = 1, . . . , min{m, n}. La notation [Aij ]1≤i≤m sera donc équivalente à A. Sans ambigüité
1≤j≤n
sur la taille de la matrice, on notera simplement [Aij ].
• Selon les besoins, on utilisera aT
i pour la
i-ème ligne de A ou aj pour la j-ème colonne de A.
a1T
 .. 
Selon le cas, on aura donc A =  .  ou A = [a1 · · · an ] .
aTm

• Pour une matrice A = [Aij ] ∈ Rm×n , la matrice transposée de A, notée AT , est la matrice
de Rn×m telle que
∀i = 1 . . . m, ∀j = 1 . . . n, AT
ji = Aij .

• Pour tout n ≥ 1, In correspond à la matrice identité Rn×n (avec 1 sur la diagonale et 0

ailleurs).
Chapitre 1

Introduction à l’optimisation

Le but de ce cours est d’étudier les problèmes d’optimisation issus de la science des données,
ainsi que les algorithmes qui leur sont appliqués. Le concept d’optimisation existe bien au-delà
de l’apprentissage, mais il est particulièrement important pour ce dernier. De nombreuses tâches
d’apprentissage peuvent en effet être formulées comme des problèmes d’optimisation, et ceux-ci
peuvent être résolus efficacement par des algorithmes modernes. Ce chapitre présente les principes
de base derrière la formulation et l’étude (à la fois mathématique et algorithmique) d’un problème
d’optimisation.

1.1 Définition et contexte

1.1.1 Problème et processus d’optimisation
Avant d’être un concept mathématique, un problème d’optimisation peut être verbalisé : on en donne
une décomposition ci-dessous.

Définition 1.1.1 Un problème d’optimisation mathématique est formé par les trois éléments suiv-
ants.

• Une fonction objectif : il s’agit du critère qui permet de quantifier la qualité d’une décision.
Selon le cas, une meilleure décision peut signifier une valeur de l’objectif plus faible (auquel cas
on aura affaire à un problème de minimisation) ou plus élevée (il s’agira alors d’un problème
de maximisation).

• Des variables de décision : ce sont les différents choix qu’il est possible d’effectuer, dont la
valeur influence celle de la fonction objectif. On cherche les meilleures valeurs de ces variables
relativement à l’objectif.

• Des contraintes : celles-ci spécifient des conditions qui doivent être satisfaites par les variables
de décision pour que les valeurs correspondantes soient acceptables.

Tout processus d’optimisation passe nécessairement par une phase de modélisation, durant
laquelle on transforme un problème concret en objet mathématique que l’on peut essayer de résoudre.
Pour cela, on se base sur des algorithmes d’optimisation qui, bien que pouvant être formulés à la
main, ont généralement vocation à être implémentés sur un ordinateur. Lorsque l’algorithme appliqué

6
Optimisation en finance - 2022/2023 7

au problème renvoie une réponse, celle-ci doit être examinée pour savoir si elle fournit une solution
satisfaisante au problème : au besoin, le modèle pourra être modifié, et l’algorithme ré-executé.
En pratique, le processus d’optimisation peut donc boucler après une phase d’interprétation ou de
discussion avec des experts du domaine d’application dont le problème est issu.

Remarque 1.1.1 L’optimisation numérique obéit généralement aux principes suivants :

• Il n’y a pas d’algorithme universel : certaines méthodes seront très efficaces sur certains types
de problèmes, et peu efficaces sur d’autres. L’étude de la structure du problème facilite le
choix d’un algorithme.

• Il peut y avoir un fort écart entre la théorie et la pratique : le calcul en précision finie peut
induire des erreurs d’arrondis qui conduisent à une performance en-deçà de celle prévue par la
théorie mathématique.

• La théorie guide la pratique, et vice-versa : pour la plupart des problèmes, il est possible de
définir des expressions mathématiques qui permettent de vérifier si l’on a trouvé une solution
du problème. Celles-ci sont à la base de nombreux algorithmes que nous étudierons. De
manière générale, l’étude théorique d’un problème permet des avancées garanties qui surpassent
souvent les heuristiques. Réciproquement, la performance de certaines méthodes a amené les
chercheurs en optimisation à en proposer une étude théorique, permettant ainsi d’expliquer le
comportement pratique.

1.1.2 Le contexte de la finance

L’optimisation est utilisée en finance comme un outil de modélisation et de résolution efficace de
problèmes.

Gestion des risques Durant la dernière décennie et suite à la crise dite des subprimes de 2007-2008,
la règlementation sur les niveaux de risques autorisés dans les milieux financiers a considérablement
évolué. Les opérations financières sont aujourd’hui exécutées En termes d’optimisation, on con-
sidèrera ainsi des problèmes sous contraintes de niveau de risque, tels que la maximisation du retour
sur investissement.

Gestion des actifs (assets) et des dettes (liabilities) La modélisation de valeurs d’actifs ou de
dettes prend en compte l’aléatoire sous-jacent au marché. En termes d’optimisation, on obtient ainsi
des problèmes d’optimisation stochastique, où le caractère aléatoire est modélisé par l’introduction
de variables aléatoires dont la valeur évolue sur une ou plusieurs périodes.

1.2 Logiciels et optimisation

L’optimisation a connu un essor majeur au cours des années 1980 avec le développement des ordi-
nateurs. Une composante majeure
Les langages de programmation les plus utilisés pour développer des algorithmes d’optimisation
étaient historiquemnet C/C++/Fortran, notamment pour développer des codes performants. Le
développement de prototypes de recherche se fait lui plutôt via des langages interprétés tels que
8 Optimisation en finance - 2022/2023

Matlab/Octave/Python/Julia, avec Python prenant de plus en plus d’importance de par son

utilisation dans les problèmes de sciences des données et apprentissage.
En plus des langages de programmation standard, de nombreux langages ou bibliothèques ont été
développés pour modéliser les problèmes d’optimisation. On peut citer notamment GAMS, AMPL,
CVX, Pyomo, qui ont un champ d’application génériques, ou MATPOWER et PyTorch, qui sont dédiés
à un domaine particulier (respectivement les réseaux d’énergie et l’apprentissage machine).

En finance Dans le contexte de la finance, le recours aux tableurs est prépondérant, ce qui a conduit
au développement de solveurs en tant qu’outil interne aux tableurs. C’est ainsi que Microsoft Excel,
LibreOffice Calc et Google Sheets possèdent des solveurs, notamment de programmation linéaire.
Si certains sont disponibles gratuitement (open source), le solveur le plus abouti (Microsoft Excel
Solver) requiert une licence d’exploitation1
D’autres outils plus bas niveau ont également été développés, parfois avec un spectre plus large
d’applications. Le logiciel MATLAB (propriétaire) dispose ainsi d’une boı̂te à outils de finance très
fournie, qui comporte notamment des algorithmes d’optimisation. On s’intéressera dans ce cours à
la bibliothèque cvxpy, développée à l’origine à l’université de Stanford (États-Unis), et qui dispose
de nombreux outils pour résoudre les problèmes de programmation convexe.

1.3 Bases de l’optimisation mathématique

1.3.1 Formulation générale et premières définitions
La transformation d’une description formelle d’un problème d’optimisation en objet mathématique
conduit à l’écriture suivante :
minimiser
n
f (x) s. c. x ∈ X, (1.3.1)
x∈R

où minimiser représente ce que l’on cherche à faire (on peut vouloir minimiser ou maximiser), x ∈ Rn
est un vecteur regroupant les variables de décision du problème, f : Rn → R est la fonction objectif
qui mesure la qualité des décisions, et X ⊂ Rn est l’ensemble des points réalisables ou admissibles,
qui vérifient les contraintes posées sur les variables de décision. 2

Définition 1.3.1 i) Un point x ∈ Rn tel que x ∈ X est dit admissible, ou réalisable.

ii) Un point x ∈ Rn tel que x 6∈ X est dit irréalisable.
iii) Si X = ∅, alors le problème (1.3.1) est dit irréalisable.

Définition 1.3.2 i) La valeur minimale (ou le minimum) du problème (1.3.1) est notée :
min {f (x)s. c. x ∈ X } . (1.3.2)
x∈Rn

Lorsque le problème possède une solution, la valeur minimale est la valeur de f en toute solution,
et cette valeur est finie. Lorsque le problème est irréalisable, on pose par convention
min {f (x)s. c. x ∈ X } = +∞.
x∈Rn
1
Il est à noter que si un compte passeport Dauphine permet d’accèder à Microsoft Excel, il ne donne pas l’autorisation
d’installer des extensions, et donc ne permet pas l’utilisation de Solver.
2
L’abbréviation s.c. signifie “sous la/les contrainte(s)”; en anglais, on utilise s.t., pour subject to.
Optimisation en finance - 2022/2023 9

Enfin, si le problème est réalisable mais qu’il n’existe pas de solution, on aura
min {f (x)s. c. x ∈ X } = −∞,
x∈Rn

et on dit alors que le problème est non borné.

ii) L’ensemble des solutions du problème (1.3.1) est noté
argmin {f (x)s. c. x ∈ X } , (1.3.3)
x∈Rn

qu’on appelle argument minimal (ou argmin) du problème. C’est un sous-ensemble de Rn (et
de X ) : il s’agit de l’ensemble des points de X qui donnent la valeur minimale de f . Il est vide
si le problème est irréalisable ou réalisable et non borné.
Remarque 1.3.1 Le problème (1.3.1) n’admet pas forcément de solution (prendre par exemple
d = 1, F = R et f (w) = w) : dans ce cas, l’argument minimal est l’ensemble vide, et la valeur
minimale est −∞.
On définit de la même manière que précédemment les problèmes de maximisation ainsi que les
opérateurs argmax et max. Dans ce cours, on se concentrera sur les problèmes de minimisation,
utilisant en cela la propriété ci-dessous.
Proposition 1.3.1 Pour toute fonction f : Rn → R et tout ensemble F ⊂ Rn , résoudre le problème
de maximisation
maximiser
n
f (x) s. c. x ∈ F
x∈R
équivaut à résoudre le problème de minimisation
minimiser
n
−f (x) s. c. x ∈ F,
x∈R

dans la mesure où

argmax {f (x)s. c. x ∈ F} = argmin {−f (x)s. c. x ∈ F}
x∈Rn x∈Rd
et
max {f (x)s. c. x ∈ F} = − minn {−f (x)s. c. x ∈ F} .
x∈Rn x∈R

Tout problème de maximisation se ramène donc à un problème de minimisation via une re-
formulation. Nous verrons d’autres exemples de reformulation, qui est une technique très utilisée
pour transformer un problème en un autre problème équivalent mais que l’on saura mieux traiter
théoriquement et/ou algorithmiquement.
Dans la majorité de ce cours, et notamment dans le reste de ce chapitre, on se concentrera sur
des problèmes d’optimisation sans contraintes pour en caractériser plus précisément les solutions.

1.4 Conclusion du chapitre 1

L’optimisation est un outil mathématique qui permet de modéliser de nombreux problèmes en sciences
des données et au-delà. L’optimisation comporte toujours une phase de modélisation, qui consiste
à formuler mathématiquement le problème en définissant une fonction objectif, des variables de
décisions et des contraintes. Cela permet de placer le problème dans une classe, et ainsi de caractériser
ce qu’est une solution de ce problème.
Chapitre 2

Optimisation linéaire en finance

Dans ce chapitre, nous nous intéressons aux problèmes de programmation linéaire. Le développement
algorithmique lié à la résolution de ces problèmes, dû notamment à George Dantzig dans les années
1960, a conduit à des avancées majeures dans de nombreux domaines d’application, dont la finance.
Les programmes linéaires forment une classe bien comprise de problèmes d’optimisation qui perme-
ttent à la fois de modéliser de nombreux problèmes concrets et également de les résoudre avec des
algorithmes efficaces, même en présence d’un très grand nombre de variables.

2.1 Bases de la programmation linéaire

Formellement, un programme linéaire consiste à minimiser ou maximiser une fonction linéaire des
variables de décision sous la contrainte que ces variables appartiennent à un ensemble décrit par des
équations et inéquations linéaires.

Définition 2.1.1 Un programme linéaire est un problème d’optimisation de la forme

minimiserx∈Rn cT x
s.c. Ax = b
Dx ≥ f .

avec A ∈ Rm×n , b ∈ Rm , D ∈ R`×n , f ∈ R` , c ∈ Rn .

Définition 2.1.2 Un programme linéaire en forme standard est de la forme

minimiserx∈Rn cT x
s.c. Ax = b
x ≥ 0,

où les contraintes d’intervalle x ≥ 0 peuvent porter seulement sur un sous-ensemble des coordonnées
de x.

Tout programme linéaire peut se mettre sous forme standard en introduisant des variables
supplémentaires. Par exemple, la contrainte x1 ≥ 1 peut se réécrire comme

x1 − s1 = 1, s1 ≥ 0.

10
Optimisation en finance - 2022/2023 11

Exemple 2.1.1 (Allocation de fonds (Cornuéjols et al. 2018)) On considère un ensemble de qua-
tre fonds d’investissement ayant les propriété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 à 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), et on
cherche l’allocation qui maximise le retour sur investissement.
Pour modéliser cet exemple via un programme linéaire, on commence par identifier les variables :
on définit ainsi x ∈ R4 , où xi correspond à l’investissement dans le fond i (exprimé en k¤). On
obtient ainsi le problème de maximisation suivant

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
(2.1.1)
0.2x1 + 0.6x2 + 0.35x3 + 0.2x4 ≥ 12
x1 + x2 + x3 + x4 = 80
x ≥ 0.

Le problème (2.1.1) n’est pas en forme standard, mais peut être converti sous cette forme en
utilisant la procédure décrite plus haut. Il possède trois contraintes d’inégalité linéaires, une contrainte
d’égalité linéaire et quatre contraintes de positivité concaténées sous la forme x ≥ 0.

2.2 Résolution d’un programme linéaire

La théorie de la programmation linéaire permet à la fois de déterminer si un programme linéaire
possède une solution et de donner des conditions qui caractérisent ces solutions si elles existent. Un
outil majeur

2.2.1 Dualité et conditions de KKT

Dans cette partie, on se concentre sur le problème suivant, appelé problème primal

 minimiserx∈Rn cT x


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

On fera les hypothèses simplificatrices suivantes.

12 Optimisation en finance - 2022/2023

Hypothèse 2.2.1 • A ∈ Rm×n est de rang plein.

• Les contraintes de positivité s’appliquent à tous les xi .

Théorème 2.2.1 (Conditions de Karush-Kuhn-Tucker (KKT)) On considère le problème (P)

sous l’hypothèse (2.2.1). Un point x∗ ∈ Rn est une solution de (P) si et seulement si il existe
y ∗ ∈ Rm et s∗ ∈ Rn tels que (x∗ , y ∗ , s∗ ) vérifie le système
 T ∗
 A y + s∗ = c
 Ax∗

= b


x ∗ ≥ 0 (KKT-Lin)


 s ∗ ≥ 0

 ∗ ∗
xi si = 0 ∀i = 1, . . . , n.

Les vecteurs y ∗ et s∗ sont les multiplicateurs de Lagrange associés aux contraintes d’égalité et
de positivité. En optimisation, on les appelle variables duales.

Remarque 2.2.1 En finance, les variables duales associées à une contrainte linéaire sont appelées
des shadow prices, ou prix fictifs. Dans le cas d’une contrainte de positivité, le multiplicateur associé
sera appelé un coût réduit.

Définition 2.2.1 (Problème dual) Le problème dual de (P) est donné par

bT y

 maximisery∈Rm

s∈Rn
s.c. AT y + s = c (D)

s ≥ 0.


Proposition 2.2.1 (Conditions d’optimalité) Si (y ∗ , s∗ ) est une solution de (D), il existe x∗ ∈ Rn

tel que (x∗ , y ∗ , s∗ ) vérifie les conditions de KKT.

L’intérêt de formuler le problème dual réside dans le lien intrinsèque entre ces deux problèmes
comme suit.

Théorème 2.2.2 On considère les problèmes (P) et (D).

1. Soit les deux problèmes sont irréalisables;

2. Soit (P) est irréalisable et (D) est non borné;

3. Soit (D) est irréalisable et (P) est non borné;

4. Soit les deux problèmes sont réalisables.

La preuve de ce résultat repose sur le résultat suivant d’algèbre linéaire.

Théorème 2.2.3 (Théorème des alternatives) Soient A ∈ Rm×n et b ∈ Rm . Alors, les alterna-
tives suivantes sont mutuellement exclusives :

• Soit ∃x, Ax = b, x ≥ 0, soit ∃y, AT y ≤ 0, bT y > 0.

Optimisation en finance - 2022/2023 13

• Soit ∃x, Ax = 0, x 0, soit ∃y, AT y > 0.

• Soit ∃x, Ax = 0, x > 0, soit ∃y, AT y 0.

En plus de résultats sur le caractère réalisable ou non borné des problèmes, on peut aussi lier les
solutions de chaque problème.

Théorème 2.2.4 (Dualité faible) Pour tout (y, s) admissible pour (D) et tout x admissible pour
(P), on a bT y ≤ cT x.

Théorème 2.2.5 (Dualité forte) Si les deux problèmes sont réalisables, alors il existe (x∗ , y ∗ , s∗ )
tel que :
• x∗ est solution de (P);
• (y ∗ , s∗ ) est solution de (D);
• (x∗ , y ∗ , s∗ ) vérifie (KKT );
• bT y ∗ = cT x∗ .

Pour résoudre un problème linéaire, on peut donc chercher à la fois une solution primale de (P)
ainsi qu’une solution duale de (D) en résolvant (KKT-Lin).

2.2.2 Analyse de sensibilité

On s’intéresse maintenant à un usage a posteriori des variables duales. Celles-ci permettent en
effet de décrire la sensibilité de la valeur optimale d’un problème relativement à une contrainte, en
décrivant l’effet d’une perturbation du second membre de ces contraintes.

Théorème 2.2.6 Soit y une variable dual associée à une contrainte d’un programme linéaire. Alors,
pour tout ∆ suffisamment petit en valeur absolue, un changement de second membre dans la con-
trainte de ∆ induit un changement de valeur optimale de y · ∆.

Ainsi, la valeur absolue d’un multiplicateur permet de juger de la sensibilité du problème par
rapport à une contrainte. Dans le cas où y = 0, par exemple, on sait que la solution ne changera pas
si l’on perturbe un peu la contrainte : cela signifie en général que cette contrainte n’est pas critique
pour calculer la solution.

Remarque 2.2.2 En règle générale, l’intervalle de valeurs ∆ pour lesquelles le résultat du théorème 2.2.6
s’applique n’est pas connu. Cependant, dans le cadre de la programmation linéaire et notamment
des algorithmes de type simplexe, il est possible de quantifier ce ∆.

Une interprétation plus générale de la sensibilité est fournie ci-dessous. On se place comme dans
la section précédente dans le cadre d’un programme linéaire en forme standard.

Définition 2.2.2 (Problèmes perturbés) Partant du problème (P) (sous l’hypothèse 2.2.1), on
définit pour tous u ∈ Rm et v ∈ Rn :
p(u, v) := minn cT x Ax = b + u, x ≥ ‘v .

(2.2.1)
x∈R

On notera que la valeur p(0, 0) correspond à la valeur optimale du problème de départ.

14 Optimisation en finance - 2022/2023

Théorème 2.2.7 Si (y ∗ , s∗ ) sont les variables duales du problème de départ, alors pour tous u et
v, on a
p(u, v) ≥ p(0, 0) + (y ∗ )T u + (s∗ )T v. (2.2.2)

En finance, le résultat du théorème 2.2.7 s’interprète comme le fait que chaque variable duale
(ou multiplicateur) représente un prix d’équilibre pour la ressource représentée par la contrainte.
Cela permet d’identifier les effets positifs ou négatifs d’agir sur la contrainte. A titre d’exemple,
notons que si s∗i 1 et vi > 0, alors l’équation 2.2.2 indique que la valeur optimale du problème
augmentera si l’on requier xi ≥ vi au lieu de xi ≥ 0, ce qui semble logique car on réduit ici l’ensemble
des contraintes.

2.3 Algorithmes et logiciels de programmation linéaire

Comme on l’a vu dans la partie précédente, les conditions d’optimalité (dites de KKT) d’un pro-
gramme linéaire permettent de caractériser ses solutions si elles existent. Cependant, déterminer les
solutions du problème directement depuis les conditions de KKT s’avère délicat, car celles-ci forment
un système d’équations non linéaires.
On décrit ci-après le fonctionnement de ces méthodes dans le cas d’un programme linéaire en
forme standard, et on supposera que ce problème et son dual sont tous deux réalisables. Les conditions
d’optimalité pour ce programme, ou de KKT s’écrivent
 T

 A y+s = c
 Ax = b


x ≥ 0 (2.3.1)
s ≥ 0




xi s i = 0 ∀i = 1, . . . , n.


On décrit ci-après les deux grandes catégories de méthodes qui visent à résoudre ces conditions
d’optimalité de manière itérative.

2.3.1 Algorithmes du simplexe

La méthode du simplexe classique revient à une suite {xk , y k , sk } vérifiant les conditions de KKT
sauf s ≥ 0, et vise à satisfaire cette condition asymptotiquement. La variante duale du simplexe
cherche à satisfaire x ≥ 0.
L’idée principale de l’algorithme du simplexe est d’exploiter le fait que l’ensemble réalisable
d’un programme linéaire (réalisable) est un polyèdre, et que la solution du problème se trouve
nécessairement sur un sommet de ce polyèdre. En ce sommet, toutes les contraintes d’inégalité ne
sont généralement pas actives : dans le cadre d’un problème en forme standard (P), cela signifie que
certaines coordonnées de la solution seront nulles (contrainte xi ≥ 0 active) tandis que d’autres ne
le seront pas. Le théorème ci-dessous garantit qu’identifier ces contraintes actives est suffisant pour
déterminer la solution.

Théorème 2.3.1 On considère le problème (P) et son dual sous l’hypothèse 2.2.1. Alors, il existe
une partition B ∪ N = {1, . . . , n} telle que

i) |B| = m;
Optimisation en finance - 2022/2023 15

ii) la matrice AB := [Aij ]1≤i≤m est inversible;

j∈B

iii) la solution du problème x∗ se décompose selon la partition en

x∗B = [xj ]j∈B = −A−1

B b

et x∗N = 0.
−1
Dans ce cas, une solution duale du problème est donnée par y ∗ = AT
B cB .

L’ensemble B, qui caractérise un ensemble de contraintes, est appelé une base du problème.
L’algorithme du simplexe décrit une manière algorithmique de parcourir l’ensemble des sommets
du polyèdre en recherchant la base dans laquelle la solution optimale doit être exprimée. Ce processus
termine nécessairement après un nombre fini d’itérations, mais celui-ci peut être très grand si le
nombre de contraintes est important.

Principe général L’algorithme commence par déterminer une base B telle que les propriétés i) et
ii) du théorème 2.3.1 soient vérifiées. Si le vecteur x associé vérifie x ≥ 0, on parle alors de solution
basique (même s’il ne s’agit pas forcément de la solution optimale, il s’agit d’un point réalisable). Il
s’agit ensuite de regarder le vecteur

c̄ = c − AT A−T
B cB ,

qui correspond aux variables duales s dans les conditions de KKT. Si les coordonnées de ce vecteur
sont positives ou nulles, alors on a obtenu une solution optimale. Sinon, cela signifie qu’il existe un
indice de colonne j 6∈ B tel que c̄j < 0 et

cT x − αA−1 T

B aj < c x

pour tout α > 0. Cette propriété signifie que l’on ne dispose pas de la bonne base B, et qu’il en
existe une meilleure contenant j : l’algorithme du simplexe explique comment échanger j avec un
élément de la base.

Variante duale Le principe de méthode du simplexe décrit plus haut est un principe primal, qui
se base essentiellement sur le calcul d’une solution primale x ∈ Rn . Il existe également des variantes
duales, dans lesquelles on calcule (y, s) tels que AT y + s = 0, s ≥ 0, Ax = b et xi si = 0 pour
tout i = 1, . . . , n.

Implémentation L’algorithme du simplexe est notamment utilisé dans l’extension Solver de Mi-
crosoft Excel. Ce solveur fournit une analyse de sensibilité détaillée, avec notamment un intervalle
(plus ou moins interprétable) de valeurs dans lequel l’approximation via les multiplicateurs décrite
dans le théorème 2.2.6 est valide. Le solveur de LibreOffice/OpenOffice Calc est également un solveur
de type simplexe, ce qui se reconnaı̂t notamment par rapport à la saturation des contraintes en la
valeur renvoyée. De même, Google Solve et OpenSolver (accessibles dans Google Sheets) se basent
sur le même genre de techniques, sans pour autant fournir de marges de validité des multiplicateurs.
Enfin, le solveur HIGHS, qui est maintenant l’algorithme par défaut de simplexe dans la bibliothèque
SciPy, est lui aussi basé sur une approche de simplexe.
16 Optimisation en finance - 2022/2023

2.3.2 Algorithmes de points intérieurs

La méthode du simplexe repose sur le fait de parcourir les sommets de l’ensemble des contraintes
d’un programme linéaire, qui (lorsqu’il est non vide) est un polyèdre. De par la structure même
du programme linéaire, on sait que la solution se trouve sur un sommet, et donc qu’il existe un
certain nombre de contraintes d’inégalité satisfaites avec égalité en la solution (c’est le sens du
Théorème 2.3.1).
Le principe des méthodes de points intérieurs, comme leur nom l’indique, consiste à passer par
l’intérieur de l’ensemble réalisable de sorte à arriver plus vite au sommet solution qu’en parcourant
l’ensemble des sommets.

Principe Un algorithme de points intérieurs part des conditions de KKT (KKT-Lin) et considère
des points dans l’intérieur de l’ensemble réalisable, c’est-à-dire des triplets de la forme (x, y, s) tels
que
Ax = b, AT y + s = c, x > 0, y > 0.
Un tel triplet est dit primal-dual admissible, car il vérifie les contraintes du problème primal et celles
du problème dual. En revanche, il ne vérifie pas la dernière condition d’optimalité de (KKT-Lin), car
xi si > 0 pour tout i. On pose alors
n
X xi s i
µ= , (2.3.2)
n
i=1

qui représente une certaine distance entre le point calculé et une solution des conditions de KKT.
Le but d’une méthode de points intérieurs est de calculer une suite de triplets telle que la valeur de
µ tende vers 0, et ainsi de devenir de plus en plus proche d’un point optimal. En pratique, on peut
calculer pour tout µ > 0 une solution vérifiant les conditions souhaitées en trouvant (x, y, s) tels
que xi > 0 et si > 0 pour tout i, et le triplet est solution du système linéaire

Ax = b
T
A y+s = c
XSe = µe, (2.3.3)

où X et S sont deux matrices diagonales donc les coefficients diagonaux sont ceux des vecteurs x
et s, respectivement, et e ∈ Rn est le vecteur dont toutes les coordonnées valent 1. On peut ainsi
calculer ce type de triplet pour des valeurs décroissantes de µ : c’est ce que font les approches de
points intérieures dites primales-duales.
La théorie des points intérieurs est extrêment riche en résultats, en particulier pour des pro-
grammes linéaires. Le succès originel des points intérieurs réside dans l’obtention de garanties de
convergence en temps polynomial vers une solution approchée du problème (qui dépend de la valeur
du paramètre µ défini en (2.3.2)). Ce type de résultat contraste avec ceux existants pour le simplexe,
où le temps de calcul peut être exponentiel pour atteindre la solution.

Implémentation CVX (MATLAB) et sa variante CVXPy en Python est à la fois un langage de

modélisation et un outil de résolution basé sur les points intérieurs. Il permet de toujours renvoyer
les variables duales d’un problème. Cette librairie permet notamment l’interface avec les meilleurs
solveurs commerciaux du marché que sont Gurobi, CPLEX et Mosek. Ceux-ci sont basés sur une
approche mixte simplexe/points intérieurs en ce qui concerne la programmation linéaire.
Optimisation en finance - 2022/2023 17

2.4 Application : arbitrage et programmation linéaire

Les problèmes d’arbitrage se posent lorsque l’on cherche à échanger différentes devises. On parle
d’opportunités d’arbitrage lorsqu’il est possible de réaliser un bénéfice via un cycle d’échanges de
devises.

Exemple 2.4.1 Supposons que l’euro s’échange à 0,9 dollar, et que le dollar s’échange à 1,22 euro.
Dans ce cas, pour tout euro échangé en dollar et à nouveau en euro, on obtiendrait 1,098 euro, soit
un bénéfice.

Dans cette section, on s’intéresse à la détection d’opportunités d’arbitrage lorsque l’on considère
un ensemble arbitraire de devises.

2.4.1 Formulation en programme linéaire

On considère que l’on dispose d’un tableau A = [aij ] 1≤i≤n représentant des taux d’échange entre
1≤j≤n
n monnaies. Une unité de monnaie i s’échange ainsi contre aij > 0 unités de monnaie j. On
posera aii = 1 pour tout i = 1, . . . , n de sorte à éviter les arbitrages triviaux, et on fait l’hypothèse
simplificatrice que le coût de conversion entre devises est nul.
On choisit les quantités suivantes comme variables du problème :

• xij : quantité de devise i échangée en devise j, que l’on souhaitera toujours positive ou nulle
(on s’attend notamment à ce que xii = 0);

• yk : quantité de devise k obtenue après tous les échanges, définie par

n
X n
X
yk = aik xik − xkj ,
i=1 j=1

où la première somme correspond à la quantité de devise k obtenue en échangeant d’autres

monnaies, et la seconde correspond à la quantité de devise k échangée contre d’autres mon-
naies. On souhaitera toujours avoir yk ≥ 0.

Lorsque yk > 0 pour une devise k donnée, on a une opportunité d’arbitrage. Notre objectif consiste
donc à définir un ensemble de transactions (c’est-à-dire de valeurs pour {xij }ij et, par là-même, de
valeurs pour {yk }k ) telles que l’une des quantités de devise après transaction soit positive. Dans
ce qui suit, on se concentrera sur l’existence d’un arbitrage pour la devise 1, et on cherchera donc
{xij }ij tels que y1 > 0.
Une première modélisation consiste à maximiser la valeur de y1 , ce qui conduit au problème

 maximiser{xij },{yk } y1
s.c. yk = ni=1 aik xik − nj=1 xkj k = 1, . . . , n

 P P


 yk ≥ 0 k = 1, . . . , n
≥ 0 i, j = 1, . . . , n.

xij
(2.4.1)
Si ce problème est un programme linéaire presque en forme standard (il faudrait minimiser plutôt
que maximiser, ce que l’on peut faire en minimisant −y1 ), il n’est pas pour autant bien posé. En
effet, s’il existe effectivement une opportunité d’arbitrage pour la devise 1, alors il existe un point
18 Optimisation en finance - 2022/2023

admissible à ce problème avec y1 > 0. Il en existe même une infinité, et pour tout choix des {xij }
qui conduit à un bénéfice de y1 , alors le choix {λxij } où λ > 1 conduit à λy1 > y1 . Par conséquent,
le problème est non borné. Un remède à cela consiste simplement à imposer une borne sur y1 , qui
sera une valeur cible pour l’arbitrage. En choisissant cette valeur cible comme étant égale à 1, on
obtient

 maximiser{xij },{yk } y1
s.c. yk = ni=1 aik xik − nj=1 xkj k = 1, . . . , n

 P P


y1 ≤1
y ≥ 0 k = 1, . . . , n



 k
≥ 0 i, j = 1, . . . , n.

xij
(2.4.2)
La résolution du programme linéaire (2.4.2) conduit aux deux cas suivants : soit il n’y a pas d’arbitrage
possible, auquel cas la valeur optimale du problème est 0, et xij = yk = 0 pour tous i, j, k, soit il y
a un arbitrage possible, et on aura alors y1 = 1.

2.4.2 Théorème fondamental de l’arbitrage

La notion d’arbitrage peut s’exprimer de manière plus abstraite, mais toujours en lien avec la pro-
grammation linéaire. Soit un système composé de m actifs durant une période donnée de T = 0 à
T = 1. On définit le vecteur  1
s0
 .. 
s0 =  .  ∈ Rm ,
sm0
qui représente les valeurs des actifs à l’instant T = 0 (on considère les valeurs comme pouvant être
positives ou négatives). À l’instant T = 1, le système peut être dans un état ω ∈ {ω1 , . . . , ωn }, qui
définit un nouveau vecteur de valeurs pour les actifs. On pose ainsi
 1 
s1 (ωj )
∀j = 1, . . . , n, s1 (ωj ) =  ...  ∈ Rm .
 

sm1 (ωj )

Une opportunité d’arbitrage dans ce contexte est un vecteur y ∈ Rm tel que

 T
 s0 y ≤ 0
s1 (ωj )T y ≥ 0 j = 1, . . . , n (2.4.3)
 T
s0 y 6= 0 ou s1 (ωj )T y j = 1, . . . , n.
L’existence ou l’absence d’un tel arbitrage est établie par le résultat suivant, appelé en anglais
asset pricing.
Théorème 2.4.1 (Théorème fondamental de l’arbitrage) On considère les vecteurs s0 , s1 (ω1 ),. . . ,
s1 (ωn ) définis ci-dessus. Alors,
i) Soit il existe un arbitrage, c’est-à-dire un vecteur y ∈ Rm vérifiant les conditions (2.4.3);
ii) Soit il existe x ∈ Rn tel que
n
X
s0 = xj s1 (ωj ) avec xj > 0∀j = 1, . . . , n. (2.4.4)
j=1
Optimisation en finance - 2022/2023 19

Le résultat du théorème 2.4.1 peut s’écrire comme un théorème des alternatives similaire au
théorème 2.2.3 de la manière suivante :
i) Soit il existe x ∈ Rn solution du système

Sx = s0 , S = [s1 (ω1 ) · · · s1 (ωn )],

avec x > 0;
ii) Soit il existe y ∈ Rm tel que
0 6= [S − s0 ]T y ≥ 0.

Ce type de condition n’est pas un problème d’optimisation linéaire, mais est en revanche considéré
comme un programme linéaire (résoudre un système d’inégalités et d’égalités linéaires). De fait, en
introduisant une fonction objectif constante, il serait possible d’écrire les conditions ci-dessus comme
contraintes d’un programme linéaire.

2.5 Conclusion du chapitre 2

La programmation linéaire permet de modéliser un grand nombre de problèmes, parfois grâce à des
hypothèses simplificatrices (que l’on cherchera à relâcher dans la suite grâce à des formulations plus
complexes). Un des grands avantages des programmes linéaires réside dans leur facilité de résolution,
que ce soit par l’algorithme du simplexe ou les approches de points intérieurs. Par ailleurs, l’analyse
de ces problèmes au moyen de la théorie de la dualité et des multiplicateurs de Lagrange (ou coûts
fictifs/réduits) permet à la fois de caractériser les solutions et d’analyser la sensibilité d’une solution
aux différentes contraintes. Ce procédé se révèle essentiel pour ne pas avoir à résoudre un problème
de manière répétée.

2.6 Exercices
Exercice 1 : Gestion actifs-passifs
Dans cet exercice, on s’intéresse aux problèmes dits de gestion actifs-passifs1 , que l’on
peut modéliser par des programmes linéaires en supposant que le seul risque inhérent
au problème réside dans les taux d’intérêt. On souhaite construire un portefeuille qui
génère suffisamment de liquidités pour couvrir des besoins (passifs) sur une période de
m années consécutives. On note `i > 0 le besoin en liquidités pour l’année i.
On suppose que le portefeuille peut être construit à partir de n obligations ayant chacune
un prix unitaire et qui génèrent un flot de liquidités sur la période des m années. On
notera Fij le flot de liquidités généré par l’obligation j en l’an i.

Année 1 2 ··· m
Obligation Prix unitaire
B1 F11 F21 ··· Fm1 p1
.. .. .. .. .. ..
. . . . . .
Bn F1n F2n ··· Fmn pn
1
Ou asset and liability management (ALM) en anglais.
20 Optimisation en finance - 2022/2023

On souhaite déterminer le portefeuille de coût minimal parmi ceux pouvant couvrir les
besoins en liquidités sur les m années. On supposera qu’on construit le portefeuille à
partir de quantités d’obligations non négatives.
Formuler le problème comme un programme linéaire selon les trois manières suivantes :

a) en supposant que le flot de liquidités à l’année i doit a minima couvrir les besoins
sur l’année `i , et en utilisant des contraintes d’inégalité linéaires. Justifier le choix
des inégalités linéaires par rapport aux égalités linéaires.
b) en supposant que le flot de liquidités à l’année i doit a minima couvrir les besoins
sur l’année `i , et en mettant le problème sous forme standard;
c) en supposant qu’un surplus de liquidités peut être reportés d’une année sur l’autre,
et en restant en forme standard.

2.6.1 Solution de l’exercice 1

Les variables du problème, concaténées dans un vecteur x ∈ Rn , représentent les quantités des
différentes obligations. L’objectif consiste à minimiser le coût du portefeuille qui est donné par
n
X
T
p x= p i xi ,
i=1

où p est le vecteur de prix qui concatène p1 , . . . , pn . En termes de contrainte, on sait d’après l’énoncé
que l’on cherche à avoir xi ≥ 0 pour tout i = 1, . . . , n.

a) Pour cette première modélisation, on cherche à couvrir les besoins en liquidité sur chaque année
uniquement avec les liquidités obtenues durant cette période. Pour chaque année i, cela s’exprime
par la contrainte
Xn
Fij xj ≥ `i .
j=1

Il est à noter que formuler cette contrainte comme une contrainte d’égalité linéaire n’est pas
souhaitable, car cela pourrait conduire à ce que le problème soit irréalisable. Au final, on obtient le
problème
 minimiserx∈Rn pT x


s.c. F T x ≥ `, i = 1, . . . , m (2.6.1)
x ≥ 0,


où F ∈ Rn×m est la matrice des Fij (flots de liquidités) et ` = [`i ] ∈ Rn est le vecteur des besoins.

b) Pour mettre le problème en forme standard, on transforme les contraintes d’inégalité en con-
traintes d’égalité en rajoutant des variables d’écart. On obtient ainsi

 minimiser x∈Rn pT x
s∈Rm


s.c. F T x − s = `

(2.6.2)


 x ≥ 0
s ≥ 0.

Optimisation en finance - 2022/2023 21

c) Les contraintes F T x − s = ` formulées en question b) modélisent de Pfait la présence éventuelle

d’un surplus. En effet, le surplus de liquidités en l’an j est donné par ni=1 Fij xi − `j = sj . Par
conséquent, pour modéliser le fait que l’on puisse reporter un surplus d’une année sur l’autre, on
remplace la contrainte
X n
Fij xi − sj = `j
i=1

par
n
X
Fij xi − sj + sj−1 = `j
i=1

lorsque j ≥ 2 (on ne peut pas effectuer de report la première année).

Exercice 2 : Contraintes de levier

Dans les exemples considérés dans ce chapitre, on a considéré pour simplifier que l’on
n’effectue que des investissements positifs (long-only positions). Cependant, en pra-
tique, on autorise un certain niveau d’investissements négatifs (ou short positions), qui
représentent une réinjection d’un investissement existant dans un autre fonds. Mathématiquement,
on modélise cette liberté par l’introduction d’une contrainte dite de levier dans la
modélisation, de la forme :
Xn
min{xj , 0} ≥ −L, (2.6.3)
j=1

où L > 0 est un niveau de levier fixé. Cette contrainte est non linéaire en les variables
xj du fait de l’utilisation de l’opérateur min.

a) En programmation linéaire, l’inégalité (2.6.3) est en général remplacée par le système

 Pn
 j=1 zj ≥ −L
zj ≤ xj j = 1, . . . , n (2.6.4)
zj ≤ 0 j = 1, . . . , n,


où z ∈ Rn est un vecteur de variables auxiliaires. Pour tout x ∈ Rn vérifiant (2.6.3),

donner un vecteur z vérifiant (2.6.4).
b) Convertir le système d’inégalités et d’égalités obtenu en question a) en forme stan-
dard 2 s’il ne l’est pas déjà.

Solution de l’exercice 2
a) On introduit le vecteur z ∈ Rn dont les composantes sont données par zj = min{xj , 0}. Ce
vecteur vérifie bien le système (2.6.4) dès lors que x vérifie (2.6.3).
2
Par abus de langage, on considèrera qu’un tel système est en forme standard si un programme linéaire avec de
telles contraintes le serait.
22 Optimisation en finance - 2022/2023

b) Pour reformuler le système en forme standard, on introduit 2n+1 variables auxiliaires s ∈ R2n+1
qui seront contraintes d’être positives ou nulles. On obtient ainsi le système suivant :
 Pn

 j=1 zj − s1 = −L
zj + sj+1 = xj j = 1, . . . , n


 z j + s j+n+1 = 0 j = 1, . . . , n
s ≥ 0,


qui est bien en forme standard.

Chapitre 3

Optimisation quadratique en finance

Dans ce chapitre, on cherche à étendre les résultats du chapitre précédent au cas où la fonction
objectif n’est plus linéaire mais quadratique en les variables de décision. Comme on le verra, il est
possible de développer une théorie de la dualité ainsi que des algorithmes similaires à ceux utilisés
pour la programmation linéaire. On s’intéressera tout particulièrement au modèle de Markowitz, qui
conduit à des programmes quadratiques spécifiques.

3.1 Bases de la programmation quadratique

Définition 3.1.1 Un programme quadratique, ou problème d’optimisation quadratique, est un problème
d’optimisation de la forme
minimiserx∈Rn 12 xT Hx + g T x
s.c. Ax = b
Cx ≥ d.
avec H ∈ Rn×n , g ∈ Rn , A ∈ Rm×n , b ∈ Rm , C ∈ R`×n , d ∈ R` .

Définition 3.1.2 Un programme linéaire en forme standard est de la forme

minimiserx∈Rn 21 xT Hx + g T x
s.c. Ax = b (3.1.1)
x ≥ 0,

où les contraintes d’intervalle x ≥ 0 peuvent porter seulement sur un sous-ensemble des coordonnées
de x.

En général, une modélisation en programme quadratique est faite de sorte à satisfaire l’hypothèse
ci-dessous.

Hypothèse 3.1.1 La matrice H est symétrique et semi-définie positive.

Un cas particulier de programme quadratique, très important dans la pratique, est décrit dans
l’exemple ci-dessous.

Exemple 3.1.1 (Moindres carrés linéaires) Soient A ∈ Rm×n et b ∈ Rm . On cherche un vecteur

x ∈ Rn tel que Ax = b, ce qui peut ou non être faisable. On considère donc les deux cas suivants.

23
24 Optimisation en finance - 2022/2023

a) S’il n’existe pas de solution à l’équation Ax = b, on résout

1 1 1
minimiser kAx − bk2 = xT AT Ax − bT Ax + bT b.
x∈Rn 2 2 2

b) S’il existe plusieurs solutions, on cherche celle de norme minimale en résolvant :

1 1
minimiser kxk2 = xT I n x s. c. Ax = b,
x∈Rn 2 2
où I n est la matrice identité dans Rn×n .

3.2 Résolution d’un programme quadratique

3.2.1 Résolution théorique
La théorie de la programmation quadratique est très similaire à celle de la programmation linéaire.
On peut notamment formuler le dual d’un programme quadratique, et en déduire des conditions
d’existence de solutions pour le problème de départ et son dual. On se contente ici de donner les
conditions d’optimalité, dites de KKT (Karush-Kuhn-Tucker).

Théorème 3.2.1 On considère le programme quadratique (3.1.1) sous l’hypothèse 3.1.1. Si x∗ ∈ Rn

est solution du problème, alors il existe y ∗ ∈ Rm et s∗ ∈ Rn tels que
−Hx∗ + AT y ∗ + s∗ = g


 Ax∗

= b


x ∗ ≥ 0 (KKT-Quad)


 s ∗ ≥ 0

 ∗ ∗
xi si = 0 ∀i = 1, . . . , n.
On notera que les conditions (KKT-Quad) sont quasiment identiques à celles pour la program-
mation linéaire (KKT-Lin). La seule différence ˚’eside dans la présence d’un terme en −Hx∗ dans la
première condition, dû au caractère quadratique de la fonction.

3.2.2 Résolution algorithmique

Comme dans le cas des programmes linéaires, la résolution des programmes quadratiques se base sur
les conditions de KKT. Les techniques principales de résolution se divisent en deux catégories.

Méthodes de contraintes actives (active set) Ces méthodes peuvent être vues comme une
extension de l’algorithme du simplexe à la programmation quadratique. Ces méthodes cherchent à
déterminer l’ensemble des contraintes actives en la solution, c’est-à-dire les contraintes d’inégalité
qui sont satisfaites avec égalité en la solution. Dans le cas d’un programme quadratique en forme
standard pour lequel la solution est x∗ , on dira que la contrainte xi ≥ 0 est active en x∗ si x∗i = 0.
Une contrainte inactive (pour laquelle x∗i > 0) peut être ignorée pour déterminer la solution.
La méthode des contraintes actives utilise à chaque itération un ensemble d’indices Ik ⊂ {1, . . . , n},
et résout le problème
minimiserx∈Rn 12 xT Hx + g T x
s.c. Ax = b (3.2.1)
xi = 0 i ∈ Ik .
Optimisation en finance - 2022/2023 25

En fonction de la solution, voire de la réalisabilité du problème, le point calculé est conservé, et

l’ensemble Ik est mis à jour en ajoutant ou supprimant un élément, comme pour le simplexe.
Remarque 3.2.1 Les approches par contraintes actives sont notamment utilisées dans le solveur
d’Excel, ainsi que dans des routines de résolution de programmation quadratique présentes dans la
bibliothèque SciPy du langage Python.

Points intérieurs Les approches de points intérieurs pour la programmation quadratique procèdent
de manière identique à celles pour la programmation linéaire. Pour un problème en forme standard
tel que (3.1.1), il s’agit toujours de calculer une suite (xk , y k , sk ) telle que xk > 0 et sk > 0, et de
réduire la valeur de xT k sk progressivement. La valeur des prochains itérés est toujours calculée via
les deux premières conditions de KKT, exprimées comme un système linéaire en les variables.
Remarque 3.2.2 Les solveurs de points intérieurs pour la programmation quadratique sont utilisés
dans différentes bibliothèques Python, dont SciPy et cvxpy.
Pour terminer cette section, on notera que de nombreux solveurs sont capables d’exploiter une
structure particulière d’un programme quadratique. Par exemple, les problèmes aux moindres carrés
linéaires (cf l’exemple 3.1.1) bénéficient souvent de solveurs dédiés. La librairie cvxpy choisit au-
tomatiquement l’algorithme adapté à la structure du problème considéré.

3.3 Application : modèle de Markowitz

3.3.1 Principe
Le modèle de Markowitz, qui valut le prix Nobel d’économie à son auteur en 1990, consiste en la
construction d’un portefeuille qui réalise un compromis entre un risque réduit et un rendement moyen
élevé.
Le portefeuille peut être défini parmi un ensemble de n actifs qui présentent chacun une part
d’aléatoire, et donc un risque, sur une période d’investissement allant d’un instant t0 à un  instant
v1,0
t > t0 . On part ainsi de prix fixés à l’instant t0 , que l’on écrit sous la forme d’un vecteur v 0 =  ... 
 

vn,0
et on cherche à définir un portefeuille en prévision de l’instant t, pour lequel les prix seront les
v1,t
composantes d’un vecteur aléatoire v t =  ... . La décision de la construction du portefeuille est
 

vn,t
prise à l’instant t0 , alors que v t est inconnu. On suppose que l’on connaı̂t néanmoins des statistiques
sur le vecteur v t , de sorte à pouvoir optimiser une certaine mesure de qualité du portefeuille.
Mathématiquement, on note h ∈ Rn les différentes quantités d’actifs qui composent le porte-
feuille choisi. Les valeurs du portefeuille à t0 et à t correspondent à
w0 = v T
0 h et w = vT
t h.

En pratique, plutôt que de raisonner sur w et w0 , on raisonne sur les retours sur investissements,
définis via la normalisation suivante :
vi,t − vi,0 n

w − w0
rp = , r = ri = .
w0 vi,0 i=1
26 Optimisation en finance - 2022/2023

Par ailleurs, plutôt que de considèrer les quantités d’actifs h, on raisonne sur les pourcentages d’actifs
présents dans le portefeuille, que l’on concatène sous la forme d’un vecteur x ∈ Rn avec

hi vi,0
xi = ∈ [0, 1].
w0

Par construction, on a alors ni=1 xi = 1. De plus, lorsque l’on souhaite maximiser la valeur w = v T h
P
du portefeuille, cela revient à maximiser

w − w0 (v − v 0 )T h
rp = = = r T x,
w0 w0

où la dernière égalité s’obtient par

Pn n n
(v − v 0 )T h i=1 (vi − vi,0 )hi X (vi − vi,0 ) hi vi,0 X T
= = = ri xi = r T x.
w0 w0 vi,0 w0
i=1 i=1

On se demande alors quels problèmes d’optimisation peuvent être définis si l’on ne connaı̂t que
des statistiques sur le vecteur r (et donc sur les valeurs à venir des actifs), et à quel genre de
portefeuille on aboutit en résolvant ces problèmes

3.3.2 Problèmes d’optimisation

Les problèmes d’optimisation que nous allons définir se basent sur les statistiques suivantes :

• les moyennes {µi = E [ri ]}i=1,...,n , ou retours sur investissement moyens (par rapport à v 0 );

• les variances {σi2 = E (ri − E [ri ])2 }i=1,...,n ;

• les covariances définies pour tous (i, j) ∈ {1, . . . , n} par

E [(ri − E [ri ])(rj − E [rj ])]

σij = σji = .
σi σj

On notera µ = [µi ] et V = [σij ]; on a alors

µ = E rT x V = E (r − E [r])(r − E [r])T = E (r − µ)(r − µ)T .

On peut alors formuler les trois problèmes d’optimisation suivants :

a) Calcul de portefeuille de risque minimal avec retour moyen sur investissement garanti :

minimiserx∈Rn 12 xT V x
s.c. µT x ≥ µ̄ (3.3.1)
eT x = 1,

où e = [1 · · · 1]T et µ̄ ∈ R représente un retour sur investissement espéré. Ce problème est un

programme quadratique.
Optimisation en finance - 2022/2023 27

b) Calcul de portefeuille à retour moyen sur investissement maximal pour un niveau de

risque contrôlé :
maximiserx∈Rn µT x
2
s.c. 12 xT V x ≤ σ2 (3.3.2)
T
e x = 1,

où σ 2 borne le niveau de risque souhaité. Ce problème possède un objectif linéaire et des con-
traintes dont l’une est quadratique. Il ne s’agit pas d’un programme quadratique1

c) Approche de Markowitz

maximiserx∈Rn µT x − γ2 xT V x
(3.3.3)
eT x = 1,

où γ > 0 est un paramètre de pénalité qui permet de contrôler le poids du terme en −xT V x
dans la maximisation en l’introduisant dans l’objectif et non via une contrainte.

On notera que la dernière formulation (3.3.3) est équivalente au programme quadratique en forme
standard :
minimiserx∈Rn γ2 xT V x − µT x
(3.3.4)
eT x = 1.
La formulation (3.3.4) est un outil de base de calcul de portefeuille qui prend en compte un risque.
La valeur de γ représente un compromis entre le retour moyen sur investissement µT x et la volatilité
xT V x. Lorsque γ tend vers 0, on tend à minimiser −µT x, et donc à maximiser uniquement le
retour moyen sur investissement; à l’inverse, lorsque γ tend vers ∞, on tend à minimiser xT V x
uniquement, et donc à rechercher un portefeuille de risque minimal (cf Section 3.5).
Plus globalement, les modèles définis plus haut peuvent être liés, comme le montre le résultat
suivant.

Proposition 3.3.1 Sous les définitions de cette section, on suppose que V est inversible et que la
T V −1 e
quantité µ̄ utilisée dans la formulation (3.3.4) vérifie µ̄ > µeT V ∗
−1 . Alors, si x est une solution de
e
2 ∗
la formulation (3.3.4), il existe σ et γ (qui dépendent de µ̄) tels que x est également une solution
des formulations (3.3.3) et (3.3.3).

Ce raisonnement s’applique aux trois formulations considérées, ainsi qu’à la formulation (3.3.4).

3.3.3 Analyse des modèles et de leurs solutions

Dans cette section,on fait l’hypothèse que la matrice V représentant les covariances des actifs est
inversible. Il s’agit alors d’une matrice symétrique définie positive, c’est-à-dire telle que xT V x > 0
si x 6= 0. Sous cette hypothèse, on peut montrer que le problème
1 T
minimiserx∈Rn 2x V x (3.3.5)
eT x = 1
1
Il s’agit cependant d’un programme conique, qui peut lui aussi être résolu par des approches de points intérieurs.
En revanche, cette résolution est plus complexe que celle d’un programme quadratique.
28 Optimisation en finance - 2022/2023

V −1 e
possède une unique solution x∗ = eT V −1 e
qui vérifie les conditions de KKT

V x∗ + ey ∗ = 0

eT x∗ = 1

pour un prix fictif y ∗ = − eT V1−1 e . Le portefeuille ainsi obtenu est noté

V −1 e
xR =
eT V −1 e
et s’appelle le portefeuille de risque minimum.
Dans le cadre du problème (3.3.4), on montre de manière similaire qu’il existe deux solutions du
problème particulières :

• le vecteur xR est solution, et minimise le risque parmi les solutions;

−1
• le vecteur xT = eTVV −1µµ , appelé portefeuille tangent (tangency portfolio), maximise le retour
moyen sur investissement parmi les solutions.

Le résultat suivant permet de lier ces portefeuilles particuliers aux autres solutions.

Théorème 3.3.1 (Two-fund theorem) Toute solution du problème (3.3.4) avec V inversible est
une combinaison des portefeuilles de risque minimum et tangent. Pour toute solution x∗ , il existe
ainsi α ∈ R tel que x∗ = αxR + (1 − α)xT .

3.4 Conclusion du chapitre 3

La programmation quadratique offre des possiblités de modélisation plus riches que la programmation
linéaire, en pouvant prendre en compte des concepts tels que les corrélations entre couples d’actifs.
Des algorithmes efficaces existent encore pour résoudre ces problèmes, notamment en se basant sur
leur structure.
L’application majeure de l’optimisation quadratique dans le cadre de la finance est due aux
problèmes d’optimisation de portefeuille impliquant un modèle moyenne-variance dit de Markowitz.
Dans ce cadre, la programmation quadratique est un outil indispensable pour prendre en compte des
aspects de risque via un terme quadratique dans l’objectif.

3.5 Exercices
Exercice 3 : Allocation à volatilité minimale
On considère un problème d’allocation de portefeuille sur trois actifs désignés par 1, 2, 3
dont le rendement est une variable aléatoire. On définit les quantités suivantes :

• σij est la corrélation entre les actifs i et j pour tout couple (i, j) ∈ {1, 2, 3}2 , avec
σii = 1 pour tout i = 1, 2, 3;
• C = [σij ] ∈ R3×3 est la matrice des corrélations;
• σi2 est la variance de l’actif i, et σi son écart-type;
Optimisation en finance - 2022/2023 29

• s ∈ R3 est le vecteur des écarts-types;

• V ∈ R3×3 est la matrice de covariance des actifs, donnée par V = CssT .

Le risque ou la volatilité d’un portefeuille x ∈ Rn sera mesuré via la quantité

3 3
1 T 1X XX
x Vx= Vii x2i + Vij xi xj .
2 2
i=1 i=1 j6=i

Le premier terme de la somme combine les variances relatives aux investissements dans
un actif, tandis que le second représente le risque dû aux corrélations entre actifs. Le
but de cet exercice est de trouver un portefeuille de risque minimal.

a) Formuler le problème en tant que programme quadratique, en supposant que le

portefeuille est exprimé en pourcentages (sommant à 1) et que ses composantes ne
peuvent être que positives ou nulles (long positions).
b) La résolution 2
 numérique de ce problème vue en séance donne comme solution
0.089
x∗ =  0  et comme valeur optimale f ∗ = 0.0012. Lorsque les contraintes
0.91
 
0.19
x ≥ 0 sont supprimées de la modélisation, on obtient en revanche x∗ = −0.14
0.94
et f ∗ = 0.0009, qui est une meilleure valeur de fonction. Pourquoi le fait d’enlever
une contrainte permet-il d’obtenir une meilleure valeur de l’objectif ?

Solution de l’exercice 3
a) Le problème s’écrit
minimiserx∈R3 12 xT V x
s.c. x1 + x2 + x3 = 1
x ≥ 0.

Note : ce problème est en forme standard.

b) Lorsque l’on supprime la contrainte x ≥ 0, on obtient

minimiserx∈R3 12 xT V x
s.c. x1 + x2 + x3 = 1.

L’ensemble admissible de ce problème contient (strictement) celui du problème écrit en question a).
Par conséquent, la valeur optimale de ce second problème est au moins aussi bonne que celle du
premier problème. Comme on s’autorise plus de liberté dans le choix des xi , on s’attend à ce que la
valeur optimale soit strictement meilleure, et c’est ce que l’on observe ici numériquement.
2
Cf les sources associées.
30 Optimisation en finance - 2022/2023

Exercice 4 : Ratio de Sharpe

Le ratio de Sharpe est une alternative au modèle de Markowitz qui combine le retour
moyen et la volatilité en une seule quantité, sous réserve que la matrice de covariance V
soit inversible. Avec les mêmes notations que celles de la section 3.3, on considère donc
le problème :
T
maximiserx∈Rn √µT x
x Vx (3.5.1)
s.c. eT x = 1
Ce problème n’est ni un programme linéaire, ni un programme quadratique. Le but de
cet exercice est néanmoins de trouver une reformulation équivalente à ce problème en
un programme quadratique.
a) On considère le changement de variable z = αx avec α > 0 et µT z = 1. Refor-
muler le problème (3.5.1) en un problème d’optimisation sur α et z où l’objectif
1
est de la forme f (z) , où f est une fonction que l’on précisera.
b) Pour toute fonction strictement positive f , minimiser f revient à maximiser √1f .
Par ailleurs, le cas α = 0 peut être incorporé au problème. En déduire alors que le
problème (3.5.1) se reformule comme le programme quadratique :
maximiserz∈Rn zTV z
α∈R
s.c. µT z = 1 (3.5.2)
eT z − α = 0
α ≥ 0.
c) D’après les conditions de KKT, on sait que (z ∗ , α∗ ) est solution du problème (3.5.2)
s’il existe y ∗ ∈ R2 et s∗ ∈ R tels que
−2V z ∗ + y1∗ µ + y2∗ e = 0
−y2∗ + s∗ = 0
µT z ∗ = 1
eT z ∗ − α∗ = 0
α∗ ≥ 0
α∗ s∗ = 0.
V −1 µ
Montrer alors que le portefeuille tangent x∗ = eT V −1 µ
définit z ∗ et α∗ qui forment
une solution du problème (3.5.2).

Solution de l’exercice 4
1
a) On utilise le changement de variable z = αx, qui donne x = α z. En remplaçant les x dans
l’expression de (3.5.1), on obtient :
1 T
maximiserz∈Rn r αµ z
1 T 1

α∈R
αz V αz
1 T
s.c. alpha e z =1
µT z = 1
α > 0,
Optimisation en finance - 2022/2023 31

où les deux dernières contraintes proviennent de la définition même de z et α. En simplifiant les α
dans la valeur de l’objectif, et en exploitant la contrainte µT z = 1, on aboutit à

maximiserz∈Rn √ 1
α∈R zT V z
s.c. T
e z−α =0
µT z = 1
α > 0,

b) D’après l’indication donnée dans la question, on sait que le problème obtenu en fin de question
a) est équivalent à
minimiserz∈Rn z T V z
α∈R
s.c. eT z − α = 0
µT z = 1
α > 0,
Il suffit ensuite de transformer la contrainte α > 0 en α ≥ 0 comme demandé par l’énoncé pour
arriver à (3.5.2).

c) Il s’agit d’utiliser les conditions de KKT pour obtenir une formule explicite pour α∗ et z ∗ en
fonction de celle de x∗ . On tire tout d’abord de la contrainte µT z ∗ = 1 le fait que

1 eT V −1 µ
α∗ = = .
µT x∗ µT V −1 µ
En utilisant cette formule dans la définition de z ∗ = α∗ x∗ , il vient

eT V −1 µ ∗ eT V −1 µ V −1 µ V −1 µ
z∗ = x = = .
µT V −1 µ µT V −1 µ eT V −1 µ µT V −1 µ
Il est ensuite aisé de vérifier algébriquement que les conditions de KKT sont vérifiées pour ces valeurs.
Chapitre 4

Optimisation stochastique en finance

Dans les chapitres précédents, nous avons soit négligé l’aléatoire en nous concentrant sur le rendement
en moyenne (cf chapitre 2), soit pris en compte cet aléatoire au travers de quantités statistiques
(rendement moyen et volatilité, cf chapitre 3 et plus particulièrement la section 3.3).
Dans ce chapitre, on va s’intéresser à des formulations dans lesquelles l’aléatoire est présent. On
présente tout d’abord un cadre général, en restant sur les formulations en deux temps, puis on décrit
une technique de résolution dans le cadre de l’approche par scénarios. On parle enfin de mesures de
risque, et de la façon dont elles généralisent les concepts déjà entrevus.

4.1 Formulation générale

4.1.1 Programmes stochastiques sans et avec recours
On considère une fenêtre de temps [0, 1]. On suppose que l’on doit prendre une décision au temps
t = 0 sous la forme d’un vecteur x ∈ Rn , mais que la qualité de cette décision est évaluée en
fonction d’une variable aléatoire ω, dont la valeur ne sera révélée qu’au temps t = 1. Un programme
stochastique classique vise à prendre la meilleure solution en moyenne.

Définition 4.1.1 (Programme stochastique) Un programme stochastique est un problème d’optimisation

de la forme
minimiserx∈Rn Eω [F (x, ω)]
(4.1.1)
s.c. x ∈ X ,
où ω ∈ Ω est une variable aléatoire, F : Rn × Ω → R est une fonction et X ⊂ Rn .

Un exemple de fonction F est r T x, où ω = r est un vecteur de rendement aléatoire. Dans ce

cas, l’objectif devient de maximiser le rendement moyen.
Il est fréquent qu’une partie de la décision prise à t = 0 ne dépende pas de la variable aléatoire.
Cela donne lieu à une modélisation particulière du problème d’optimisation, décrite ci-dessous.

Définition 4.1.2 Un programme stochastique avec recours est de la forme

minimiserx∈Rn f (x) + Eω [Q(x, ω)]

(4.1.2)
s.c. x ∈ X ,

32
Optimisation en finance - 2022/2023 33

où f : Rn → R est une fonction déterministe et Q : Rn × Ω → R est une fonction dite de recours
donnée par la solution d’un problème d’optimisation :
miny(ω)∈Rm g(y(ω), ω)
Q(vx, ω) := (4.1.3)
s. c. y(ω) ∈ Y(x, ω).
Le vecteur y(ω) représente la décision prise au temps t = 1, qui dépend de la valeur de la variable
aléatoire ω. Cette décision vise à minimiser une fonction de coût g : Rm × Ω → R sur un ensemble
Y(x, ω) ⊂ Rm . Cet ensemble contient toute dépendance de y(ω) vis-à-vis de x.
Dans le langage de la programmation stochastique, le problème (4.1.2) s’appelle également un
programme stochastique en deux temps (two-phase stochastic programming ). La décision de
recours (ou dans un second temps) y(ω) est fixe dès lors que la variable ω a été observée et que x
est fixé.
Remarque 4.1.1 Les notions présentées dans ce chapitre se généralisent sur des temps multiples
(on parle en anglais de multistage stochastic programming). Dans ce cours, on se contentera du cas
plus simple de la programmation en deux temps, qui illustre déjà les défis de modélisation.

4.1.2 Programme linéaire stochastique en deux temps

Définition 4.1.3 Un programme linéaire stochastique en deux temps est donné par
minimiserx∈Rn cT x + Eω [Q(x, ω)]
s.c. Ax = b (4.1.4)
x ≥ 0,
où les contraintes d’intervalle x ≥ 0 peuvent porter seulement sur un sous-ensemble des coordonnées
de x. La fonction Q est définie comme
miny(ω)∈Rm q(ω)T y(ω)
Q(vx, ω) := s. c. T (ω)x + N (ω)y(ω) = h(ω) (4.1.5)
y(ω) ≥ 0,
où q(ω) ∈ Rm , T (ω) ∈ R`×n , N (ω) ∈ R`×m , h(ω) ∈ R` , et les contraintes d’intervalle y(ω) ≥ 0
peuvent porter seulement sur un sous-ensemble des coordonnées de y(ω).
On notera qu’en l’absence de recours, le problème serait un programme linéaire en forme stan-
dard. Ici, la fonction objectif dépend d’un second programme linéaire (lui aussi en forme standard).
Cependant, on observera que les matrices T (ω) et N (ω), ainsi que les vecteurs q(ω) et h(ω),
peuvent être des fonctions non linéaires de ω.
La définition 4.1.3 met en avant le fait que la décision y(ω) est prise relativement à la valeur de
la variable ω (tandis que la décision x dite “dans un premier temps” n’en dépend pas). Il est courant
d’omettre cette dépendance pour obtenir une formulation simplifiée, de la forme suivante :
minimiser x∈Rn Eω cT x + q T y

y∈Rm
s.c. Ax = b
T x + Ny = h (4.1.6)
x≥0
y ≥ 0,
dans laquelle il est implicite que q, T , N et h dépendent de ω.
34 Optimisation en finance - 2022/2023

Exemple 4.1.1 (Problème de distribution) On achète une quantité x ≥ 0 d’un bien pour répondre
à une demande future incertaine. On considère que le coût d’achat à t = 0 par unité vaut cu , que le
coût d’achat à t = 1 (en cas de stock insuffisant) est de cp > cu et que le coût de stockage à t = 1
(en cas de surplus) est de cs . Si d > 0 est la valeur incertaine de la demande à t = 1, le coût final
de l’achat de quantité x est

F (x, d) = cu x + cp max(d − x, 0) + cs max(x − d, 0).

La formulation de ce problème en programme stochastique (au sens de la définition 4.1.1) donne

minimiserx∈R Ed [F (x, d)]

s.c. x ≥ 0,

tandis que celle avec recours s’écrit

minimiserx∈R cu x + Ed [Q(x, d)]

s.c. x ≥ 0,

avec Q(x, d) = cp max(d − x, 0) + cs max(x − d, 0). Cette quantité peut s’interpréter comme la
solution d’un programme linéaire

miny(d),z(d) cp y(d) + cs z(d)

s. c. y(d) ≥ d − x
Q(x, d) = z(d) ≥ x − d
y(d) ≥ 0
z(d) ≥ 0.

La reformulation avec dépendance implicite en d, à la manière de (4.1.6), s’écrit :

minimiserx∈R Ed [cu x + cp y + cs z]
y∈R
z∈R
s. c. x + y ≥ d
−x + z ≥ −d
x, y, z ≥ 0.

4.2 Approche par scénarios

4.2.1 Principe
L’approche par scénarios est l’une des techniques les plus fréquentes en programmation stochastique.
Elle consiste à n’envisager qu’un nombre fini de valeurs possibles pour la variable aléatoire ω, appelés
scénarios. On définit ainsi des scénarios {ω1 , . . . , ωK }Painsi que leurs probabilités d’occurrence
{p1 , . . . , pK }. Par conséquent, ces probabilités vérifient K
k=1 pk = 1.
L’intérêt de cette approche réside dans le fait qu’il est maintenant possible de réécrire un pro-
gramme stochastique de manière déterministe, en introduisant une variable pour chaque scénario
possible. Dans le cadre d’un programme en deux temps, cela signifie que l’on définit une variable y k
associée au scénario ωk .
Optimisation en finance - 2022/2023 35

Proposition 4.2.1 Sous l’hypothèse de K scénarios sur ω, le programme linéaire stochastique en

deux temps (4.1.6) s’écrit de manière déterministe comme
PK
minimiser x∈Rn cT x + T
k=1 pk q k y k
y 1 ,...,y K ∈Rm
s.c. Ax = b
T k x + N k y k = hk k = 1, . . . , K (4.2.1)
x≥0
y k ≥ 0 k = 1, . . . , K.

La structure très particulière du problème (4.2.1) va faciliter sa résolution. En effet, à x fixé, les
y k peuvent être calculés indépendamment en résolvant k programmes linéaires. C’est le principe de
la méthode décrite dans la section suivante.

4.2.2 Décomposition de Benders pour programmes linéaires stochastiques

Dans ce qui suit, on réécrit le problème (4.2.1) comme

minimiserx∈Rn cT x + K
P
k=1 Pk (x)
s.c. Ax = b (4.2.2)
x ≥ 0,

où chaque valeur Pk (x) est la valeur optimale d’un programme linéaire déterminé par x :

minyk pk q T
k yk
Pk (x) = s. c. N k y k = hk − T k x (4.2.3)
y k ≥ 0.

L’algorithme dit de décomposition de Benders procède itérativement en partant de x0 ∈ Rn ,

typiquement choisi comme

x0 ∈ argmin cT x|Ax = b, x ≥ 0 .

x∈Rn

Pour chaque itération i, l’algorithme calcule les valeurs {Pk (xi )} en résolvant les programmes linéaires
associés, pour lesquels on suppose que leurs duaux sont toujours réalisables. On se trouve alors dans
l’une des situations suivantes.

a) Soit le problème (4.2.3) possède une solution, et dans ce cas il existe uik tel que

∀x, Pk (x) ≥ [uik ]T (T k xi − T k x) + Pk (xi ).

b) Soit le problème est irréalisable, et il existe alors uik tel que

[uik ]T (hk − T k x) ≤ 0.

Dans les deux cas, il s’agit de contraintes linéaires (appelées coupes) que l’on peut rajouter au
problème utilisé pour calculer xi de sorte à obtenir un meilleur xi+1 . Ce vecteur sera en effet calculé
36 Optimisation en finance - 2022/2023

en résolvant
PK
minimiser x∈Rn cT x + k=1 Pk (x)
y 1 ,...,y K ∈Rm
s.c. Ax = b
Pk (x) ≥ [uik ]T (T k xi − T k x) + Pk (xi )
∀(i, k) tel que le problème associé à Pk (xi ) ait une solution, (4.2.4)
[uik ]T (hk − T k x) ≤ 0
∀(i, k) tel que le problème associé à Pk (xi ) soit irréalisable,
x≥0
y k ≥ 0 k = 1, . . . , K.

L’avantage de cette procédure est qu’elle ne requiert que de résoudre des programmes linéaires
(au nombre de contraintes croissant). On peut montrer que ce processus converge vers la solution
en un nombre fini d’itérations.

4.3 Mesures de risque

4.3.1 Motivation et définition générique
Dans le chapitre 3, et plus particulièrement dans la section 3.3, nous avons étudié une fonction
de coût mêlant la variance d’un vecteur de rendement ainsi que sa moyenne. Ce programme peut
s’écrire comme un programme stochastique, où la composante stochastique est le rendement. On
obtient ainsi
minimiserx∈Rn f (r T x)
(4.3.1)
s.c. eT x = 1
avec
γ
f (t) = σr2 (t) − Er [t] , σvr
2
(t) = Er t2 − Er [t]2 .

2
A travers le terme de variance, f incorpore une information liée au risque du portefeuille. Plus
généralement, les fonctions de ce type sont appelées des mesures de risque.

Remarque 4.3.1 L’utilisation, déjà vue au chapitre (2), du rendement moyen comme mesure conduit
à un problème dont le résultat sera neutre au risque ( risk neutral), par opposition aux autres mesures
de risque, qui elles seront attentives au risque ( risk averse).

4.3.2 VaR et CVaR

L’utilisation de la variance présente l’inconvénient de diminuer l’investissement dans des actifs qui
peuvent prendre des valeurs extrêmes (et donc avoir une forte variance), même si cela n’arrive qu’avec
une faible probabilité. Il est possible de définir d’autres mesures de risque qui soient moins sensibles
à cela. C’est notamment le but de la valeur à risque (value-at-risk), définie ci-dessous et popularisée
par J.P. Morgan.

Définition 4.3.1 Soit z une valeur aléatoire et α ∈ (0, 1) un niveau de sûreté. La valeur à risque
α de z est la valeur δ telle que
P (z ≥ δ) = 1 − α. (4.3.2)
On note alors VaRα [z] = δ.
Optimisation en finance - 2022/2023 37

Exemple 4.3.1 i) Si z ∼ N (µ, σ 2 ), alors VaR0.99 [z] = µ + 2.33σ.

ii) Si z ∈ {z
P1 , dots, zK } avec P (z = zk ) = pk , alors VaRα [z] = zJ , où J est le plus petit entier
tel que K k=J pk ≥ 1 − α.

On peut ainsi formuler des problèmes d’optimisation où l’on cherche à minimiser la valeur à risque,
ce qui donne généralement des solutions plus robustes aux comportements extrêmes qu’en utilisant
la variance. Dans le cas d’une approche par scénarios, on retombe à nouveau sur un programme
linéaire.

Valeur à risque conditionnelle L’un des inconvénients de la valeur à risque est qu’il ne s’agit pas
d’une mesure de risque cohérente, car VaRα [z + y] 6≤ VaRα [z] + VaRα [y] en général. Cela signifie
que diversifier un portefeuille n’apporte pas de robustesse au sens de la valeur à risque. La variante
cohérente de la valeur à risque la plus répandue est définie ci-après.

Définition 4.3.2 Soit z une valeur aléatoire et α ∈ (0, 1) un niveau de sûreté. La valeur à risque
conditionnelle α de z, notée CVaRα [z], est définie par

CVaRα [z] = Ez [z|z ≥ VaRα [z]] . (4.3.3)

L’interprétation de la valeur à risque conditionnelle est qu’elle exprime, pour une valeur à risque
donnée, de combien on excèdera cette valeur en moyenne. Il s’agit d’une mesure de risque cohérente.

Exemple 4.3.2 i) Si z ∼ N (µ, σ 2 ), alors VaR0.99 [z] = µ + 2.67σ.

ii) Si z ∈ {z1 , dots, zK } avec P (z = zk ) = pk , alors

K
1 X
CVaRα [z] = pk ,
1−α
k=J

PK
où J est le plus petit entier tel que k=J+1 pk ∈ [1 − α − pJ , 1 − α).

Le calcul de la valeur à risque conditionnelle n’est en général pas possible de manière explicite,
car il correspond à la résolution d’un programme linéaire stochastique en deux temps, comme le
montre le résultat ci-dessous.

Théorème 4.3.1 Si z une valeur aléatoire et α ∈ (0, 1), alors

h i
1
CVaRα [z] = minδ δ + 1−α Ez [max{z − δ, 0}]
1
minδ,u δ + 1−α Ez [u] (4.3.4)
= s.c. u ≥ z − δ
u ≥ 0.

En règle générale, l’utilisation de la valeur à risque conditionnelle conduira donc au moins à une
modélisation en programme stochastique avec recours.
38 Optimisation en finance - 2022/2023

4.4 Conclusion du chapitre 4

La prise en compte explicite du caractère aléatoire d’une composante de l’environnement (typique-
ment, le rendement d’un actif) conduit à des modélisations et donc des problèmes d’optimisation
plus complexes. Parmi ceux-ci, les programmes stochastiques en deux temps font partie des classes
les mieux comprises sur le plan théorique ainsi que sur le plan algorithmique. Les approches par
scénarios permettent également de décrire ces problèmes de manière déterministe. Dans le cas où
ces programmes sont aussi linéaires, des approches telles que la décomposition de Benders peuvent
exploiter la structure inhérente à la présence de scénarios.
L’un des atouts majeurs de la programmation stochastique est de pouvoir quantifier le risque de
certains investissements, de manière plus flexible que ce qui peut être fait avec la variance. Cela est
rendu possible grâce à la notion de mesure de risque, dont la valeur à risque et la valeur à risque
conditionnelle forment deux importantes instances.

4.5 Exercices
Exercice 5 : Déviation en moyenne absolue
Comme on l’a vu plus haut, l’utilisation de la variance en tant que mesure de risque
présente quelques inconvénients, notamment celui d’être sensible aux comportements
aberrants, et donc de conduire à des solutions conservatrices. On s’intéresse ici à une
autre métrique définie via la déviation en moyenne absolue.
Soit r ∈ Rn un vecteur de retours sur investissement aléatoire de moyenne µ = E [r].
La déviation en moyenne absolue de r est la fonction d : Rn → R définie par

∀x ∈ Rn , d(x) = E |(r − µ)T x| .

(4.5.1)

a) Supposons que r suive une loi discrète de valeurs {r 1 , . . . , r K } avec P (r = r k ) =

pk . Écrire alors le problème

minimiserx∈Rn d(x)
(4.5.2)
s.c. eT x = 1,

en fonction de {r k }k=1,...,K et {pk }k=1,...,K .

b) En introduisant la décomposition

(r k − µ)T x = wk+ − wk−

|(r k − µ)T x| = wk+ + wk− ,

où wk+ et wk− sont des quantités positives ou nulles (représentant la partie positive
et négative de (r k − µ)T x), formuler le problème (4.5.2) comme un programme
linéaire.
c) Donner un avantage pratique de résoudre un programme linéaire tel que celui for-
mulé dans cet exercice par rapport à la résolution de programmes quadratiques
impliquant la variance.
Optimisation en finance - 2022/2023 39

Solution de l’exercice 5
a) Par définition de l’espérance, on a dans le cas de cette question
K
X
d(x) = E |(r − µ)T x| = pk |(r k − µ)T x|.

i=1

Le problème s’écrit donc PK T

minimiserx∈Rn i=1 pk |(r k − µ) x|
T
s.c. e x = 1.

b) En utilisant la décomposition, on peut reformuler le problème en remplaçant l’objectif par

K
X K
X
pk |(r k − µ)T x| = pk (wk+ − wk− )
i=1 i=1

et en rajoutant les contraintes

(r k − µ)T x = wk+ + wk− .
On obtient donc le problème
PK
minimiser x∈Rn
+
i=1 pk (wk − wk− )
w+ ∈RK
w− ∈RK
s.c. (r k − µ)T x − wk+ − wk− = 0 k = 1, . . . , K,
eT x = 1.

c) Un programme linéaire peut se résoudre avec un plus grand nombre de variables qu’un programme
quadratique, car il existe des algorithmes très efficaces en grande dimension.

Exercice 6 : Utilité
On considère que l’on dispose d’un capital de w0 > 0 à investir pour construire un porte-
feuille. En tant que personne, on dispose d’une utilité qui nous est propre représentée
par une fonction U : R → R, que l’on va chercher à maximiser via la construction du
portefeuille. On note w = w0 (1 + r T x) le capital obtenu après investissement, dont on
suppose qu’il dépend d’un vecteur de rendement aléatoire.
Le problème de construction de portefeuille d’utilité maximale s’écrit comme suit :

maximiserx∈Rn Er [U (w)]
s. c. w = w0 (1 + r T x) (4.5.3)
eT x = 1.

On se concentre dans la suite sur le cas U : w 7→ U (w).

a) Si r = µ est déterministe, reformuler le problème (4.5.3) en un programme linéaire.

Utiliser pour cela le fait que maximiser log(f (x)) revient à minimiser f (x).
b) Généraliser le résultat précédent dans le cas où r ∈ {r 1 , . . . , r K } avec P (r = r k ) =
pk .
40 Optimisation en finance - 2022/2023

c) Si r suit une loi normale de moyenne µ et de matrice de covariance V , on a alors

c
Er [U (w)] = − (x − µ)T V (x − µ)
2

pour c > 0. Montrer que dans ce cas, le problème (4.5.3) se ramène à un problème
quadratique. Comparer le problème obtenu avec celui de gestion de portefeuille de
la forme proposée par Markowitz.

Solution de l’exercice 6
a) Dans le cas d’un vecteur r déterministe, on a

Er [U (w)] = U (w0 (1 + µT x)) = log(w0 (1 + µT x)).

Par conséquent, le problème (4.5.3) devient

maximiserx∈Rn log(w0 (1 + µT x))

s. c. eT x = 1.

En utilisant le fait que maximiser un logarithme revient à minimiser la fonction, une reformulation
équivalente de ce problème est
minimiserx∈Rn w0 µT x
s. c. eT x = 1,

qui est bien un programme linéaire.

b) Lorsque r suit une distribution discrète, la fonction objectif du problème (4.5.3) s’écrit

Er [U (w)] = Er U (w0 (1 + r T x))

K
X
= pk U (w0 (1 + r T
k x))
k=1
K
!
w0pk (1
Y
= log + rT
k x)
pk
.
k=1

Par conséquent, en utilisant le fait que maximiser un logarithme revient à minimiser la fonction
argument du logarithme, on arrive à
QK pk
minimiserx∈Rn k=1 w0 (1 + rT
k x)
pk

s. c. T
e x = 1,

On notera que ce problème n’est un programme linéaire que lorsque K = 1 et p1 = 1. 1

1
Sinon, il s’agit d’un programme dit géométrique, pour lequel des techniques telles que celles vues en cours peuvent
être développées.
Optimisation en finance - 2022/2023 41

c) En introduisant la première contrainte du problème (4.5.3) dans l’objectif, on aboutit au problème

maximiserx∈Rn − 2c (x − µ)T V (x − µ)
s. c. eT x = 1,

qui est équivalent à

c T
minimiserx∈Rn 2 (x − µ) V (x − µ)
s. c. eT x = 1.
Comme multiplier par une constante positive ne change pas les solutions d’un problème d’optimisation,
ce dernier problème est aussi équivalent à
1 T
minimiserx∈Rn 2 (x − µ) V (x − µ)
s. c. T
e x=1

En développant la fonction objectif, on obtient

1 1 T
(x − µ)T V (x − µ) = x V x − 2µT V x + µT V µ

2 2
1 T 1
= x V x − µT V x + µT V µ.
2 2
Le dernier terme étant constant, il n’importe pas dans le processus de minimisation. Au final, on
obtient donc le problème
minimiserx∈Rn 12 xT V x − µT V x
s. c. eT x = 1.
Ce problème ressemble au problème d’allocation de Markowitz (avec γ = 1). Cependant, au lieu
d’avoir un terme en −µT x qui tend à maximiser le rendement, on a ici un terme en −µT V x, qui
tend à maximiser une version normalisée du rendement moyen.
Bibliographie

[1] J. R. Birge and F. Louveaux. Introduction to Stochastic Programming. Springer Series in

Operations Research and Financial Engineering. Springer, New York, second edition, 2011.

[2] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, Cambridge,
United Kingdom, 2004.

[3] G. Cornuéjols, J. Peña, and R. Tütüncü. Optimization Methods in Finance. Cambridge University
Press, Cambridge, United Kingdom, second edition, 2018.

42
Annexe A

Bases mathématiques

A.1 Éléments d’algèbre linéaire

Les fondements mathématiques de l’optimisation se trouvent dans l’analyse réelle, et en partic-
ulier dans le calcul différentiel. Les structures d’algèbre linéaire dans Rn jouent cependant un rôle
prépondérant en optimisation (et en sciences des données). Cette section regroupe les résultats de
base qui seront utilisés dans le cours.
Pour approfondir ces notions, on pourra consulter les liens suivants :

• https://www.ceremade.dauphine.fr/∼carlier/polyalgebre.pdf (en français);

• http://vmls-book.stanford.edu/vmls.pdf (Chapitres 1 à 3, en anglais).

A.1.1 Algèbre linéaire vectorielle

On considèrera toujours l’espace des vecteurs Rn muni de sa structure d’espace vectoriel normé de
dimension d. On définit donc les opérations suivantes :

• Pour tous x, y ∈ Rn , la somme des vecteurs x et y est notée x + y = [xi + yi ]1≤i≤d ;

n
• Pour tout λ ∈ R, on définit λx = λ · x = [λxi ]1≤i≤d . Dans ce contexte, un tel réel λ sera
appelé un scalaire.

A l’aide de ces opérations, nous pouvons donc construire des combinaisons Plinéaires de vecteurs
de Rn dont le résultat sera un vecteur de Rn , à savoir des vecteurs de la forme pi=1 λi xi , où xi ∈ Rn
et λi ∈ R pour tout i = 1, . . . , p.
Pour ce qui est de l’espace des matrices Rn×d , on peut également le munir d’une structure
d’espace vectoriel normé de dimension nd. On définit donc les opérations suivantes :

• Pour tous A, B ∈ Rn×d , la somme des matrices A et B est notée A + B = [Aij + B ij ] 1≤i≤d ;
1≤j≤d
n
• Pour tout scalaire λ ∈ R, on définit λA = λ · A = [λAij ]1≤i≤n .
1≤j≤d

Définition A.1.1 Un ensemble S ⊆ Rn vérifiant les conditions

1. 0d ∈ S;

43
44 Optimisation en finance - 2022/2023

2. ∀(x, y) ∈ S, x + y ∈ S;

3. ∀x ∈ S, ∀λ ∈ R, λx ∈ S.

s’appelle un sous-espace vectoriel de Rn .

Définition A.1.2 Soient x1 , . . . , xp p vecteurs de Rn . Le sous-espace engendré par les vecteurs

x1 , . . . , xp , noté vect(x1 , . . . , xp ), est le sous-espace vectoriel
p
( )
X
vect(x1 , . . . , xp ) := x = αi xi αi ∈ R ∀i .
i=1

On rappelle ensuite les différentes propriétes notables des familles de vecteurs.

Définition A.1.3 • Une famille libre {xi }ki=1 de vecteurs de Rn est telle que les vecteurs sont
Pk
linéairement indépendants : pour tous scalaires λ1 , . . . , λk tels que i=1 λi xi = 0, alors
λ1 = · · · = λk = 0. On a nécessairement k ≤ n.

• Une famille liée est une famille de vecteurs qui n’est pas libre.

• Une famille génératrice de vecteurs de Rn est un ensemble de vecteurs {xi } tel que le sous-
espace engendré par ces vecteurs soit égal à Rn .

• Une base de Rn est une famille de vecteurs {xi }ni=1 qui est à la fois libre et génératrice. Tout
vecteur de Rn s’écrit alors de manière unique comme combinaison linéaire des xi . Toute base
de Rn comporte exactement n vecteurs.

Comme la taille d’une base de Rn est n, on dit que cet espace vectoriel est de dimension n. En
conséquence, la dimension d’un sous-espace vectoriel est au plus n.
Pn T
Exemple A.1.1 Tout vecteur x de Rn s’écrit x = i=1 xi ei , où ei = [0 · · · 0 1 0 · · · 0] est le
i-ème vecteur de la base canonique (le coefficient 1 se trouvant en i-ème position).

Norme et produit scalaire L’utilisation d’une norme, et du produit scalaire associé, permet de
mesurer les distances entre vecteurs, ce qui sera particulièrement utile pour montrer la convergence
d’une suite de points générés par un algorithme vers une solution d’un problème d’optimisation.

Définition A.1.4 La norme euclidienne k · k sur Rn est définie pour tout vecteur x ∈ Rn par
v
u n
uX
kxk := t x2i .
i=1

Remarque A.1.1 Il s’agit bien d’une norme, car elle vérifie les quatres axiomes d’une norme :

1. ∀x, y ∈ Rn , kx + yk ≤ kxk + kyk;

2. kxk = 0 ⇔ x = 0Rn ;

3. ∀x, kxk ≥ 0;
Optimisation en finance - 2022/2023 45

4. ∀x ∈ Rn , ∀λ ∈ R, kλxk = |λ|kxk.

On dira qu’un vecteur x ∈ Rn est unitaire si kxk = 1.

Définition A.1.5 Pour tous vecteurs x, y ∈ Rn , le produit scalaire dérivé de la norme euclidienne
est une fonction de x et y, notée xT y, et définie par
n
X
T
x y := x i yi .
i=1

Deux vecteurs x et y tels que xT y = 0 seront dits orthogonaux.

On notera en particulier que y T x = xT y. Ce produit scalaire définit donc un “produit” entre

un vecteur ligne et un vecteur colonne.

Proposition A.1.1 Soient x et y deux vecteurs de Rn . Alors, on a les propriétés suivantes :

i) |x + yk2 = kxk2 + 2xT y + kyk2 ;

ii) kx − yk2 = kxk2 − 2xT y + kyk2 ;

1
iii) kxk2 + kyk2 = kx + yk2 + kx − yk2 ;

4

iv) Inégalité de Cauchy-Schwarz :

∀x, y ∈ Rn , xT y ≤ kxkkyk.

Remarque A.1.2 La dernière inégalité est un résultat très important, qui s’utilise aussi bien en
algèbre linéaire qu’en analyse fonctionnelle. Comme on le verra, elle apparaı̂t également dans la
preuve des inégalités de Taylor, qui sont fondamentales en optimisation.

A.1.2 Algèbre linéaire matricielle

Sur les espaces matriciels, on définit également un produit matriciel entre matrices de dimensions
compatibles. Pour toutes matrices A ∈ Rm×n et B ∈ Rn×p , la matrice produit AB est définie
comme la matrice C ∈ Rm×p telle que
n
X
∀i = 1, . . . , m, ∀j = 1, . . . , p, C ij = Aik B kj .
k=1

Par analogie, le produit d’une matrice A ∈ Rm×n avec un vecteur x ∈ Rn sera le vecteur y ∈ Rm
donné par
n
X
∀i = 1, . . . , m, yi = Aij xj .
j=1

Remarque A.1.3 On notera que la notation du produit scalaire sur Rn correspond au produit de
deux matrices de taillle 1 × n et n × 1, dont le résultat est une matrice 1 × 1, c’est-à-dire un scalaire.
46 Optimisation en finance - 2022/2023

Lorsque l’on travaille avec des matrices, on s’intéresse généralement aux sous-espaces définis
ci-dessous.

Définition A.1.6 (Sous-espaces matriciels) Soit une matrice A ∈ Rm×n , on définit les deux sous-
espaces suivants :
• Le noyau de A est le sous-espace vectoriel

ker(A) := {x ∈ Rn | Ax = 0m }

• L’image de A est le sous-espace vectoriel

Im(A) := {y ∈ Rm | ∃x ∈ Rn , y = Ax}

La dimension de ce sous-espace vectoriel s’appelle le rang de A. On la note rang(A) et on a

rang(A) ≤ min{m, n}.

Théorème A.1.1 (Théorème du rang) Pour toute matrice A ∈ Rm×n , on a

dim(ker(A)) + rang(A) = n.

Définition A.1.7 (Normes matricielles) On définit sur Rm×n la norme d’opérateur k·k et la norme
de Frobenius k · kF par

:= maxx∈Rn kAxk


 kAk kxk = max x∈R kAxk
n

 x6=0n kxk=1
∀A ∈ Rm×n , rP
 2
 kAkF := 1≤i≤m Aij .


1≤j≤n

Définition A.1.8 (Matrice symétrique) Une matrice carrée A ∈ Rn×n est dite symétrique si elle
vérifie AT = A.
L’ensemble des matrices symétriques de taille n × n sera noté S n .

Définition A.1.9 (Matrice inversible) Une matrice carrée A ∈ Rn×n est dite inversible s’il existe
B ∈ Rn×n telle que BA = AB = I n (où l’on rappelle que I n désigne la matrice identité de Rn×n ).
Si elle existe, une telle matrice B est unique : elle est appelée l’inverse de A et on la note A−1 .

Définition A.1.10 (Matrice (semi-)définie positive) Une matrice carrée A ∈ Rn×n symétrique
est dite semi-définie positive si
∀x ∈ Rn , xT Ax ≥ 0,
ce que l’on notera A 0.
Une telle matrice est dite définie positive lorsque xT Ax > 0 pour tout vecteur x non nul, ce
que l’on notera A 0.

Définition A.1.11 (Matrice orthogonale) Une matrice carrée P ∈ Rn×n est dite orthogonale si
P T = P −1 .
Par extension, on dira que Q ∈ Rm×n avec m ≤ n est orthogonale si QQT = I m (les colonnes
de Q sont donc orthonormées dans Rm ).
Optimisation en finance - 2022/2023 47

On notera que lorsque Q ∈ Rn×n est une matrice orthogonale, alors sa transposée QT est
également orthogonale (ce résultat n’est pas vrai pour une matrice rectangulaire). On utilisera
fréquemment la propriété des matrices orthogonales énoncée ci-dessous.

Lemme A.1.1 Soit une matrice A ∈ Rm×n et U ∈ Rm×m , V ∈ Rn×n des matrices orthogonales,
respectivement de Rm×m et Rn×n . On a

kAk = kU Ak = kAV k et kAkF = kU AkF = kAV kF ,

c’est-à-dire que la multiplication par une matrice orthogonale ne modifie pas la norme d’opérateur.

Par corollaire immédiat du lemme précédent, on note qu’une matrice Q ∈ Rm×n orthogonale
√
avec m ≤ n vérifie nécessairement kQk = 1 et kQkF = m.

Définition A.1.12 (Valeur propre) Soit une matrice A ∈ Rn×n . On dit que λ ∈ R est une valeur
propre de A si
∃v ∈ Rn , v 6= 0n , Av = λv.
Le vecteur v est appelé un vecteur propre associé à la valeur propre λ. L’ensemble des valeurs
propres de A s’appelle le spectre de A.

Le sous-espace engendré par les vecteurs propres associés à la même valeur propre d’une matrice
s’appelle un sous-espace propre. Sa dimension correspond à l’ordre de multiplicité de la valeur propre
relativement à la matrice.

Proposition A.1.2 Pour toute matrice A ∈ Rn×n , on a les propriétés suivantes :

• La matrice A possède n valeurs propres complexes mais pas nécessairement réelles.

• Si la matrice A est semi-définie positive (respectivement définie positive), alors ses valeurs
propres sont réelles positives (respectivement strictement positives).

• Le noyau de A est engendré par les vecteurs propres associés à la valeur propre 0.

Théorème A.1.2 (Théorème spectral) Toute matrice carrée A ∈ Rn×n symétrique admet une
décomposition dite spectrale de la forme :

A = P ΛP −1 ,

où P ∈ Rn×n est une matrice orthogonale , dont les colonnes p1 , . . . , pn forment une base or-
thonormée de vecteurs propres, et Λ ∈ Rn×n est une matrice diagonale qui contient les n valeurs
propres de A λ1 , . . . , λn sur la diagonale.

Il est à noter que la décomposition spectrale n’est pas unique. En revanche, l’ensemble des
valeurs propres est unique, que l’on prenne en compte les ordres de multiplicité ou non.
Géométriquement parlant, on voit ainsi que, pour tout vecteur x ∈ Rn décomposé dans la base
des pi que l’on multiplie par A, les composantes de ce vecteur associées aux plus grandes valeurs
propres1 seront augmentées, tandis que celles associées aux valeurs propres de petite magnitude
seront réduites (voire annihilées dans le cas d’une valeur propre nulle).
1
On parle ici de plus grandes valeurs propres en valeur absolue, ou magnitude.
48 Optimisation en finance - 2022/2023

Lien avec la décomposition en valeurs singulières Soit une matrice rectangulaire A ∈ Rm×n :
dans le cas général, les dimensions de la matrice diffèrent, et on ne peut donc pas parler de valeurs
propres de la matrice A. On peut en revanche considérer les deux matrices

AT A ∈ Rn×n et AAT ∈ Rm×m .

Ces matrices sont symétriques réelles, et par conséquent diagonalisables. On peut se baser sur cette
propriété pour obtenir une décomposition en valeurs singulières de A (ou SVD d’après l’acronyme
anglais).

Vous aimerez peut-être aussi

Modèles Stochastiques Et Applications À La Finance PDF
Pas encore d'évaluation
Modèles Stochastiques Et Applications À La Finance PDF
147 pages
Modèles de Régression Linéaire Appliquée
100% (1)
Modèles de Régression Linéaire Appliquée
127 pages
Methodes Mathematiques Finance
Pas encore d'évaluation
Methodes Mathematiques Finance
66 pages
Propriétés et Théorèmes des Vecteurs Gaussiens
Pas encore d'évaluation
Propriétés et Théorèmes des Vecteurs Gaussiens
8 pages
M2 Cours
Pas encore d'évaluation
M2 Cours
84 pages
Diagonalisation
Pas encore d'évaluation
Diagonalisation
22 pages
Cours Survie
Pas encore d'évaluation
Cours Survie
59 pages
CoursSeriesTemp Chap1
Pas encore d'évaluation
CoursSeriesTemp Chap1
58 pages
Travaux Dirig Es: Mod' Eles de Dur Ee S Eance N 2 Du 30 Novembre 2015 - Corrig e
Pas encore d'évaluation
Travaux Dirig Es: Mod' Eles de Dur Ee S Eance N 2 Du 30 Novembre 2015 - Corrig e
8 pages
Annales Correction PDF
Pas encore d'évaluation
Annales Correction PDF
42 pages
Introduction aux Techniques d'Enquête
Pas encore d'évaluation
Introduction aux Techniques d'Enquête
80 pages
Calcul Stochastique en Économie et Finance
Pas encore d'évaluation
Calcul Stochastique en Économie et Finance
93 pages
Calcul Stochastique en Finance
Pas encore d'évaluation
Calcul Stochastique en Finance
181 pages
Corrélation partielle et multicolinéarité
Pas encore d'évaluation
Corrélation partielle et multicolinéarité
37 pages
M1mmd MouvementBrownien Ibtjtgt v7 3
Pas encore d'évaluation
M1mmd MouvementBrownien Ibtjtgt v7 3
213 pages
Processus M2
100% (1)
Processus M2
184 pages
Processus Stochastiques en Finance
Pas encore d'évaluation
Processus Stochastiques en Finance
36 pages
Mathf 207 Seance 5 Corr
Pas encore d'évaluation
Mathf 207 Seance 5 Corr
9 pages
Evaluation Des Options Américaines (ATTALLAH Sabrina)
Pas encore d'évaluation
Evaluation Des Options Américaines (ATTALLAH Sabrina)
130 pages
TD3 2019
100% (1)
TD3 2019
5 pages
CC1L3 2007 Correction
Pas encore d'évaluation
CC1L3 2007 Correction
4 pages
EstimationCorrige PDF
Pas encore d'évaluation
EstimationCorrige PDF
30 pages
Méthodes de Monte Carlo Pour La Finance
Pas encore d'évaluation
Méthodes de Monte Carlo Pour La Finance
72 pages
TD Criteres2021corrige
Pas encore d'évaluation
TD Criteres2021corrige
8 pages
Maths Ing Fin PDF
Pas encore d'évaluation
Maths Ing Fin PDF
271 pages
Cours Langage R en Actuariat
100% (1)
Cours Langage R en Actuariat
52 pages
2023.examen Yy
Pas encore d'évaluation
2023.examen Yy
3 pages
Econométrie Var Quali
Pas encore d'évaluation
Econométrie Var Quali
84 pages
Chaines de Markov
Pas encore d'évaluation
Chaines de Markov
26 pages
Mathf 207 Seance 6 Corr
Pas encore d'évaluation
Mathf 207 Seance 6 Corr
6 pages
TD 1 2019-2020
100% (1)
TD 1 2019-2020
2 pages
14-Estimation Part
Pas encore d'évaluation
14-Estimation Part
13 pages
Variables Aléatoires Continues
100% (1)
Variables Aléatoires Continues
3 pages
Stat F 508
Pas encore d'évaluation
Stat F 508
157 pages
Introduction à l'Algèbre Linéaire
Pas encore d'évaluation
Introduction à l'Algèbre Linéaire
72 pages
EMV Cours 2 PDF
Pas encore d'évaluation
EMV Cours 2 PDF
68 pages
SERIES - TEMPORELLES - PDF 2 PDF
50% (2)
SERIES - TEMPORELLES - PDF 2 PDF
141 pages
Actuariat et Gestion des Risques
Pas encore d'évaluation
Actuariat et Gestion des Risques
67 pages
Décomposition Séries Temporelles
Pas encore d'évaluation
Décomposition Séries Temporelles
14 pages
La Décision Dans L'incertain
100% (1)
La Décision Dans L'incertain
98 pages
Statistiques avancées : modèles et propriétés
Pas encore d'évaluation
Statistiques avancées : modèles et propriétés
1 page
Tests Statistiques en 3ème EM
Pas encore d'évaluation
Tests Statistiques en 3ème EM
2 pages
TDs Estimation ENSAE
Pas encore d'évaluation
TDs Estimation ENSAE
42 pages
Statistiques Avancées pour Étudiants
Pas encore d'évaluation
Statistiques Avancées pour Étudiants
2 pages
Exercices sur les variables aléatoires
Pas encore d'évaluation
Exercices sur les variables aléatoires
2 pages
Exercices Théorie Des Jeux
Pas encore d'évaluation
Exercices Théorie Des Jeux
5 pages
Analyse de la régression linéaire
Pas encore d'évaluation
Analyse de la régression linéaire
31 pages
Exos Var Densite 2020-2021
Pas encore d'évaluation
Exos Var Densite 2020-2021
9 pages
Serie TD Proba 2020 2021 Gmec1 1
Pas encore d'évaluation
Serie TD Proba 2020 2021 Gmec1 1
8 pages
Modules Statistiques pour Data Science
Pas encore d'évaluation
Modules Statistiques pour Data Science
20 pages
Methodes Reduction Variance
Pas encore d'évaluation
Methodes Reduction Variance
78 pages
Slides Cours
Pas encore d'évaluation
Slides Cours
80 pages
TestsHypStatL3Mass1516 Exam
Pas encore d'évaluation
TestsHypStatL3Mass1516 Exam
19 pages
Méthodes de ré-échantillonnage en stats
Pas encore d'évaluation
Méthodes de ré-échantillonnage en stats
148 pages
Théorème de Cochran Et Applications en Statistiques
Pas encore d'évaluation
Théorème de Cochran Et Applications en Statistiques
4 pages
Econometrie Appliquee Avec R Part03 - Compress
Pas encore d'évaluation
Econometrie Appliquee Avec R Part03 - Compress
22 pages
Optimisation EA1
Pas encore d'évaluation
Optimisation EA1
130 pages
Poly Cours
Pas encore d'évaluation
Poly Cours
142 pages
Optimisation EA1
Pas encore d'évaluation
Optimisation EA1
130 pages
Optimisation pour l'Apprentissage
Pas encore d'évaluation
Optimisation pour l'Apprentissage
64 pages
Cours M1 Finance 2020-2021 (5) Betas
Pas encore d'évaluation
Cours M1 Finance 2020-2021 (5) Betas
15 pages
Qualitative
Pas encore d'évaluation
Qualitative
23 pages
Intro Fin Quant Slides Sem Dep 2020
Pas encore d'évaluation
Intro Fin Quant Slides Sem Dep 2020
123 pages
Les Retracements Et Speedlines - Formation Zonebourse
Pas encore d'évaluation
Les Retracements Et Speedlines - Formation Zonebourse
1 page
Cours M1 Finance 2020-2021 (7) Analyse Financière Et Choix de Portefeuilles
Pas encore d'évaluation
Cours M1 Finance 2020-2021 (7) Analyse Financière Et Choix de Portefeuilles
23 pages
L'analyse Fondamentale Est Incontournable: Chapitre 1
Pas encore d'évaluation
L'analyse Fondamentale Est Incontournable: Chapitre 1
18 pages
Chapitre 4 2 Simplexe
Pas encore d'évaluation
Chapitre 4 2 Simplexe
22 pages
Cours de Recherche Opérationnelle L3D
Pas encore d'évaluation
Cours de Recherche Opérationnelle L3D
44 pages
Plan Cours RO2021
Pas encore d'évaluation
Plan Cours RO2021
2 pages
Dualité en Recherche Opérationnelle
Pas encore d'évaluation
Dualité en Recherche Opérationnelle
20 pages
ROCours 2017
Pas encore d'évaluation
ROCours 2017
105 pages
TD Gpmi
Pas encore d'évaluation
TD Gpmi
8 pages
Chapitre 4 - Modèle de Transport
100% (1)
Chapitre 4 - Modèle de Transport
12 pages
Optimisation Discrète : Méthodes de Coupes
Pas encore d'évaluation
Optimisation Discrète : Méthodes de Coupes
106 pages
2 Dualite
Pas encore d'évaluation
2 Dualite
29 pages
Chapitre4-050121
Pas encore d'évaluation
Chapitre4-050121
22 pages
Flot Maximum: Cplex et Ford-Fulkerson
100% (1)
Flot Maximum: Cplex et Ford-Fulkerson
5 pages
Cours de Recherche Opérationnelle: Chapitre I: Programmation Linéaire Chapitre II: Résolution de Programme Linéaire P.L Par Le Solveur Excel
Pas encore d'évaluation
Cours de Recherche Opérationnelle: Chapitre I: Programmation Linéaire Chapitre II: Résolution de Programme Linéaire P.L Par Le Solveur Excel
12 pages
Devoir Graphe Et Opt Esie l3 2024
Pas encore d'évaluation
Devoir Graphe Et Opt Esie l3 2024
1 page
Notes de Recherche Opérationnelle SCAI
Pas encore d'évaluation
Notes de Recherche Opérationnelle SCAI
118 pages
Chap2 Notions de Bases de La Prog-Linéaire
Pas encore d'évaluation
Chap2 Notions de Bases de La Prog-Linéaire
23 pages
Cours RO PPT Partie Formulation
Pas encore d'évaluation
Cours RO PPT Partie Formulation
18 pages
Démonstrations Du Théorème Du Minimax
Pas encore d'évaluation
Démonstrations Du Théorème Du Minimax
4 pages
Introduction à la Gestion Budgétaire
Pas encore d'évaluation
Introduction à la Gestion Budgétaire
114 pages
3 AGE 2023 2024 PL Simplexe
Pas encore d'évaluation
3 AGE 2023 2024 PL Simplexe
42 pages
Cours R o Chapitre 1
Pas encore d'évaluation
Cours R o Chapitre 1
41 pages
Travaux Diriges Ro 24 - 25 Serie 2 Avec Solution 2024 - 2025
Pas encore d'évaluation
Travaux Diriges Ro 24 - 25 Serie 2 Avec Solution 2024 - 2025
5 pages
Exercices-Optimisation Linéaire Avec Solutions
100% (1)
Exercices-Optimisation Linéaire Avec Solutions
52 pages
10 FR - ES - Solides - Ex 47 - Cor - vs2
Pas encore d'évaluation
10 FR - ES - Solides - Ex 47 - Cor - vs2
2 pages
Problème de Transport
Pas encore d'évaluation
Problème de Transport
35 pages
Corrige 1
50% (2)
Corrige 1
5 pages
Contrôle de Gestion
Pas encore d'évaluation
Contrôle de Gestion
23 pages
Correction Examen RO 10-11
Pas encore d'évaluation
Correction Examen RO 10-11
8 pages
CH2 Recherche Opérationnelle
Pas encore d'évaluation
CH2 Recherche Opérationnelle
29 pages
Optimisation : Techniques et Applications
Pas encore d'évaluation
Optimisation : Techniques et Applications
63 pages
Mini Projet Recherche Operationnelle Programmation Dans C
Pas encore d'évaluation
Mini Projet Recherche Operationnelle Programmation Dans C
10 pages