Optimisation Différentiable

Compilé par Arnak DALALYAN

ENSAE Paris, 1A

28 janvier 2025
 Table des matières

1 Fondements de l’optimisation 9
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Définitions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Un problème de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Typologie des problèmes d’optimisation . . . . . . . . . . . . . . . . . . . . 12
1.5 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6 Gradient, différentielle et hessienne . . . . . . . . . . . . . . . . . . . . . . . 16
1.7 Convexité des fonctions différentiables . . . . . . . . . . . . . . . . . . . . . 19
1.8 Reconnaissance d’un minimum local . . . . . . . . . . . . . . . . . . . . . . 21
1.9 Conditions suffisantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.10 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.11 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.12 Résumé du Chapitre 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2 Algorithmes d’optimisation 33
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2 Méthode du nombre d’or . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3 Algorithme de dichotomie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.4 Descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.5 Méthode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.6 Résumé du Chapitre 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Table des matières Table des matières

3 Problèmes avec des contraintes d’égalité 49

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2 Points réguliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3 Condition de Lagrange et exemples . . . . . . . . . . . . . . . . . . . . . . 52
3.4 Directions admissibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.5 Preuve du Théorème de Lagrange . . . . . . . . . . . . . . . . . . . . . . . 57
3.6 Conditions du second ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.7 Résumé du Chapitre 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4 Problèmes avec des contraintes d’inégalité 65

4.1 Formulation du problème et définitions . . . . . . . . . . . . . . . . . . . . 65
4.2 Théorème de Karush-Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . 66
4.3 Méthode de résolution générale . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.4 KKT et convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5 Liste des questions de cours 75

Contenu prévisionnel des séances . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
 Table des figures

1.1 Un problème de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2 Minimum global versus minima locaux . . . . . . . . . . . . . . . . . . . . 14
1.3 Trajectoire du véhicule amphibie dans l’exemple 1. . . . . . . . . . . . . . . 25

2.1 Exemple d’une fonction unimodale . . . . . . . . . . . . . . . . . . . . . . . 34

2.2 Méthode du nombre d’or . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3 Méthode du nombre d’or . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4 Gradient descent algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.5 Méthode de Newton : un cas favorable, f ′′ ( x ) > 0 . . . . . . . . . . . . . . 44
2.6 Méthode de Newton : un cas défavorable, f ′′ ( x ) < 0 . . . . . . . . . . . . . 45

3.1 Solution graphique au problème (3.1). . . . . . . . . . . . . . . . . . . . . . 51

3.2 La surface représentant l’ensemble admissible de Example 3.2. . . . . . . . 52
3.3 La courbe représentant l’ensemble admissible de Example 3.3. . . . . . . . 52
3.4 Illustration de Example 3.8 dans le cas n = 2. . . . . . . . . . . . . . . . . . 61
 Preface

L’objectif de ces notes de cours est de fournir aux étudiants une introduction concise à
l’optimisation. La majeure partie de ce document est empruntée aux manuels suivants :

[ChZ] Edwin K. P. Chong, Stanislaw H. Zak, An Introduction to Optimization, 4e édi-

tion, Volume 76 de la série Wiley en mathématiques discrètes et optimisation, John
Wiley & Sons, 2013.
[NW] Jorge Nocedal, Stephen J. Wright, Numerical Optimization, Springer, 2006.
[HL] Frederick S. Hillier, Gerald J. Lieberman, Introduction to Operations Research, 10e
édition, McGraw-Hill Education, 2015.

Les lecteurs désirant obtenir une exposition plus complète sur divers sujets en opti-
misation sont renvoyés à ces manuels.
 Fondements de l’optimisation en
1
dimension finie

Ce chapitre est consacré à l’introduction des concepts de base et des outils mathéma-
tiques utilisés en optimisation (continue).

1.1 Introduction

Les individus optimisent. Les investisseurs cherchent à créer des portefeuilles qui
évitent les risques excessifs tout en atteignant un taux de rendement élevé. Les fabri-
cants visent une efficacité maximale dans la conception de leurs processus de produc-
tion.
La nature optimise. Les systèmes physiques tendent vers un état d’énergie minimale.
Les rayons lumineux suivent des trajectoires qui minimisent leur temps de déplace-
ment.
L’optimisation est un outil important en science de la décision et dans l’analyse des
systèmes physiques. Pour utiliser cet outil, nous devons d’abord identifier un objectif,
une mesure quantitative de la performance du système étudié. Cet objectif pourrait être
le profit, le temps, l’énergie potentielle, ou toute quantité pouvant être représentée par
Définitions de base Fondements de l’optimisation

un nombre unique. L’objectif dépend de certaines caractéristiques du système, appelées

variables ou inconnues. Notre but est de trouver des valeurs pour ces variables qui
optimisent l’objectif. Souvent, les variables sont restreintes ou contraintes d’une certaine
manière. Par exemple, des quantités telles que le taux d’intérêt sur un prêt ne peuvent
pas être négatives.
Le processus d’identification de l’objectif, des variables et des contraintes pour un
problème donné est connu sous le nom de modélisation. La construction d’un modèle
approprié est la première étape, parfois la plus importante, du processus d’optimisation.
Si le modèle est trop simpliste, il ne fournira pas d’informations utiles sur le problème
pratique. S’il est trop complexe, il peut être trop difficile à résoudre.
Une fois que le modèle a été formulé, un algorithme d’optimisation peut être uti-
lisé pour trouver sa solution, généralement à l’aide d’un ordinateur. Il n’y a pas d’al-
gorithme d’optimisation universel, mais plutôt une collection d’algorithmes, chacun
adapté à un type particulier de problème d’optimisation. Le choix de l’algorithme ap-
proprié pour une application spécifique incombe souvent à l’utilisateur. Ce choix est
crucial, car il peut influencer la rapidité ou la lenteur de la résolution du problème,
voire déterminer si une solution est trouvée ou non.
Après l’application d’un algorithme d’optimisation au modèle, nous devons être ca-
pables de reconnaître si une solution a été trouvée. Dans de nombreux cas, il existe des
expressions mathématiques élégantes appelées conditions d’optimalité pour vérifier si
l’ensemble des valeurs de variables fourni par l’algorithme est effectivement la solution
du problème.

1.2 Définitions de base

Dans ce chapitre, nous examinons le problème d’optimisation suivant :

minimiser f ( x)
(1.1)
sous contrainte x ∈ Ω.

La fonction f : R p → R que nous souhaitons minimiser est une fonction réelle appelée
la fonction-objectif ou la fonction-coût. Le vecteur x est un vecteur de variables de di-
mension p : x = [ x1 ; x2 ; . . . ; x p ]⊤ ∈ R p . Les variables x1 , x2 , . . . , x p sont souvent appelées
variables de décision. L’ensemble Ω est un sous-ensemble de R p appelé l’ensemble de
contraintes ou l’ensemble admissible.
Le problème d’optimisation ci-dessus peut être vu comme un problème de décision
qui consiste à trouver le vecteur x «optimal» des variables de décision parmi tous les
vecteurs possibles dans Ω. Par «optimal», nous entendons celui qui conduit à la plus

10
Un problème de transport Fondements de l’optimisation

petite valeur de la fonction-objectif. Ce vecteur est appelé le minimiseur de f sur Ω. Il

est possible qu’il puisse y avoir plusieurs minimiseurs. Dans ce cas, trouver un élément
quelconque de l’ensemble des minimiseurs suffira.
Il existe également des problèmes d’optimisation qui nécessitent la maximisation de
la fonction-objectif, auquel cas nous recherchons des maximiseurs. Les problèmes de
maximisation peuvent être représentés de manière équivalente sous la forme de mini-
misation, car maximiser f est équivalent à minimiser − f . Par conséquent, nous pouvons
limiter notre attention, sans perte de généralité, aux problèmes de minimisation.
Le problème ci-dessus est une forme générale d’un problème d’optimisation sous
contraintes, car les variables de décision sont contraintes à appartenir à l’ensemble de
contraintes Ω. Si Ω = R p , alors nous appelons (1.1) un problème d’optimisation sans
contraintes.
Souvent, l’ensemble de contraintes Ω prend la forme

Ω = x ∈ R p : h( x) = 0, g( x) ⩽ 0 ,


où h et g sont des fonctions données. Nous appelons de telles contraintes des contraintes
fonctionnelles (respectivement d’égalité et d’inégalité).

1.3 Un problème de transport

Nous commençons par un exemple largement simplifié d’un problème qui pourrait
se poser dans le domaine de la fabrication et du transport. Une entreprise chimique
dispose de 2 usines F1 et F2 ainsi que d’une douzaine de points de vente R1 , R2 , . . . , R12 .
Chaque usine Fi peut produire ai tonnes d’un certain produit chimique chaque semaine ;
ai est appelée la capacité de l’usine. Chaque point de vente R j a une demande hebdo-
madaire connue de b j tonnes du produit. Le coût d’expédition d’une tonne du produit
de l’usine Fi au point de vente R j est cij .
Le problème consiste à déterminer la quantité de produit à expédier de chaque usine
vers chaque point de vente afin de satisfaire toutes les exigences et de minimiser les
coûts. Les variables du problème sont xij , i = 1, 2, j = 1, . . . , 12, où xij est le nombre de
tonnes du produit expédiées de l’usine Fi vers le point de vente R j ; voir la Fugure 1.1.
Nous pouvons formuler le problème comme suit :

11
Typologie des problèmes d’optimisation Fondements de l’optimisation

F IGURE 1.1 – Un problème de transport

minimiser ∑ cij xij (1.2)

ij
12
sous contrainte ∑ xij ⩽ ai , i = 1, 2,
j =1
2
∑ xij ⩾ bj , j = 1, . . . , 12,
i =1
xij ⩾ 0, i = 1, 2 j = 1, . . . , 12.

Ce type de problème est connu sous le nom de problème de programmation linéaire,

car la fonction-objectif et les contraintes sont toutes des fonctions linéaires des variables
d’optimisation xi,j . Dans un modèle plus pratique, nous inclurions également des coûts
liés à la fabrication et au stockage du produit. Il peut y avoir des remises sur le vo-
lume dans la pratique pour l’expédition du produit ; par exemple, le coût (1.2) pourrait
être représenté par ∑ij cij δ + xij , où δ > 0 est une petite redevance. Dans ce cas, le
p

problème est un programme non linéaire car la fonction-objectif est non linéaire.

1.4 Typologie des problèmes d’optimisation

Les problèmes d’optimisation sont catégorisés selon divers critères. Dans cette sec-
tion, nous passons brièvement en revue les critères les plus fréquemment utilisés.

12
1.4.1 Continu versus discret Fondements de l’optimisation

1.4.1 Continu versus discret

Dans certains problèmes d’optimisation, les variables n’ont de sens que si elles prenn-
ent des valeurs entières. Par exemple, une variable xi pourrait représenter le nombre
d’usines de type i que doit construire un fournisseur d’électricité au cours des 5 pro-
chaines années, ou elle pourrait indiquer si une usine particulière doit être située dans
une ville donnée. La formulation mathématique de tels problèmes inclut des contraintes
d’intégralité, qui ont la forme xi ∈ Z, où Z est l’ensemble des entiers, ou des contraintes
binaires, qui ont la forme xi ∈ {0, 1}. Les problèmes de ce type sont appelés des pro-
blèmes de programmation entière. Si certaines des variables du problème ne sont pas
restreintes à être des variables entières ou binaires, on les appelle parfois des problèmes
de programmation entière mixte, ou MIP 1 pour faire court.
Les problèmes de programmation entière sont un type de problème d’optimisation
discret. En général, les problèmes d’optimisation discrets peuvent contenir non seule-
ment des variables à valeurs entières et des variables binaires, mais aussi des objets de
variable plus abstraits tels que des permutations d’un ensemble ordonné. La caractéris-
tique déterminante d’un problème d’optimisation discret est que l’inconnue x est tirée
d’un ensemble fini (mais souvent très grand).
En revanche, l’ensemble admissible pour les problèmes d’optimisation continus
est généralement infini et non dénombrable, notamment lorsque les composantes de
x sont autorisées à être des nombres réels. Les problèmes d’optimisation continus sont
généralement plus faciles à résoudre car la régularité des fonctions permet d’utiliser
les informations des fonctions intervenant dans l’objectif et les contraintes en un point
particulier x pour déduire des informations sur le comportement de ces fonctions à
tous les points proches de x. Dans les problèmes discrets, en revanche, le comportement
de l’objectif et des contraintes peut changer de manière significative lorsque l’on passe
d’un point admissible à un autre, même si les deux points sont «proches» selon certaines
mesures.

1.4.2 Optimisation globale versus optimisation locale

En considérant le problème d’optimisation général (1.1), nous distinguons deux types

de minimiseurs, comme spécifié par les définitions suivantes.
Définition 1.1. Supposons que f : Ω → R soit une fonction réelle définie sur un en-
semble Ω ⊂ R p .
— Un point x∗ ∈ Ω est un minimiseur local de f sur Ω s’il existe ε > 0 tel que
f ( x) ⩾ f ( x∗ ) pour tout x ∈ Ω tel que ∥ x − x∗ ∥ ⩽ ε.
1. Mixed Integer Program

13
1.4.2 Optimisation globale vs. locale Fondements de l’optimisation

— Un point x∗ ∈ Ω est un minimiseur local strict de f sur Ω s’il existe ε > 0 tel que
f ( x) > f ( x∗ ) pour tout x ∈ Ω tel que 0 < ∥ x − x∗ ∥ ⩽ ε.
— Un point x∗ ∈ Ω est un minimiseur global de f sur Ω si f ( x) ⩾ f ( x∗ ) pour tout
x ∈ Ω.

F IGURE 1.2 – Minimum global versus minima locaux

Si le point x∗ est un minimiseur global de la fonction f sur Ω, nous écrivons f ( x∗ ) =

minx∈Ω f ( x) et x∗ = arg minx∈Ω f ( x). En d’autres termes, étant donné une fonction
réelle f , l’expression arg minx∈Ω f ( x) désigne l’argument qui minimise la fonction f (un
point dans le domaine de f ), en supposant qu’un tel point est unique. Si la fonction f a
plus d’un minima globaux, l’expression arg min désigne l’ensemble de tous les minima
globaux.
Exercice. Soit f : R → R définie par f ( x) = ( x + 1)2 + 3. Montrer que
1. arg minx∈R f ( x) = −1,
2. arg minx∈[0,∞) f ( x) = 0.

À proprement parler, un problème d’optimisation est résolu uniquement lorsqu’un

minimiseur global est trouvé. Cependant, les minimiseurs globaux sont, en général, dif-
ficiles à trouver. Par conséquent, en pratique, nous devons souvent nous contenter de
trouver des minimiseurs locaux.
Pour les problèmes de programmation convexe, et plus particulièrement pour les
programmes linéaires, les solutions locales sont également des solutions globales. Les
problèmes non linéaires généraux, qu’ils soient contraints ou non, peuvent posséder des
solutions locales qui ne sont pas des solutions globales.

14
Convexité Fondements de l’optimisation

1.5 Convexité

Le concept de convexité est fondamental en optimisation. De nombreux problèmes

pratiques possèdent cette propriété, ce qui les rend généralement plus faciles à résoudre
tant sur le plan théorique que pratique.
Le terme «convexe» peut s’appliquer aussi bien aux ensembles qu’aux fonctions. Un
ensemble C ⊂ R p est un ensemble convexe si le segment de droite reliant deux points
quelconques de C se trouve entièrement dans C. Formellement, pour deux points x ∈ C
et y ∈ C, nous avons αx + (1 − α)y ∈ C pour tout α ∈ [0, 1]. Dans certains types de
problèmes d’optimisation, la notion d’un point extrémal d’un esnemble convexe joue un
rôle central. Un point z ∈ C est appelé point extrémal de C s’il n’est pas possible d’avoir
z = αx + (1 − α)y avec x, y ∈ C et α ∈]0, 1[. En d’autres termes, le point z est extrémal
s’il n’existe pas de ségment (non-dégénéré) dans C contenant z. Par exemple, si C est
un carré dans R2 , ses points extrémaux sont ses sommets. C’est également le cas pour
tout polygone convexe. Ces ensembles ont donc un nombre fini de points extrémaux. En
revanche, si C est un disque dans R2 , le cercle qui constitue son contour est l’ensemble
de ses points extrémaux.
La fonction f est une fonction convexe si son domaine S est un ensemble convexe et
si, pour deux points quelconques x et y dans S, la propriété suivante est satisfaite :


f αx + (1 − α)y ⩽ α f ( x) + (1 − α) f (y), pour tout α ∈ [0, 1].

Des exemples simples d’ensembles convexes comprennent la boule unité {y ∈ R p :

∥y∥2 ⩽ 1} ; et tout polyèdre, qui est un ensemble défini par des égalités et des inégalités
linéaires, c’est-à-dire,
x ∈ R p : Ax = b, Cx ⩽ d ,


où A et C sont des matrices de dimension appropriée, et b et d sont des vecteurs. Des

exemples simples de fonctions convexes comprennent la fonction linéaire f ( x) = c⊤ x +
a, pour tout vecteur constant c ∈ R p et scalaire a ; et la fonction quadratique convexe
f ( x) = x⊤ Hx, où H est une matrice symétrique positive.
Une fonction f est dite concave si − f est convexe. Si la fonction-objectif dans le pro-
blème d’optimisation et la région admissible sont toutes deux convexes, alors toute so-
lution locale du problème est en fait une solution globale.
Le terme programmation convexe est utilisé pour décrire un cas particulier du pro-
blème général d’optimisation sous contraintes (1.1) dans lequel
— la fonction objectif est convexe,
— les contraintes d’égalité hi ( x) = 0 impliquent des fonctions linéaires hi , et
— les contraintes d’inégalité g j ( x) ⩽ 0 impliquent uniquement des fonctions convexes.

15
Gradient, différentielle et hessienne Fondements de l’optimisation

1.6 Gradient, différentielle et hessienne

Dans toute cette partie, on supposera que Ω est un ouvert de R p et que x∗ ∈ Ω. On

noter B( x∗ , r ) la boule dans R p centrée en x∗ de rayon r > 0.

Définition 1.2. On dit que f est différentiable en x∗ , s’il existe un vecteur a ∈ R p tel que

f ( x) = f ( x∗ ) + a⊤ ( x − x∗ ) + o (∥ x − x∗ ∥), lorsque x → x∗ .

On notera alors a = ∇ f ( x∗ ). On l’appellera gradient de f en x∗ .

Définition 1.3. Si f est différentiable dans un voisinage B( x∗ , r ) de x∗ et l’application

∇ f : B( x∗ , r ) → R p est continue, alors on dit que f est continûment différentiable en
x∗ . Si f est continûment différentiable en tout x∗ ∈ Ω, on dit que f est continûment
différentiable dans Ω et écrit f ∈ C1 (Ω).

Il est important de noter que si f est différentiable en x∗ , alors toutes les dérivées
partielles
∂f ∗ ∂f ∗ ∂f ∗
( x ), ( x ), . . . , (x )
∂x1 ∂x2 ∂x p
existent. De plus, si toutes les dérivées partielles existent et sont continues en x∗ , alors
f est différentiable en x∗ . Plus généralement, f ∈ C1 (Ω) si et seulement si toutes les
dérivées partielles existent et sont continues dans Ω.
Cependant, il y a des fonctions qui admettent des dérivées partielles en x∗ , mais qui
ne sont pas dérivables en x∗ . Un exemple de telle fonction est
x1 x2
f : R2 → R, f ( x) = q , si x12 + x22 > 0
x12 + x22

et f (0, 0) = 0. Pour cette fonction, il est claire que les dérivées partielles existent en tout
point, même en (0, 0)⊤ , et sont données par

∂f ∗ x23 ∂f ∗ x13
(x ) = 2 , (x ) = 2 , x∗ ̸= (0, 0)⊤ ,
∂x1 ( x1 + x22 )3/2 ∂x2 ( x1 + x22 )3/2
∂f ∗ ∂f ∗
( x ) = 0, ( x ) = 0, x∗ = (0, 0)⊤ .
∂x1 ∂x2
Si f était différentiable en (0, 0)⊤ , on aurait
" ∂f #
" #
∂x1 (0, 0) 0
∇ f (0, 0) = ∂f = ,
∂x2 (0, 0)
0

et, par conséquent, on aurait que f ( x) = f (0, 0) + ∇ f (0, 0)⊤ x + o (∥ x∥) = o (∥ x∥). Or,
√
ce n’est pas le cas car f (t, t) = 2 t/2 ̸= o (t).

16
Gradient, différentielle et hessienne Fondements de l’optimisation

Exercice 1.1. Calculer le gradient de f : R p → R définie par f ( x) = log(1 + ∥ x∥2 ).

Corrigé. Soit g : R → R la fonction g(t) = f (t, x2 , . . . , x p ) = log(1 + t2 + x22 + . . . + x2p ).

Cette fonction est dérivable en tout t ∈ R et on a g′ (t) = 2t/(1 + t2 + x22 + . . . + x2p ). La
fonction g′ qu’on vient d’obtenir est continue dans R. On en déduit que ∂ f /∂x1 existe
et est donnée par

∂f 2x1
( x) = .
∂x1 1 + ∥ x ∥2

Cette fonction est clairement continue xans R p . Comme f est symétrique par rapport
à toutes ses variables x1 , . . . , x p , on peut montrer de la même façon que toutes les dé-
rivées partielles de f existent et sont continues. On en déduit que f est continûment
différentiable dans R p et que

2x
∇ f ( x) = .
1 + ∥ x ∥2

Exercice 1.2. Si f : R p → R est définie par f ( x) = g(Ax) où A ∈ Mq,p (R) et g : Rq → R

est C1 (R), alors f ∈ C1 (R) et ∇ f ( x) = A⊤ ∇ g(Ax).

Passons maintenant aux fonctions à valeurs vectorelles.

⊤
Définition 1.4. Soit f : Ω → Rq qui s’écrit sous la forme f ( x) = f 1 ( x), . . . , f q ( x) . On
dit que f est différentiable (resp. continûment différentiable) en x∗ si toutes les fonctions
f 1 , . . . , f p : Ω → R sont différentiables (resp. continûment différentiables) en x∗ . Si f est
continûment différentiable en tout x ∈ Ω, on écrit f ∈ C1 (Ω).

Pour une fonction f : Ω → Rq différentiable en x ∗ , on appelle matrice jacobienne,

matrice de différentielle ou simplement différentielle 2 , la matrice q × p définie par
 
∇ f1 (x )∗ ⊤
∗

D f (x ) =  .. 
.
 . 
∗
∇ f p (x ) ⊤

Cette définition nous permet de calculer la différentielle d’une fonction composée en

utilisant la «chain rule».

Théorème 1.1. Si f : R p → Rq et g : Rr → R p sont deux fonctions telles que g est différen-

tiable en x ∈ Rr et f est différentiable en g( x), alors h = f ◦ g : Rr → Rq est différentiable en
x et Dh( x) = D f ( g( x)) Dg( x).
2. Il s’agit ici d’un abus de langage qui ne porte pas à confusion lorsqu’on travaille dans des espaces
euclidiens.

17
Gradient, différentielle et hessienne Fondements de l’optimisation

Corollaire 1. Si f : R p → R et g : R → R p sont toutes les deux différentiables en tout point,

alors h = f ◦ g : R → R est dérivable en tout point et
p
∂f
′ ⊤ ′
h (t) = ∇ f ( g(t)) g (t) = ∑ ∂xi ( g(t)) gi′ (t).
i =1

Le résultat de ce corollaire est souvent utilisé pour calculer les dérivées des fonctions
complexes. Considérons, par exemple, la fonction
Z t
h : R → R, h(t) = ψ(y2 + t) dy,
0

où ψ : R → [0, 1] est une fonction continûment dérivable. Pour calculer la dérivée de h,

on peut introduire les fonctions
Z x1
f : R → R,
2
f ( x1 , x2 ) = ψ(y2 + x2 ) dy,
0
g : R → Rp, g(t) = (t; t; . . . ; t)⊤ .

On a alors g′ (t) = (1, . . . , 1), ce qui implique que

∂f ∂f
h′ (t) = (t, t) + (t, t).
∂x1 ∂x2
Or, le simple calcul montre que
Z x1
∂f ∂f
( x1 , x2 ) = ψ( x12 + x2 ), ( x1 , x2 ) = ψ′ (y2 + x2 ) dy.
∂x1 ∂x2 0

En remplaçant x1 et x2 par t, il vient

Z t
∂f ∂f
h′ (t) = (t, t) + (t, t) = ψ(t2 + t) + ψ′ (y2 + t) dy.
∂x1 ∂x2 0

Théorème 1.2 (Formule de Taylor). Si Ω est un convexe ouvert de R p et f : Ω → R est

continûment différentiable dans Ω, alors pour tout x, x0 ∈ Ω,
Z 1
f ( x ) − f ( x0 ) = ∇ f ( x0 + t( x − x0 ))⊤ dt( x − x0 ). (1.3)
0

Démonstration. Il suffit de remarquer que la fonction h : [0, 1] → R définie par h(t) =

f ( x0 + t( x − x0 )) = f ◦ g(t) où g(t) = x0 + t( x − x0 ), vérifie h(0) = f ( x0 ), h(1) =
f ( x) et h′ (t) = ∇ f ( x0 + t( x − x0 ))⊤ ( x − x0 ). La formule (5.1) est alors équivalent à
R1
h(1) − h(0) = 0 h′ (t) dt.
Définition 1.5. Si f : Ω → R est différentiable dans un voisinage de x∗ et le gradient
∇ f , bien définie dans ce voisinage, est différentiable en x∗ , alors on dira que f est deux
fois différentiable en x∗ . On utilisera la notation

∇2 f ( x ∗ ) = D ∇ f ( x ∗ ) ∈ M p (R).

La matrice ∇2 f ( x∗ ) s’appelle la hessienne de f en x∗ .

18
Convexité des fonctions différentiables Fondements de l’optimisation

Si f est deux fois différentiable, alors elle a des dérivées partielles d’ordre 2 et

∂2 f
∇2 f ( x ∗ ) ( x ∗ ).


i,j
=
∂xi ∂x j

Si ∇2 f ( x) existe et est continue en tout x ∈ Ω, on dit que f est deux fois continûment
différentiable dans Ω et on écrit f ∈ C2 (Ω).

Théorème 1.3. Si f est deux fois continûment différentiable dans un voisinage de x, alors la
hessienne ∇2 f ( x) est une matrice symétrique. Par conséquent,

∂2 f ∂2 f
( x∗ ) = ( x ∗ ), ∀i, j = 1, . . . , p.
∂xi ∂x j ∂x j ∂xi

Nous avons vu dans le Théorème 1.2 que le gradient d’une fonction différentiable
nous permettait de caractériser les accroissements de cette fonction. Si la fonction est
plus régulière, notamment si elle est deux fois différentiable, on peut aller plus loin et
caractériser l’approximation de la fonction par une fonction affine. C’est l’objectif du
théorème suivant.

Théorème 1.4. Soit Ω un convexe ouvert de R p . Si la fonction f : Ω → R est deux fois

continûment différentiable dans Ω, alors pour tout x, x0 ∈ Ω, il existe un point z appartenant
au segment [ x0 , x], tel que
1
f ( x) = f ( x0 ) + ∇ f ( x0 )⊤ ( x − x0 ) + ( x − x0 )⊤ ∇2 f (z)( x − x0 ) .
| {z } 2| {z }
approximation affine forme quadr. de matrice ∇2 f (z)

Démonstration. Il suffit de considérer la même fonction h(t) = f ( x0 + t( x − x0 )) que

dans la preuve du Théorème 1.2. D’après le théorème de Taylor-Lagrange, il existe ϑ ∈
[0, 1] tel que
1
h(1) = h(0) + h′ (0) + h′′ (ϑ ).
2
En substituant h et ses dérivées par leur expression, on obtient le résultat souhaité.

1.7 Convexité des fonctions différentiables

Dans toute cette partie, nous supposerons que Ω est un convexe ouvert de R p et que
f : Ω → R. Dans de nombreux cas, il peut être difficile de vérifier la convexité de f
en utilisant simplement la définition présentée dans la partie 1.5. Lorsque la fonction
f est régulière, c’est-à-dire différentiable ou même deux fois différentiable, il existe des
critères plus simples pour tester la convexité d’une fonction. Le but de cette partie est
de présenter certains de ces critères.

19
Convexité des fonctions différentiables Fondements de l’optimisation

Théorème 1.5. Si la fonction f est continûment différentiable dans Ω, alors les trois assertions
suivantes sont équivalentes :
a) f est convexe,
b) on a f ( x) ⩾ f ( x0 ) + ∇ f ( x0 )⊤ ( x − x0 ) pour tout x, x0 ∈ Ω,
c) ∇ f est croissante, c’est-à-dire ( x − x0 )⊤ (∇ f ( x) − ∇ f ( x0 )) ⩾ 0 pour tout x, x0 ∈ Ω.

Démonstration. a) =⇒ b) On sait que

f αx + (1 − α) x0 ⩽ α f ( x) + (1 − α) f ( x0 ), ∀α ∈ [0, 1].

On soustrait f ( x0 ) des deux côtés de cette inégalité et on divise par α. Il vient

f αx + (1 − α) x0 − f ( x0 )
⩽ f ( x ) − f ( x0 ).
α
En faisant tendre α vers 0, on voit que le membre gauche de cette inégalité converge
vers la dérivée en 0 de la fonction g(t) = f ( x0 + t( x − x0 )). Comme cette dérivée est
égale à ∇ f ( x0 )⊤ ( x − x0 ), on obtient l’assertion b).
b) =⇒ c) Cette implication est très facile à démontrer. Il suffit de récopier b) en échan-
geant les rôles de x et x0 , puis additionner les deux inégalités obtenues.
c) =⇒ a) On utilisera la notation suivante :

yα = αx + (1 − α) x0 = x0 + α( x − x0 ).

D’après la formule de Taylor, on a

Z 1
f ( x ) − f ( x0 ) = ∇ f (yt )⊤ dt ( x − x0 ),
0
Z 1
f ( y α ) − f ( x0 ) = ∇ f ( x0 + t(yα − x0 ))⊤ dt (yα − x0 )
0
Z 1
=α ∇ f ( x0 + αt( x − x0 ))⊤ dt ( x − x0 )
0
Z 1
=α ∇ f (yαt )⊤ dt ( x − x0 ).
0

Il en découle que

α( f ( x) − f ( x0 )) − ( f (yα ) − f ( x0 ))
Z 1
⊤
=α ∇ f (yt ) − ∇ f (yαt ) dt ( x − x0 ),
0
Z 1
α 1
⊤
= ∇ f (yt ) − ∇ f (yαt ) (1 − α)t( x − x0 ) dt
(1 − α ) 0 t | {z }
=yt −yαt
Z 1
α 1
⊤
= ∇ f (yt ) − ∇ f (yαt ) (yt − yαt ) dt.
(1 − α ) 0 t| {z }
⩾0 d’après c)

20
Reconnaissance d’un minimum local Fondements de l’optimisation

On obtient donc α( f ( x) − f ( x0 )) − ( f (yα ) − f ( x0 )) ⩾ 0, ce qui peut également s’écrire

comme


α f ( x) + (1 − α) f ( x0 ) ⩾ f (yα ) = f αx + (1 − α) x0 .

Comme cette inégalité est vraie pour tout α ∈]0, 1[, x, x0 ∈ Ω, on en déduit que f est
convexe.

Théorème 1.6. Si la fonction f est deux fois continûment différentiable dans Ω, alors les deux
assertions suivantes sont équivalentes :
a) f est convexe,
b) la hessienne ∇2 f ( x) de f en tout point x est positive, ∇2 f ( x) ≽ 0.

Démonstration. a) =⇒ b) Soit u ∈ R p un vecteur quelconque. Définissons la fonction

g(t) = f ( x + tu). Comme Ω est un ouvert, x + tu sera dans Ω dès que t est suffisamment
petit. La fonction g est donc bien définie dans le voisinage de 0. De plus, la convexité de
f entraîne la convexité de g. Comme g est deux fois dérivable, il en résulte que g′′ (t) ⩾ 0
pour tout t dans un voisinage de 0. En particulier, g′′ (0) ⩾ 0. Un calcul rapide montre
que g′′ (0) = u⊤ ∇2 f ( x)u. Nous avons donc prouvé que la forme quadratique u 7→
u⊤ ∇2 f ( x)u est positive pour tout vecteur u. Il en résulte que la matrice ∇2 f ( x) est
positive.
b) =⇒ a) Conséquence directe du Théorème 1.4.

1.8 Reconnaissance d’un minimum local

D’après les définitions précédentes, il pourrait sembler que la seule façon de déter-
miner si un point x∗ est un minimum local est d’examiner tous les points dans son
voisinage immédiat, afin de s’assurer qu’aucun d’entre eux n’a une imgae par f plus
petite que f ( x∗ ). Cependant, lorsque la fonction f est régulière, ils existent des moyens
plus efficaces et pratiques d’identifier les minima locaux. En particulier, si f est deux
fois continûment différentiable, nous pourrions être en mesure de déterminer que x∗
est un minimiseur local (et éventuellement un minimiseur local strict) en examinant
simplement le gradient ∇ f ( x∗ ) et l’hessien ∇2 f ( x∗ ).
Exercice. Soit f : R3 → R définie par f ( x1 , x2 , x3 ) = 4 + 2x1 − x3 + x12 + 3x22 + 2x1 x3 .
1. Calculer le gradient ∇ f ( x1 , x2 , x3 ).
2. Calculer l’hessien ∇2 f ( x1 , x2 , x3 ).
3. Écrire la fonction f sous une forme matricielle en utilisant le vecteur-colonne x =
[ x1 ; x2 ; x3 ] ⊤ .

21
Reconnaissance d’un minimum local Fondements de l’optimisation

4. Déduire les deux premières questions de la troisième question en utilisant les

règles des dérivées par rapport à une variable multidimensionnelle.
Les conditions nécessaires à l’optimalité sont dérivées en supposant que x∗ est un
minimiseur local et en prouvant ensuite des faits sur ∇ f ( x∗ ) et ∇2 f ( x∗ ).

Théorème 1.7 (Conditions Nécessaires du Premier Ordre). Si x∗ est un minimiseur local

et f est continûment différentiable dans un voisinage ouvert de x∗ , alors ∇ f ( x∗ ) = 0.

Démonstration. Nous allons raisonner par l’absurde. Supposons que ∇ f ( x∗ ) ̸= 0. Défi-

nissons le vecteur u = −∇ f ( x∗ ) et notons que u⊤ ∇ f ( x∗ ) = −∥∇ f ( x∗ )∥2 < 0. Comme
∇ f est continue dans un voisinage de x∗ , il existe un scalaire T > 0 tel que

u⊤ ∇ f ( x∗ + tu) < 0, pour tout t ∈ [0, T ].

Pour tout t̄ ∈ (0, T ], nous avons d’après le théorème de Taylor que f ( x∗ + t̄u) = f ( x∗ ) +
t̄u⊤ ∇ f ( x∗ + tu), pour un certain t ∈ (0, t̄). Par conséquent, f ( x∗ + t̄u) < f ( x∗ ) pour
tout t̄ ∈ (0, T ]. Nous avons trouvé une direction s’éloignant de x∗ le long de laquelle f
diminue, donc x∗ n’est pas un minimiseur local, et nous avons une contradiction.

Nous appelons x∗ un point stationnaire de f si ∇ f ( x∗ ) = 0. Selon le Theorem 1.7,

tout minimiseur local d’une fonction continûment différentiable doit être un point sta-
tionnaire.
Pour le résultat suivant, nous rappelons qu’une matrice B est définie positive si
u⊤ Bu > 0 pour tout u ̸= 0, et positive (ou semi-définie positive) si u⊤ Bu ⩾ 0 pour
tout u.

Théorème 1.8 (Conditions Nécessaires du Second Ordre). Si x∗ est un minimiseur local de

f et ∇2 f existe et est continue dans un voisinage ouvert de x∗ , alors ∇ f ( x∗ ) = 0 et ∇2 f ( x∗ )
est positive.

Démonstration. Nous savons d’après le Theorem 1.7 que ∇ f ( x∗ ) = 0. Pour raisonner

par l’absurde, supposons que ∇2 f ( x∗ ) n’est pas positive. Alors, nous pouvons choisir
un vecteur u ∈ R p tel que u⊤ ∇2 f ( x∗ )u < 0, et comme ∇2 f est continue dans un voisi-
nage de x∗ , il existe un scalaire T > 0 tel que u⊤ ∇2 f ( x∗ + tu)u < 0 pour tout t ∈ [0, T ].
En effectuant un développement en série de Taylor autour de x∗ , nous avons pour
tout t̄ ∈ (0, T ] et un certain t ∈ (0, t̄) que

1 2 ⊤ 2
f ( x∗ + t̄u) = f ( x∗ ) + t̄ u⊤ ∇ f ( x∗ ) + t̄ u ∇ f ( x∗ + tu)u < f ( x∗ ).
2
Comme dans le Theorem 1.7, nous avons trouvé une direction à partir de x∗ le long de
laquelle f diminue, et donc une fois de plus, x∗ n’est pas un minimiseur local.

22
Conditions suffisantes Fondements de l’optimisation

1.9 Conditions suffisantes

Nous décrivons maintenant des conditions suffisantes, qui sont des conditions sur
les dérivées de f en le point x∗ qui garantissent que x∗ est un minimum local.

Théorème 1.9. Supposons que ∇2 f est continue dans un voisinage ouvert de x∗ et que ∇ f ( x∗ ) =
0 et ∇2 f ( x∗ ) est défini positive. Alors x∗ est un minimum local strict de f .

Démonstration. Comme la matrice hessienne est continue et définie positive en x∗ , nous

pouvons choisir un rayon r > 0 de telle sorte que ∇2 f ( x) reste définie positive pour
tous les x dans la boule ouverte D = {z : ∥z − x∗ ∥ < r }. En prenant un vecteur non nul
u avec ∥u∥ < r, nous avons x∗ + u ∈ D et donc
1 ⊤ 2
f ( x∗ + u) = f ( x∗ ) + u⊤ ∇ f ( x∗ ) + u ∇ f (z)u
2
1 ⊤ 2
= f ( x∗ ) + u ∇ f (z)u,
2
où z = x∗ + tu pour certains t ∈ (0, 1). Comme z ∈ D , nous avons u⊤ ∇2 f (z)u > 0, et
donc f ( x∗ + u) > f ( x∗ ), ce qui donne le résultat.

Notez que les conditions suffisantes du second ordre ne sont pas nécessaires : un
point x∗ peut être un minimum local strict et peut tout de même ne pas satisfaire les
conditions suffisantes. Un exemple simple est donné par la fonction f ( x ) = x4 , pour
laquelle le point x ∗ = 0 est un minimum local strict où la matrice hessienne s’annule (et
n’est donc pas définie positive).
Lorsque la fonction-objectif est convexe, les minimiseurs locaux et globaux sont simples
à caractériser.

Théorème 1.10. Lorsque f est convexe, tout minimiseur local x∗ est un minimiseur global de
f . Si de plus f est différentiable, alors tout point stationnaire x∗ est un minimiseur global de f .

Démonstration. Supposons que x∗ est un minimiseur local mais pas global. Alors, nous
pouvons trouver un point z ∈ R p avec f (z) < f ( x∗ ). Considérons le segment de droite
qui joint x∗ à z, c’est-à-dire,

x = λz + (1 − λ) x∗ , pour certains λ ∈ (0, 1]. (1.4)

En raison de la propriété de convexité de f , nous avons

f ( x ) ⩽ λ f ( z ) + (1 − λ ) f ( x ∗ ) < f ( x ∗ ). (1.5)

Tout voisinage N de x∗ contient une partie du segment de droite (1.4), de sorte qu’il y
aura toujours des points x ∈ N pour lesquels (1.5) est satisfait. Par conséquent, x∗ n’est
pas un minimiseur local.

23
Exemples Fondements de l’optimisation

Pour la deuxième partie du théorème, soit x∗ un point stationnaire de f et soit z un

point quelconque du domaine de f . Alors, en raison de la convexité, nous avons

d
∇ f ( x∗ )⊤ (z − x∗ ) = f ( x∗ + λ(z − x∗ ))
dλ λ =0
f ( x + λ(z − x )) − f ( x∗ )
∗ ∗
= lim
λ ↘0 λ
λ f ( z ) + (1 − λ ) f ( x ∗ ) − f ( x ∗ )
⩽ lim
λ ↘0 λ
= f ( z ) − f ( x ∗ ).

Par conséquent, ∇ f ( x∗ ) = 0, implique que f (z) − f ( x∗ ) ⩾ 0 pour tout z. Il en découle

que x ∗ est un minimiseur global de f .

1.10 Exemples

Exemple 1 Un véhicule amphibie doit se déplacer du point A (sur terre) au point B

(dans l’eau), comme illustré dans la Figure 1.3. Les vitesses auxquelles le véhicule se
déplace sur terre et dans l’eau sont respectivement v1 et v2 .

a) Supposons que le véhicule emprunte un chemin qui minimise le temps total né-
cessaire pour aller de A à B. Utilisez la condition nécessaire du premier ordre
pour montrer que, pour le chemin optimal ci-dessus, les angles ϑ1 et ϑ2 dans la
Figure 1.3 satisfont la loi de Snell :

sin ϑ1 v
= 1.
sin ϑ2 v2

b) Est-ce que le minimiseur du problème de la partie a) satisfait la condition suffisante

du second ordre ?

Réponse à la question a) Notons t1 le temps que le véhicule passe sur terre et t2 le

temps passé dans l’eau. Puisque le temps est égal à la distance divisée par la vitesse,
nous avons √ p
x2 + 1 ( d − x )2 + 1
t1 = , t2 = .
v1 v2
Par conséquent, l’objectif est de minimiser la fonction f ( x ) = t1 + t2 donnée par la
formule √ p
x2 + 1 ( d − x )2 + 1
f (x) = + .
v1 v2

24
Exemples Fondements de l’optimisation

F IGURE 1.3 – Trajectoire du véhicule amphibie dans l’exemple 1.

La condition du premier ordre f ′ ( x ) = 0 peut être écrite comme

1
′ 1
′
f ′ (x) = ( x2 + 1)1/2 + [(d − x )2 + 1]1/2
v1 v2
1 x 1 (d − x )
= 2 1/2
− = 0.
v1 ( x + 1) v2 [(d − x )2 + 1]1/2

D’autre part, on vérifie facilement que

x d−x
sin ϑ1 = , sin ϑ2 = .
( x2 + 1)1/2 ((d − x )2 + 1)1/2
Cela implique que
sin ϑ1 sin ϑ2
f ′ (x) = 0 ⇐⇒ = .
v1 v2
Réponse à la question b) Calculons la dérivée du deuxième ordre :
′ ′
( x − d)
 
′′ 1 x 1
f (x) = +
v1 ( x2 + 1)1/2 v2 [( x − d)2 + 1]1/2
1 1 1 x2
= −
v1 ( x2 + 1)1/2 v1 ( x2 + 1)3/2
1 1 1 ( x − d )2
+ −
v2 [( x − d)2 + 1]1/2 v2 [( x − d)2 + 1]3/2
1 1 1 1
= 2 3/2
+ .
v1 ( x + 1) v2 [( x − d)2 + 1]3/2

25
Exemples Fondements de l’optimisation

Nous constatons que f ′′ ( x ) > 0, cela signifie que la condition suffisante du deuxième
ordre est remplie. Par conséquent, la solution x ∗ de l’équation f ′ ( x ∗ ) = 0 est un mini-
mum local strict. De plus, la fonction f étant convexe, ce minimum local est également
un minimum global.

Exemple 2 : Ajustement de droite Soient [ x1 , y1 ]⊤ , . . . , [ xn , yn ]⊤ , n ⩾ 2, des points

dans le plan R2 (chaque xi , yi ∈ R). Nous souhaitons trouver la droite «d’ajustement
optimal» à travers ces points («optimal» dans le sens où l’erreur quadratique moyenne
est minimisée) ; autrement dit, nous voulons trouver a, b ∈ R pour minimiser
1 n
f ( a, b) = ∑
n i =1
( axi + b − yi )2 .

Introduisons les notations suivantes

1 n 1 n 1 n 2 1 n
x̄ = ∑ xi , ȳ = ∑ yi , x2 = ∑ xi , xy = ∑ xi yi .
n i =1 n i =1 n i =1 n i =1

On vérifie facilement que f est une fonction quadratique en ( a, b) et est donnée par

f ( a, b) = x2 a2 + b2 + 2x̄ ab − 2xya − 2ȳ b + y2 .

Par conséquent, nous avons

" #
x2 a + x̄ b − xy
∇ f ( a, b) = 2 (1.6)
b + x̄ a − ȳ
et "#
2 x2 x̄
∇ f ( a, b) = 2 .
x̄ 1
En utilisant l’inégalité de Cauchy-Schwarz, ( x̄ )2 ⩽ x2 . Cela implique que le détermi-
nant de la matrice ∇2 f ( a, b) , de dimensions 2 × 2, est non négatif. De plus, la trace
de la même matrice est positive. En conséquence, la matrice ∇2 f ( a, b) est positive pour
tout ( a, b) ∈ R2 . Cela implique que la fonction f est convexe. Par conséquent, si nous
trouvons un point stationnaire de f , il sera également son minimiseur global.
Pour trouver les points stationnaires de f , nous résolvons l’équation ∇ f ( a∗ , b∗ ) = 0.
En utilisant (1.6), et en supposant que ( x̄ )2 < x2 , ce qui est équivalent 3 à s2x = x2 −
( x̄ )2 > 0, nous obtenons
xy − x̄ ȳ s xy
b∗ = ȳ − a∗ x̄, a∗ = 2
= 2. (1.7)
sx sx
En conclusion, la droite qui s’ajuste le mieux au nuage de points [ xi , yi ]⊤ est donnée par
l’équation y = a∗ x + b∗ , où a∗ et b∗ sont donnés par (1.7).
3. C’est le cas si les nombres xi ne sont pas tous égaux.

26
Exercices Fondements de l’optimisation

1.11 Exercices

Exercice 1.3. On note Sn (R) et Pn (R) l’ensemble des matrices n × n à coefficients réels
symétriques et positives, respectivement. Dans Sn (R) structuré en espace euclidien
grâce au produit scalaire ⟨A, B⟩ = Tr(AB), on considère l’ensemble suivant

Ω1 = {A ∈ Pn (R) : Tr(A) = 1}.

1. Montrer que Ω1 est un convexe compact de Sn (R).

2. Montrer que les points extrémaux de Ω1 sont exactement les matrices de la forme
xx⊤ , où x est un vecteur unitaire de Rn . (Remarque : cela équivaut à dire que A
est un point extrémal de Ω1 si et seulement s’il est de rang 1.)

Exercice 1.4. Déterminer le gradient et la hessienne des fonctions suivantes.

1. f : R p → R définie par x 7→ a⊤ x + b.
2. g : R p → R définie par g( x) = 21 x⊤ Ax.
3. h : R p → R définie par h( x) = ∑im=1 ri ( x)2 , où ri : R p → R sont des fonctions deux
fois différentiables.

Exercice 1.5. Soit f : Ω → R une fonction deux fois continûment différentiable dans le
convexe ouvert Ω ⊆ R p . Montrer que
Z 1 
2
∇ f ( x ) − ∇ f ( x0 ) = ∇ f ( x0 + t( x − x0 )) dt ( x − x0 ), ∀ x, x0 ∈ Ω.
0

Indication : On peut commencer par le théorème fondamental d’analyse appliqué à la fonction

g : [0, 1] → R définie par g(t) = u⊤ ∇ f ( x0 + t( x − x0 )) où u ∈ R p est un vecteur quelconque.

Exercice 1.6. Soit f : R p → R continûment différentiable. On suppose qu’il existe M > 0

tel que

∥∇ f ( x) − ∇ f ( x′ )∥ ⩽ M∥ x − x′ ∥, ∀ x, x′ ∈ R p .

Montrer que

f ( x + u) − f ( x) − u⊤ ∇ f ( x) ⩽ ( M/2)∥u∥2 , ∀ x, u ∈ R p .

Exercice 1.7. Soit f : R p → R une fonction convexe et de classe C1 telle que ∇ f est
Lipschitzienne de constant M : ∥∇ f ( x) − ∇ f ( x′ )∥ ⩽ M ∥ x − x′ ∥ pout tout x, x′ ∈ R p .
Alors, pour tout x, x′ ∈ R p , on a

27
Exercices Fondements de l’optimisation

1. f ( x′ ) − f ( x) − ∇ f ( x)⊤ ( x′ − x) ⩾ 2M
1
∥∇ f ( x′ ) − ∇ f ( x)∥2 ,

⊤
2. ∇ f ( x) − ∇ f ( x′ ) ( x − x′ ) ⩾ M 1
∥∇ f ( x) − ∇ f ( x′ )∥2 .
Indication : Pour la première question, on pourra commencer par appliquer l’exercice 1.6 à
u = x′ − x − M1
∇ f ( x′ ) − ∇ f ( x)

Exercice 1.8. Soit Mn (R) l’ensemble des matrices n × n à coefficients réels structuré en
espace euclidien grâce au produit scalaire ⟨A, B⟩ = Tr(A⊤ B). Soit Ω l’ouvert de Mn (R)
constitué des matrices inversibles. Déterminer le gradient de chacune des applications
suivantes :
1. f : Mn (R) → R définie par f (A) = Tr(A).
2. g : Mn (R) → R définie par g(A) = det(A).
3. h : Ω → R définie par h(A) = log det( A).

Exercice 1.9. Soit f : R p → R continue et bornée inférieurement sur R p . Soit ε > 0 et soit
u ∈ R p une solution à ε près du problème de minimisation de f dans R p , c’est-à-dire u
vérifie

f (u) ⩽ infp f ( x) + ε.
x ∈R

On fixe un λ > 0 et considère la fonction g : R p → R donnée par

ε
g( x) = f ( x) + ∥ x − u ∥.
λ
1. Ontrer qu’il existe v ∈ R p minimisant g sur R p .
2. Montrer que ce point v vérifie les propriétés
(a) f (v) ⩽ f (u),
(b) ∥u − v∥ ⩽ λ,
(c) ∀ x ∈ R p , f (v) ⩽ f ( x) + λε ∥ x − v∥.
3. Soit f : R p → R différentiable et bornée inférieurement sur R p . Montrer que pour
tout ε > 0 il existe un xε ∈ R p tel que ∥∇ f ( xε )∥ ⩽ ε.

28
Résumé du Chapitre 1 Fondements de l’optimisation

1.12 Résumé du Chapitre 1

L’objectif de l’optimisation est de résoudre le problème

minimiser f ( x)
sous contrainte x ∈ Ω.

Terminologie et définitions

• f est la fonction-objectif ou la fonction-coût.

• Ω est l’ensemble des contraintes ou l’ensemble admissible.
• x ∗ est une solution admissible si elle satisfait toutes les contraintes, c’est-à-dire x ∗ ∈
Ω.
• x∗ est un minimiseur local de f s’il existe un ε > 0 tel que f ( x∗ ) ⩽ f ( x) pour tout
x ∈ Ω satisfaisant ∥ x − x∗ ∥ ⩽ ε.
• x ∗ est un minimiseur local strict de f s’il existe un ε > 0 tel que f ( x∗ ) ⩽ f ( x) pour
tout x ∈ Ω satisfaisant 0 < ∥ x − x∗ ∥ ⩽ ε.
• x∗ est un minimiseur global de f si f ( x∗ ) ⩽ f ( x) pour tout x ∈ Ω.
• x∗ est un point stationnaire d’une fonction différentiable f si ∇ f ( x∗ ) = 0.

Ensembles et fonctions convexes

• Un ensemble C ⊂ R p est appelé convexe, si pour tout x, y ∈ C, le segment [ x, y] est

inclus dans C :

x, y ∈ C; α ∈ [0, 1] =⇒ αx + (1 − α)y ∈ C.

• Si C est soit fermé, soit ouvert, alors pour vérifier que C est convexe, il suffit de vérifier
que
1
x, y ∈ C =⇒ ( x + y) ∈ C.
2
• Une fonction f : Ω → R définie sur un ensemble convexe Ω ⊂ R p est appelée
convexe, si

x, y ∈ Ω; α ∈ [0, 1] =⇒ f αx + (1 − α)y ⩽ α f ( x) + (1 − α) f (y).

• Si Ω est soit ouvert, soit fermé, alors pour vérifier que f : Ω → R est convexe, il suffit
de vérifier que f est continue et
 
x+y f ( x) + f (y)
x, y ∈ Ω =⇒ f ⩽ .
2 2

29
Résumé du Chapitre 1 Fondements de l’optimisation

• Si f est continûment différentiable, alors elle est convexe si et seulement si sa courbe

est au-dessus de chacune de ses tangentes :

f ( x ) ⩾ f ( x0 ) + ( x − x0 ) ⊤ ∇ f ( x0 ), ∀ x, x0 ∈ Ω.

• Si f est deux fois continûment différentiable, alors elle est convexe si et seulement si
la hessienne est positive en tout point : ∇2 f ( x) ≽ 0 pour tout x ∈ Ω.

Conditions nécessaires

• FONC : Si x∗ est un minimiseur local de f et f est continûment différentiable dans un

voisinage de x∗ , alors ∇ f ( x∗ ) = 0. Cela signifie que pour que x∗ soit un minimi-
seur local, il est nécessaire qu’il soit un point stationnaire.
• SONC : Si x∗ est un minimiseur local de f et f est deux fois continûment différentiable
dans un voisinage de x∗ , alors la hessienne de f en x∗ est positive : ∇2 f ( x∗ ) ≽ 0.

Conditions suffisantes

• SOSC : Soit x∗ un point stationnaire d’une fonction f deux fois continûment différen-
tiable. Si la hessienne de f en x∗ est définie positive, ∇2 f ( x∗ ) ≻ 0, alors x∗ est un
minimiseur local de f .
• Convexité 1 : Si f est convexe, tout minimiseur local de f est un minimiseur global.
Cela est vrai même pour des fonctions non différentiables telles que f ( x ) = | x |.
• Convexité 2 : Si f est convexe et différentiable, alors tout point stationnaire de f est
un minimiseur global.

Matrices définies positives et (semi-définies) positives

• Une matrice symétrique A, de taille p × p, est appelée positive ou semi-définie posi-

tive, notée A ≽ 0, si
p
v⊤ Av = ∑ Ai,j vi v j ⩾ 0 ∀v ∈ R p .
i,j=1

• Une matrice symétrique A, de taille p × p, est appelée définie positive, notée A ≻ 0,

si
p
⊤
v Av = ∑ Ai,j vi v j > 0 ∀ v ∈ R p \ {0}.
i,j=1

30
Résumé du Chapitre 1 Fondements de l’optimisation

• Une matrice est positive si et seulement si toutes ses valeurs propres sont non néga-
tives.
• Une matrice est positive définie si et seulement si toutes ses valeurs propres sont
strictement positives.
• Une matrice positive est définie positive si son déterminant est positif.
• (Critère de Sylvster) Une matrice symétrique est positive si et seulement si tous ses
mineurs principaux sont non négatifs.
• (Critère de Sylvster) Une matrice symétrique est définie positive si et seulement si
tous ses mineurs principaux dominants sont positifs.

31
 Algorithmes d’optimisation
2
2.1 Introduction

Dans ce chapitre, nous nous intéressons au problème de minimisation d’une fonction

objectif f , en commençant par le cas univarié f : [ a, b] → R. L’approche consiste à
utiliser un algorithme de recherche itératif, également appelé méthode de recherche
linéaire. Puis, on présente deux algorithmes qui permettent d’optimiser une fonction
multivariée.
Les méthodes de recherche unidimensionnelle sont intéressantes pour les raisons sui-
vantes. Premièrement, elles sont des cas particuliers des méthodes de recherche utilisées
dans les problèmes multivariés. Deuxièmement, elles sont utilisées dans le cadre d’al-
gorithmes multivariés généraux (comme nous le verrons plus tard dans ce cours).
Dans un algorithme itératif, nous commençons avec une solution candidate initiale
x (0)∈ [ a, b] et générons une séquence d’itérations x (1) , . . . , x (k) . Pour chaque itération
k = 0, 1, . . ., le point suivant x (k+1) dépend de 1 les valeurs passées x (k) , . . . , x (0) et de
la fonction objectif f . L’algorithme peut utiliser uniquement la valeur de f à des points
spécifiques, ou peut-être sa première dérivée f ′ , ou même sa deuxième dérivée f ′′ . Dans
ce chapitre, nous étudions plusieurs algorithmes :
1. Pour certaines méthodes telles que la méthode du nombre d’or, l’itération suivante peut également
dépendre de certaines autres quantités calculées lors des étapes précédentes.
Méthode du nombre d’or Algorithmes d’optimisation

F IGURE 2.1 – Un exemple d’une fonction unimodale. On remarquera que la fonction f

est strictement décroissante jusqu’au minimiseur x ∗ et strictement croissante de x ∗ à b.

— Méthode du nombre d’or 2 (utilise uniquement f ),

— Méthode de dichotomie (utilise uniquement f ′ ),
— Descente de gradient (utilise uniquement f ′ ),
— Méthode de Newton (utilise f ′ et f ′′ ),

2.2 Méthode du nombre d’or

Les méthodes de recherche abordées dans cette section et la section suivante nous
permettent de trouver le minimum d’une fonction objectif f sur un intervalle fermé
[ a, b]. La seule hypothèse que nous faisons sur la fonction f est qu’elle est unimodale,
c’est-à-dire qu’elle possède un unique minimum local. Un exemple illustratif d’une telle
fonction est présenté dans la Figure 2.1.
Les méthodes que nous présentons se basent sur l’évaluation de la fonction objectif
à différents points de l’intervalle [ a0 , b0 ] := [ a, b]. Ces points sont choisis de manière à
obtenir une approximation du minimiseur de f avec le moins d’évaluations possible.
Notre objectif est de réduire progressivement l’intervalle jusqu’à ce que le minimiseur
soit confiné dans un intervalle suffisamment précisément déterminé.
Considérons une fonction unimodale f dont on cherche le minimum dans l’intervalle
[ a, b]. Afin d’obtenir un intervalle réduit qui contient avec certitude le minimiseur de f ,
nous proposons d’évaluer f à deux points situés à l’intérieur de [ a, b], comme illustré
dans la Figure 2.2. Nous choisissons ces points, notés A et B, de manière à ce que la
réduction de l’intervalle soit symétrique, au sens où

A − a0 = b0 − B = γ(b0 − a0 ).

où γ ∈ (0, 1/2) (cette condition est nécessaire pour avoir A < B).
2. Golden Section Search, en anglais

34
Méthode du nombre d’or Algorithmes d’optimisation

F IGURE 2.2 – Méthode du nombre d’or : le cas où f ( A) < f ( B), ce qui implique que le
minimum local x ∗ se trouve dans [ a0 , B].

Nous évaluons ensuite f aux points A et B. Si f ( A) < f ( B), alors le minimiseur doit
se situer dans l’intervalle [ a0 , B]. Si, en revanche, f ( A) ⩾ f ( B), alors le minimiseur se
trouve dans l’intervalle [ A, b0 ]. Ainsi, nous définissons le nouvel intervalle comme suit :

[ a , B], si f ( A) < f ( B),
0
[ a1 , b1 ] =
[ A, b0 ], sinon.

On vérifie facilement que dans les deux cas, la longueur du nouvel intervalle est donnée
par
b1 − a1 = (1 − γ)(b0 − a0 ).
Ainsi, le nouvel intervalle est plus petit que celui de la précédente itération et contient
toujours le minimiseur x ∗ .
Les paragraphes ci-dessus décrivent comment obtenir l’intrvalle [ a1 , b1 ] à partir de
l’intervalle [ a0 , b0 ]. Supposons maintenant que pour tout n ∈ N∗ , [ an , bn ] est obtenu à
partir de [ an−1 , bn−1 ] en utilisant la même procédure, voir le pseudo-code ci-dessous.
Soit xn le centre de l’intervalle [ an , bn ].
En utilisant les propriétés présentées ci-dessus, nous pouvons établir le théorème
suivant.

Théorème 2.1. Si f est une fonction unimodale sur [ a, b] et γ ∈ (0, 1/2), alors l’approximation
de la méthode du nombre d’or xn converge vers x ∗ et nous avons

| xn − x ∗ | ⩽ 0.5(1 − γ)n (b − a).

35
Méthode du nombre d’or Algorithmes d’optimisation

Data: paramètre γ, fonction f , intervalle [ a, b], nombre d’itérations n

Result: le minimiseur approximatif x ∗
initialisation : a0 = a et b0 = b;
for k ∈ {0, 1, . . . , (n − 1)} do
A ← a k + γ ( bk − a k ) ;
B ← bk − γ ( bk − a k ) ;
if f ( A) < f ( B) then
a k +1 ← a k ;
bk+1 ← B;
else
ak+1 ← A;
bk + 1 ← bk ;
end
end
return xn ← ( an + bn )/2

Algorithm 1: Méthode du nombre d’or pour γ arbitraire

Démonstration. Nous avons déjà vu que x ∗ ∈ [ an , bn ] pour tout n ∈ N. Puisque xn est

défini comme le centre de l’intervalle [ an , bn ], nous obtenons

| xn − x ∗ | ⩽ 0.5| an − bn |. (2.1)

D’autre part, l’utilisation répétée du fait que bk − ak = (1 − γ)(bk−1 − ak−1 ) implique

que (bn − an ) = (1 − γ)n (b − a). En combinant cette relation avec (2.1), nous obtenons
le résultat du théorème.

F IGURE 2.3 – Le cas d’un γ minimisant le nombre d’évaluations de f dans la méthode

du nombre d’or.

Le pseudo-code de l’algorithme de la méthode du nombre d’or est présenté dans

l’Algorithme 1. Concentrons-nous maintenant sur le choix du paramètre γ. Il s’avère

36
Algorithme de dichotomie Algorithmes d’optimisation

que pour une valeur spécifique de γ, à l’itération k, l’un des deux points A et B coïncide
avec l’une de ces valeurs à l’itération précédente k − 1. Plus précisément, si à l’itération
k − 1 nous avons, par exemple, f ( A) < f ( B), alors pour les points A′ et B′ à l’itération
k nous aurons B′ = A (voir fig. 2.3). En rappelant que

A = a k − 1 + γ ( bk − 1 − a k − 1 ) ,
B = bk − 1 − γ ( bk − 1 − a k − 1 ) ,
a k = a k −1 ,
bk = B,
B ′ = bk − γ ( bk − a k ) ,

nous pouvons vérifier que B′ = A est équivalent à

a k − 1 + γ ( bk − 1 − a k − 1 ) = B − γ ( B − a k )
= bk − 1 − γ ( bk − 1 − a k − 1 ) − γ ( bk − 1 − γ ( bk − 1 − a k − 1 ) − a k )
= bk−1 − γ(2 − γ)(bk−1 − ak−1 ).

Cela implique que

γ2 − 3γ + 1 = 0.
Les solutions de cette équation sont
√
3± 5
γ= .
2
Puisque γ doit être inférieur à 1/2, nous obtenons
√
3− 5
γ= ≈ 0.382. (2.2)
2
Conclusion : Si nous appliquons l’algorithme de la méthode du nombre d’or avec γ
donné par (2.2), alors en utilisant n + 1 évaluations de la fonction f (n itérations), nous
obtenons un point x ∗ satisfaisant

| xn − x ∗ | ⩽ 0.5(0.618)n (b − a).

2.3 Algorithme de dichotomie

Notre but est toujours de trouver le minimiseur d’une fonction objectif f : [ a, b] → R.

Comme précédemment, nous supposons que f est unimodale. De plus, supposons que
f soit continûment différentiable et que nous puissions utiliser les valeurs de la dérivée
f ′ comme base pour réduire l’intervalle auquel appartient le point de minimum.

37
Descente de gradient Algorithmes d’optimisation

F IGURE 2.4 – Gradient descent algorithm

La méthode de dichotomie est un algorithme simple pour réduire successivement

l’intervalle d’incertitude basé sur des évaluations de la dérivée. Pour commencer, soit
x0 = ( a0 + b0 )/2 le centre de l’intervalle d’incertitude initial. Ensuite, évaluons f ′ ( x0 ). Si
f ′ ( x0 ) > 0, alors nous déduisons que le minimiseur se situe à gauche de x0 . En d’autres
termes, nous réduisons l’intervalle d’incertitude à [ a0 , x0 ]. En revanche, si f ′ ( x0 ) < 0,
alors nous déduisons que le minimiseur se situe à droite de x0 . Dans ce cas, nous rédui-
sons l’intervalle d’incertitude à [ x0 , b0 ]. Enfin, si f ′ ( x0 ) = 0, alors nous déclarons x0 être
le minimiseur et terminons notre recherche.
Avec le nouvel intervalle d’incertitude calculé, nous répétons le processus de ma-
nière itérative. À chaque itération k, nous calculons le centre de l’intervalle d’incerti-
tude. Appelons ce point xk . Selon le signe de f ′ ( xk ) (en supposant qu’il est non nul),
nous réduisons l’intervalle d’incertitude à gauche ou à droite de xk . Si à une itération k
quelconque nous trouvons que f ′ ( xk ) = 0, alors nous déclarons xk être le minimiseur et
terminons notre recherche.
Deux caractéristiques saillantes distinguent la méthode de dichotomie de la méthode
du nombre d’or. Premièrement, au lieu d’utiliser les valeurs de f , la méthode de dicho-
tomie utilise les valeurs de f ′ . Deuxièmement, à chaque itération, la longueur de l’in-
tervalle d’incertitude est réduite d’un facteur de 1/2. Ainsi, après n étapes, la plage est
réduite d’un facteur (1/2)n . Ce facteur est plus petit que dans la méthode du nombre
d’or. Enfin, notons que si nous laissons le paramètre γ de la méthode du nombre d’or
tendre vers 1/2, et que nous considérons une fonction objectif différentiable f , alors la
limite de la méthode du nombre d’or est la méthode de dichotomie.

38
Descente de gradient Algorithmes d’optimisation

2.4 Descente de gradient

Soit f : R p → R une fonction différentiable telle que ∇ f soit continue. Pour définir
l’algorithme de descente de gradient, nous devons choisir un paramètre h > 0 appelé
pas de gradient. Ensuite, en partant d’un point x0 ∈ R p , nous définissons la séquence
{ xk }k∈N en utilisant la règle de mise à jour suivante :

x k +1 = x k − h ∇ f ( x k ), k = 0, 1, . . . .

Pour expliquer la logique derrière cette méthode, considérons le cas simple où p = 1 et

où la fonction f est unimodale avec un point de minimum noté x∗ . Alors,

— si f ′ ( xk ) < 0, la fonction f décroît en xk . Cela implique que le minimiseur x ∗ est

à droite de xk . C’est pourquoi xk+1 est défini en ajoutant un nombre positif à xk .
De plus, si f ′ ( xk ) est grand, cela signifie que la pente de la tangente en xk est forte.
Par conséquent, nous pouvons faire un grand pas de xk vers la droite.
— si f ′ ( xk ) > 0, la fonction f croît en xk . Cela implique que le minimiseur x ∗ est à
gauche de xk . C’est pourquoi xk+1 est défini en soustrayant un nombre positif à
xk . De plus, si | f ′ ( xk )| est grand, cela signifie que la pente de la tangente en xk est
fortement négative. Par conséquent, nous pouvons faire un grand pas de xk vers
la gauche.
— si f ′ ( xk ) = 0, alors xk est un point stationnaire et, par conséquent, nous n’avons
pas besoin de nous déplacer ni vers la gauche ni vers la droite.

L’algorithme est illustré dans la Figure 2.4. Les propriétés de convergence de la descente
de gradient sont données dans les théorèmes suivants.

Théorème 2.2. Soit x∗ un minimiseur local de f . Supposons qu’il existe un ε > 0 tel que :
• le point initial x0 soit dans la boule B( x∗ , ε),
• f soit convexe et de classe C2 dans B( x∗ , ε),
• il existe M ∈]0, +∞[ tel que λmax (∇2 f ( x)) ⩽ M pour tout x ∈ B( x∗ , ε).
Alors, pour le pas de taille h ⩽ 2/M, toutes les itérations xk de l’algorithme de descente de
gradient se trouvent dans la boule B( x∗ , ε) et satisfont
 M 
f ( xk+1 ) ⩽ f ( xk ) − h 1 − h ∥∇ f ( xk )∥2 . (2.3)
2

Avant de présenter la preuve de ce théorème, faisons quelques remarques, et prou-

vons un lemme qui sera utilisé dans la démonstration du théorème.
Remarques

39
Descente de gradient Algorithmes d’optimisation

1. On peut choisir ε = ∥ x0 − x∗ ∥ ; alors, la première affirmation du théorème est que

les itérations successives de l’algorithme de descente de gradient seront au moins
aussi proches de x∗ que le point initial.
2. La deuxième affirmation du théorème nous dit qu’à chaque étape de l’algorithme,
nous diminuons la valeur de la fonction objective f , sauf si nous sommes déjà au
minimum local (c’est-à-dire, à moins que nous ayons xk = x∗ ).
3. Les affirmations du théorème impliquent que xk → x∗ lorsque k → ∞. En ef-
fet, considérons toute sous-suite convergente de { xk }, disons xnk → a. Alors,
par continuité de f et f ′ , nous déduisons de (2.3) que f ( a) ⩽ f ( a) − 12 h[ f ′ ( a)]2 .
Cela implique que f ′ ( a) = 0 et, par conséquent, a = x∗ . Ainsi, chaque sous-suite
convergente de { xk } converge vers x∗ . Par conséquent, xk → x∗ .
4. Le pas de gradient h est un paramètre de la méthode, dont le choix est très im-
portant. Si l’on choisit ce paramètre en minimisant par rapport à h le côté droit de
(2.3), on obtient h = 1/M.

Proof of Theorem 2.2. Nous commençons par prouver que toutes les itérations xk de l’al-
gorithme de descente de gradient restent dans la boule B( x∗ , ε). Nous prouvons cette
affirmation par récurrence. L’affirmation est vraie pour k = 0. Supposons maintenant
qu’elle soit vraie pour xk , c’est-à-dire ∥ xk − x∗ ∥ ⩽ ε, et prouvons-la pour xk+1 . Soit
u ∈ R p . Le théorème fondamental d’analyse appliqué à la fonction t 7→ u⊤ ∇ f ( x∗ +
t( xk − x∗ )) implique que
Z 1
⊤ ⊤ ∗
u⊤ ∇2 f x∗ + t( xk − x∗ ) ( xk − x∗ ) dt


u ∇ f ( xk ) − u ∇ f ( x ) =
0
Z 1
= u⊤ ∇2 f x∗ + t( xk − x∗ ) dt ( xk − x∗ ).


0

Comme cette relation est vraie pour tout u ∈ R p , on a

Z 1
∗
∇2 f x∗ + t( xk − x∗ ) dt ( xk − x∗ ).


∇ f ( xk ) − ∇ f ( x ) =
|0 {z }
:=H

Il en résulte que

xk+1 − x∗ = xk − x∗ − hH( xk − x∗ ) = (I p − hH)( xk − x∗ ),

ce qui implique que

∥ xk+1 − x∗ ∥ ⩽ ∥|I p − hH∥| · ∥ xk − x∗ ∥ (2.4)

La matrice H est symétrique et positive. Ses valeurs propres sont donc entre 0 et M. Il
en découle que les valeurs propres de la matrice I p − hH sont entre 1 − hM et 1. Comme

40
Descente de gradient Algorithmes d’optimisation

h ⩽ 2/M, on en déduit que les valeurs propres de I p − hH sont entre −1 et 1. Par

conséquent, ∥|I p − hH∥| ⩽ 1. En combinant avec (2.4), il vient que xk+1 ∈ B( x∗ , ε).
Le théorème de Taylor vu au chapitre précédent implique que, pour tout x, y ∈
B ( x ∗ , ε ),
Z 1
⊤
⊤
f (y) − f ( x) − ∇ f ( x) (y − x) = ∇ f x + t(y − x) dt (y − x) − ∇ f ( x)⊤ (y − x)
0
Z 1
⊤
= ∇ f x + t(y − x) − ∇ f ( x) dt (y − x)
0
Z 1

⩽ ∇ f x + t(y − x) − ∇ f ( x) ∥y − x∥dt
0
Z 1
⩽M ∥t(y − x)∥ ∥y − x∥dt = 1
2 M ∥ y − x ∥2 .
0

Il en résulte que

f ( x k +1 ) − f ( x k ) − ∇ f ( x k ) ⊤ ( x k +1 − x k ) ⩽ 1
2 M ∥ x k +1 − x k ∥ 2 .

Comme par définition, xk+1 − xk = −h∇ f ( xk ), on arrive à

1
f ( xk+1 ) ⩽ f ( xk ) − h∥∇ f ( xk )∥2 + Mh2 ∥∇ f ( xk )∥2
2
 1 
= f ( xk ) − h 1 − Mh ∥∇ f ( xk )∥2 .
2
C’est ce qu’il fallait démontrer.

Théorème 2.3. Supposons que les conditions du Théorème 2.2 soient remplies. Alors, pour le
pas de taille h ⩽ 1/M, la sortie xK de l’algorithme de descente de gradient en K étapes satisfait
∥ x0 − x ∗ ∥2
f ( xK ) − f ( x∗ ) ⩽ .
2hK

Démonstration. Puisque f est une fonction convexe, elle vérifie l’inégalité f ( x∗ ) − f ( xk ) ⩾

∇ f ( xk )⊤ ( x∗ − xk ). Ceci peut être écrit de manière équivalente comme

f ( x k ) ⩽ f ( x ∗ ) − ∇ f ( x k ) ⊤ ( x ∗ − x k ).

En combinant cette inégalité avec Théorème 2.2, nous obtenons

 M 
f ( xk+1 ) ⩽ f ( x∗ ) − ∇ f ( xk )⊤ ( x∗ − xk ) − h 1 − h ∥∇ f ( xk )∥2
2
h
⩽ f ( x∗ ) − ∇ f ( xk )⊤ ( x∗ − xk ) − ∥∇ f ( xk )∥2 .
2
En ajoutant et en soustrayant le terme ∥ x∗ − xk ∥2 /(2h), nous obtenons

∗ ∥ x ∗ − x k ∥2 1
∥ x∗ − xk ∥2 + 2h∇ f ( xk )( x∗ − xk ) + h2 ∥∇ f ( xk )∥2 .


f ( x k +1 ) ⩽ f ( x ) + −
2h 2h | {z }
∥ x∗ − xk + h∇ f ( xk )∥2

41
Descente de gradient Algorithmes d’optimisation

Cela nous donne

∥ x ∗ − x k ∥ 2 ∥ x ∗ − x k +1 ∥ 2
f ( x k +1 ) ⩽ f ( x ∗ ) + − .
2h 2h
En écrivant la dernière inégalité pour chaque k = 0, 1, . . . , K − 1 et en moyennant toutes
les inégalités obtenues, nous arrivons à
K −1
1 ∥ x ∗ − x0 ∥2 ∥ x ∗ − x K ∥2
K ∑ f ( x k +1 ) ⩽ f ( x ∗ ) +
2hK
−
2hK
.
k =0

Pour compléter la preuve, il suffit de remarquer qu’au vu du Théorème 2.2, tous les
termes f ( xk+1 ) sont supérieurs ou égaux à f ( xK ).

Il s’avère qu’on peut obtenir un résultat encore meilleur si la fonction f est fortement
convexe dans le voisinage de x∗ . La constante de forte convexité est notée m > 0.

Théorème 2.4. Supposons que les conditions du Théorème 2.2 sont remplies et, de plus, que f
est m-fortement convexe dans B( x∗ , ε), c’est-à-dire
m
f ( x) ⩾ f (y) + ∇ f (y)⊤ ( x − y) + ∥ x − y ∥2 , pour tout x, y ∈ B( x∗ , ε).
2
Alors, pour le pas h ⩽ 1/M, la sortie xK de l’algorithme de descente de gradient en K étapes
satisfait

f ( xK ) − f ( x∗ ) ⩽ (1 − mh)K f ( x0 ) − f ( x∗ ) ,

∥ xK − x∗ ∥ ⩽ (1 − mh)K ∥ x0 − x∗ ∥.

Démonstration. Nous commençons par prouver que la forte convexité de f implique que

∥∇ f ( xk )∥2 ⩾ 2m f ( xk ) − f ( x∗ ) .


(2.5)

En effet, la forte convexité implique que

m ∗
f ( x∗ ) ⩾ f ( xk ) + ∇ f ( xk )⊤ ( x∗ − xk ) + ∥ x − x k ∥2
2
1 1 2
= f ( xk ) − ∥∇ f ( xk )∥2 + ∇ f ( xk ) + m( x∗ − xk )
2m 2m
1
⩾ f ( xk ) − ∥∇ f ( xk )∥2 .
2m
En réarrangeant les termes de cette inégalité, nous obtenons (2.5). En combinant (2.5)
avec (2.3), nous arrivons à :
h
f ( xk+1 ) ⩽ f ( xk ) − ∥∇ f ( xk )∥2
2
⩽ f ( xk ) − mh f ( xk ) − f ( x∗ ) .

42
Méthode de Newton Algorithmes d’optimisation

Cela nous mène directement à

f ( xk+1 ) − f ( x∗ ) ⩽ (1 − mh) f ( xk ) − f ( x∗ ) .

En appliquant cette inégalité pour k = 0, . . . , K − 1, nous obtenons f ( xK ) − f ( x∗ ) ⩽

(1 − mh)K f ( x0 ) − f ( x∗ ) .

Pour démontrer la seconde assertion du théorème, on se rappelle qu’au vu de (2.4),

∥ xk+1 − x∗ ∥ ⩽ ∥|I p − hH∥| · ∥ xk − x∗ ∥.

On peut démontrer que la m-forte convexité de f implique que la matrice ∇2 f ( x) a

toutes ses valeurs propres supérieures ou égales à m. Il en résulte que les valeurs propres
de I p − hH sont toutes entre (1 − Mh) ⩾ 0 et (1 − mh). Donc,

∥ xk+1 − x∗ ∥ ⩽ (1 − mh)∥ xk − x∗ ∥.

On peut donc conclure la preuve du théorème par récurrence sur k.

Remarque 2.1. L’algorithme de descente de gradient présente des avantages et des inconvé-
nients par rapport à l’algorithme de dichotomie vu dans les sections précédentes. Les principaux
avantages sont :
A1) Il est défini au cas où la fonction objectif est multivariée f : R p → R.
A2) Il est garanti de diminuer la valeur de la fonction objectif à chaque itération.
A3) Si les conditions du dernier théorème sont satisfaites, alors il converge exponentiellement
vite et, dans le cas univarié, sa vitesse de convergence est indépendante de la taille de
l’intervalle initial [ a, b].

Les principaux points faibles sont :

S1) Si la fonction f n’est pas convexe, nous n’avons pas d’information sur la vitesse de conver-
gence de xk vers x∗ .
S2) Il nécessite la forte convexité de f pour la convergence à vitesse exponentielle.

2.5 Méthode de Newton

Supposons dans cette partie que nous sommes confrontés au problème de minimiser
une fonction f d’une seule variable réelle x. Nous supposons maintenant qu’à chaque
point xk nous pouvons déterminer f ( xk ), f ′ ( xk ) et f ′′ ( xk ). Dans un voisinage de xk , nous
pouvons approcher f par une fonction quadratique de la forme

1 ′′
q( x ) = f ( xk ) + f ′ ( xk )( x − xk ) + f ( xk )( x − xk )2 .
2

43
Méthode de Newton Algorithmes d’optimisation

F IGURE 2.5 – Méthode de Newton : un cas favorable, f ′′ ( x ) > 0

Notez que q( xk ) = f ( xk ), q′ ( xk ) = f ′ ( xk ) et q′′ ( xk ) = f ′′ ( xk ). Ensuite, au lieu de mi-

nimiser f , nous minimisons son approximation q. La condition nécessaire d’ordre un
pour un minimiseur de q donne

0 = q′ ( x ) = f ′ ( xk ) + f ′′ ( xk )( x − xk ).

En notant par xk+1 la solution de la dernière équation, nous obtenons

f ′ ( xk )
x k +1 = x k − . (2.6)
f ′′ ( xk )

Définition 2.1. Nous dirons que xn est l’approximation de x ∗ obtenue par la méthode
de Newton après n itérations, si (2.6) est vrai pour k = 0, . . . , n − 1.

La méthode de Newton fonctionne bien si f ′′ ( x ) > 0 partout (voir Figure 2.5). Si

f ′′ ( x ) < 0 pour certains x, la méthode de Newton peut échouer à converger vers le
minimiseur (voir Figure 2.6). En fait, la méthode de Newton peut être vue comme un
moyen de pousser la première dérivée de f vers zéro.
La convergence de la méthode de Newton est assurée par le résultat suivant.

Théorème 2.5. Soit x ∗ un minimiseur local de f . Supposons que pour un r > 0 donné,
• le point initial x0 se trouve dans l’intervalle I := [ x ∗ − r, x ∗ + r ],
• f est m-fortement convexe dans I,
• f ′′′ est bornée dans I par une constante L, c’est-à-dire | f ′′′ ( x )| ⩽ L.

Si Lr < 2m, alors les itérations de la méthode de Newton satisfont

| xn − x ∗ | < | xn−1 − x ∗ | ⩽ r, ∀n ∈ N
  2n
∗ 2m Lr
| xn − x | ⩽ , ∀ n ∈ N.
L 2m

44
Méthode de Newton Algorithmes d’optimisation

F IGURE 2.6 – Méthode de Newton : un cas défavorable, f ′′ ( x ) < 0

Démonstration. La formule de Taylor implique qu’il existe t ∈ I tel que

1 ′′′
f ′ ( x ∗ ) − f ′ ( xn−1 ) − f ′′ ( xn−1 )( x ∗ − xn−1 ) = | f (t)|( x ∗ − xn−1 )2 . (2.7)
2
Puisque f a une dérivée seconde continue et est m-fortement convexe, nous avons
f ′′ ( xn−1 ) ⩾ m > 0. En divisant les deux côtés de (2.7) par le nombre positif f ′′ ( xn−1 )
et en utilisant le fait que f ′ ( x ∗ ) = 0 (la condition nécessaire de premier ordre), nous
obtenons
f ′ ( x n −1 ) ∗ | f ′′′ (t)|
+ x − x n −1 = · ( x ∗ − x n −1 )2 .
f ′′ ( xn−1 ) 2 f ′′ ( xn−1 )
| {z }
x ∗ − xn

Par conséquent, en utilisant le fait que f ′′′ est majoré par L et que f ′′ est minoré par m,
nous obtenons
L ∗
x ∗ − xn ⩽ ( x − x n −1 )2 . (2.8)
2m
À partir de cette inégalité, nous pouvons déduire les assertions du théorème par récur-
rence sur n. L’assertion est vraie pour n = 0. Supposons maintenant qu’elle soit vraie
pour n − 1, c’est-à-dire, en particulier,

| x n −1 − x ∗ | < | x n −2 − x ∗ | , (2.9)
  2n −1
∗ 2m Lr
| x n −1 − x | ⩽ . (2.10)
L 2m

Nous notons d’abord que, en considérant (2.8) et (2.9), nous avons x ∗ − xn < x ∗ −

45
Résumé du Chapitre 2 Algorithmes d’optimisation

xn−1 . Ensuite, en combinant (2.8) et (2.10), nous obtenons

L ∗
| xn − x ∗ | ⩽ ( x − x n −1 )2
2m
 2   2n −1  2
L 2m Lε
⩽
2m L 2m
  2n
2m Lr
⩽ .
L 2m
C’est bien ce qu’il fallait démontrer.

Quelques commentaires sont nécessaires ici.

1. Ce théorème montre que pour les «bonnes» fonctions f la méthode de Newton
a un taux de convergence très rapide ; elle est beaucoup plus rapide que le taux
exponentiel des méthodes vues précédemment. Par conséquent, en pratique, si
la méthode de Newton est applicable et que la fonction est fortement convexe, il
n’est pas nécessaire de chercher une autre méthode.
2. On peut utiliser une stratégie mixte d’optimisation : commencer par l’algorithme
de descente de gradient afin de rendre r suffisamment petit pour satisfaire l’inéga-
lité Lr < 2m puis appliquer la méthode de Newton pour améliorer la précision.
3. La méthode de Newton et le dernier théorème peuvent être étendus directement
au problème de minimisation d’une fonction multivariée :

x n = x n −1 − ∇ 2 f ( x n −1 ) −1 ∇ f ( x n −1 ).

Cependant, le calcul de la matrice Hessienne à chaque itération et, plus important

encore, l’inversion de cette matrice, est une opération coûteuse en calcul qui réduit
considérablement l’attractivité de la méthode de Newton dans des problèmes à
très grande échelle.

2.6 Résumé du Chapitre 2

Ce chapitre traite du problème d’approximation de la valeur

x ∗ ∈ arg min f ( x )
x ∈Ω
où Ω est un intervalle de R (Ω peut être égal à R) ou Ω est un ouvert de R p .

Méthode du nombre d’or

• Conditions d’applicabilité : Ω = [ a0 , b0 ] est un intervalle fini, f est unimodale dans

l’intervalle Ω.

46
Résumé du Chapitre 2 Algorithmes d’optimisation

• Paramètres d’entrée : x0 ∈ Ω, γ ∈ (0, 0.5) et n ∈ N.

• Algorithme : pour k = 1 : n, définir

a ) A = a k − 1 + γ ( bk − 1 − a k − 1 ) ,
b ) B = bk − 1 − γ ( bk − 1 − a k − 1 ) ,
c) si f ( A) < f ( B)
a k = a k −1 , bk = B
sinon
ak = A, bk = bk − 1
a + bk
d) xk = k .
2

• Garanties de convergence : | xn − x ∗ | ⩽ 0.5(1 − γ)n (b0 − a0 ).

√
3− 5
• Choix de γ pour réduire le nombre d’évaluations de fonction : γ = 2 ≈ 0.382.

Méthode de la dichotomie

• Conditions d’applicabilité : Ω = [ a0 , b0 ] est un intervalle fini, f est unimodale et conti-

nûment dérivable dans Ω.
• Paramètres d’entrée : n ∈ N.
• Algorithme : pour k = 1 : n, définir

a k − 1 + bk −1
a) xk =
2
′
b) si f ( xk ) > 0 alors a k = a k −1 , bk = x k
sinon ak = xk , bk = bk − 1 .

• Garanties de convergence : | xn − x ∗ | ⩽ 0.5n+1 (b0 − a0 ).

Descente de gradient

• Pour une fonction f : Ω → R continûment dérivable, la méthode de descente de

gradient est définie par

x n +1 = x n − h ∇ f ( x n ), n = 0, 1, . . .

où x0 est une valeur initiale donnée et h > 0 est un paramètre de la méthode

appelé pas de descente.
• Soit x∗ un minimiseur local de f . Supposons que pour un r > 0 donné,

47
Résumé du Chapitre 2 Algorithmes d’optimisation

• le point initial x0 se trouve dans la boule B( x∗ , r ),

• ∇ f est lipschitzienne dans B( x∗ , r ) avec la constante M, c’est-à-dire ∥∇ f ( x) −
∇ f (y)| ⩽ M∥ x − y∥.
Alors, pour le pas de descente
h ⩽ 1/M,
nous avons

h
f est convexe dans B( x∗ , r ) =⇒ f ( xk+1 ) ⩽ f ( xk ) − ∥∇ f ( xk )∥2
2

∥ x0 − x ∗ ∥2
f est convexe dans B( x∗ , r ) =⇒ f ( xk ) − f ( x∗ ) ⩽
2hk

f ( xk ) − f ( x∗ ) ⩽ (1 − hm)k f ( x0 ) − f ( x∗ )


f est m-fortement convexe
=⇒
dans B( x∗ , r ) ∥ xk − x∗ ∥ ⩽ (1 − hm)k ∥ xk − x∗ ∥.

Méthode de Newton

• Conditions d’applicabilité : ∇2 f existe et est inversible.

• La méthode est définie par

x n +1 = x n − ∇ 2 f ( x n ) −1 ∇ f ( x n ), n = 0, 1, . . .

où x0 est une valeur initiale donnée.

Soit x∗ un minimiseur local de f . Supposons que pour un r > 0 donné,
• le point initial x0 se trouve dans l’intervalle I := [ x ∗ − r, x ∗ + r ],
• f est m-fortement convexe dans I,
• f ′′′ est bornée dans I par une constante L, c’est-à-dire | f ′′′ ( x )| ⩽ L.
Si Lr < 2m, alors les itérations de la méthode de Newton satisfont
  2n
∗ 2m Lr
| xn − x | ⩽ , ∀ n ∈ N.
L 2m

48
 Optimisation sous contrainte : problèmes
3
avec des contraintes d’égalité

3.1 Introduction

Dans ce chapitre et le chapitre suivant, nous nous concentrerons sur une classe de
problèmes d’optimisation sous contraintes non linéaires qui peuvent être formulés comme

minimiser f ( x)
sous contrainte hi ( x) = 0, i = 1, . . . , m,
g j ( x) ⩽ 0, j = 1, . . . , n,

où x ∈ R p , f : R p → R, hi : R p → R, g j : R p → R, et m ⩽ p. En notation vectorielle, le
problème ci-dessus peut être représenté sous la forme standard suivante :

minimiser f ( x)
sous contrainte h( x) = 0,
g ( x) ⩽ 0,

où h : R p → Rm et g : R p → Rn . Comme d’habitude, nous adoptons la terminologie

suivante.

Définition 3.1. Tout point satisfaisant les contraintes est appelé une solution admissible.
Points réguliers Problèmes avec des contraintes d’égalité

L’ensemble de toutes les solutions admissibles,

{ x ∈ R p : h( x) = 0, g ( x) ⩽ 0},

est appelé un ensemble admissible.

Nous illustrons les problèmes que nous étudions dans cette partie en considérant
l’exemple numérique simple suivant.

Exemple 3.1. Considérez le problème d’optimisation

minimiser ( x1 − 1)2 + x2 − 2
sous contrainte x2 − x1 = 1, (3.1)
x1 + x2 ⩽ 2.

Ce problème est déjà sous la forme standard donnée précédemment, avec f ( x1 , x2 ) =

( x1 − 1)2 + x2 − 2, h( x1 , x2 ) = x2 − x1 − 1, et g( x1 , x2 ) = x1 + x2 − 2. La simplicité du
problème nous permet de le résoudre graphiquement (voir la Figure 3.1). Dans la figure,
l’ensemble de points qui satisfont aux contraintes (l’ensemble réalisable) est marqué par
la ligne solide épaisse. Les paraboles inversées représentent les ensembles de niveau de
la fonction-objectif f —plus l’ensemble de niveau est bas, plus la valeur de la fonction-
objectif est petite. Par conséquent, la solution peut être obtenue en trouvant l’ensemble
de niveau le plus bas qui intersecte l’ensemble admissible.
Dans ce cas, le minimiseur se trouve sur l’ensemble de niveau avec f = −1/4. Le
minimiseur de la fonction objectif est x∗ = [1/2, 3/2]⊤ .

3.2 Points réguliers

La classe de problèmes d’optimisation que nous analysons dans ce chapitre est

minimiser f ( x)
sous contrainte de h( x) = 0,

où h : R p → Rm , h = [ h1 , . . . , hm ]⊤ , et m ⩽ p. Nous supposons que la fonction h est

continûment différentiable, c’est-à-dire, h ∈ C1 . Nous introduisons la définition sui-
vante.

Définition 3.2. Un point x∗ satisfaisant les contraintes h( x∗ ) = 0 est dit être un point
régulier des contraintes si les vecteurs gradients ∇h1 ( x∗ ),. . ., ∇hm ( x∗ ) sont linéairement
indépendants. Lorsque m = 1, cela signifie que ∇h1 ( x∗ ) ̸= 0.

50
Points réguliers Problèmes avec des contraintes d’égalité

F IGURE 3.1 – Solution graphique au problème (3.1).

L’ensemble des contraintes d’égalité décrit une surface S = { x ∈ R p : h( x) = 0}.

En supposant que tous les points de S sont réguliers, la dimension de la surface S est
p − m.
Exemple 3.2. Soit p = 3 et m = 1 (c’est-à-dire, nous opérons dans R3 ). En supposant
que tous les points de S sont réguliers, l’ensemble S est une surface bidimensionnelle.
Par exemple, soit
h1 ( x) = x2 − x32 .
Notez que ∇h1 ( x) = [0, 1, −2x3 ]⊤ , et donc pour tout x ∈ R3 , ∇h1 ( x) ̸= 0. Dans ce cas,
dim S = dim{ x : h1 ( x) = 0} = p − m = 2.
Voir la Figure 3.2 pour une illustration graphique.

Exemple 3.3. Soit p = 3 et m = 2. En supposant la régularité, l’ensemble admissible S

est un objet unidimensionnel (c’est-à-dire, une courbe dans R3 ). Par exemple, soit
h1 ( x ) = x1 ,
h2 ( x) = x2 − x32 .
Dans ce cas, ∇h1 ( x) = [1, 0, 0]⊤ et ∇h2 ( x) = [0, 1, −2x3 ]⊤ . Ainsi, les vecteurs ∇h1 ( x) et
∇h2 ( x) sont linéairement indépendants dans R3 . Donc,
dim S = dim{ x : h( x) = 0} = p − m = 1.
Voir la Figure 3.3 pour une illustration graphique.

51
Condition de Lagrange et exemples Problèmes avec des contraintes d’égalité

F IGURE 3.2 – La surface représentant l’ensemble admissible de Example 3.2.

F IGURE 3.3 – La courbe représentant l’ensemble admissible de Example 3.3.

3.3 Condition de Lagrange et exemples

Dans cette section, nous présentons une condition nécessaire du premier ordre pour
les problèmes d’extrémum avec contraintes. Le résultat est souvent appelé théorème de
Lagrange.

Théorème 3.1. Soit x∗ un minimiseur (ou maximiseur) local de f : R p → R, sous contrainte

h( x) = 0, h : R p → Rm , m ⩽ p. Si x∗ est un point régulier, alors il existe λ∗ ∈ Rm tel que
m
∇ f ( x∗ ) + ∑ λ∗j ∇h j ( x∗ ) = 0.
j =1

Il est pratique d’introduire la fonction lagrangienne L : R p × Rm → R, donnée par

L( x, λ) = f ( x) + λ⊤ h( x).

Les coefficients du vecteur λ sont souvent appelés multiplicateurs de Lagrange. La

condition de Lagrange pour un minimiseur local x∗ peut être représentée en utilisant
la fonction lagrangienne comme

∇L( x∗ , λ∗ ) = 0

52
Condition de Lagrange et exemples Problèmes avec des contraintes d’égalité

pour un certain λ∗ , où le gradient est calculé par rapport à l’ensemble de l’argument

[ x∗ , λ∗ ]. Autrement dit, la condition nécessaire dans le théorème de Lagrange est équi-
valente à la condition nécessaire du premier ordre pour l’optimisation sans contrainte
appliquée à la fonction lagrangienne.
Nous ne donnerons pas la preuve de ce théorème tout de suite, mais présenterons
quelques exemples illustrant la puissance et les limites du théorème de Lagrange. Nous
commençons par un exemple qui montre l’importance de l’hypothèse que x∗ soit un
point régulier.

Exemple 3.4. Considérons le problème suivant :

minimiser x
sous contrainte de h( x ) = 0,

où 
2 si x < 0,
x ,



h( x ) = 0, si 0 ⩽ x ⩽ 1,


( x − 1)2 , si x > 1.


L’ensemble admissible est évidemment [0, 1]. Clairment, x ∗ = 0 est un minimiseur local.
Cependant, f ′ ( x ∗ ) = 1 et h′ ( x ∗ ) = 0. Par conséquent, x ∗ ne satisfait pas la condition
nécessaire dans le théorème de Lagrange. Notez, cependant, que x ∗ n’est pas un point
régulier, c’est pourquoi le théorème de Lagrange ne s’applique pas ici.

Exemple 3.5. Given a fixed area of cardboard, we wish to construct a closed cardboard
box with maximum volume. We can formulate and solve this problem using the La-
grange condition. Denote the dimensions of the box with maximum volume by x1 , x2 ,
and x3 , and let the given fixed area of cardboard be A. The problem can then be formu-
lated as
maximize x1 x2 x3
subject to x1 x2 + x1 x3 + x2 x3 − 0.5A = 0.
We denote f ( x) = − x1 x2 x3 and h( x) = x1 x2 + x1 x3 + x2 x3 − 0.5A. We have ∇ f ( x) =
−[ x2 x3 ; x1 x3 ; x1 x2 ]⊤ and ∇h( x) = [ x2 + x3 ; x1 + x3 ; x1 + x2 ]⊤ . Note that all feasible
points are regular in this case. By the Lagrange condition, the dimensions of the box
with maximum volume satisfy

x2 x3 − λ( x2 + x3 ) = 0,
x1 x3 − λ( x1 + x3 ) = 0,
x1 x2 − λ( x1 + x2 ) = 0,
x1 x2 + x1 x3 + x2 x3 = 0.5A,

53
Condition de Lagrange et exemples Problèmes avec des contraintes d’égalité

where λ ∈ R.
We now solve these equations. First, we show that that x1 , x2 , x3 , and λ are all non-
zero. Suppose that x1 = 0. By the constraints, we have x2 x3 = A/2. However, the
second and third equations in the Lagrange condition yield λx2 = λx3 = 0, which to-
gether with the first equation implies that x2 x3 = 0. This contradicts the constraints. A
similar argument applies to x2 and x3 .
Next, suppose that λ = 0. Then, the sum of the three Lagrange equations gives x2 x3 +
x1 x3 + x1 x2 = 0, which contradicts the constraints.
We now solve for x1 , x2 , and x3 in the Lagrange equations. First, multiply the first
equation by x1 and the second by x2 , and subtract one from the other. We arrive at
x3 λ( x1 − x2 ) = 0. Because neither x3 nor λ can be zero (see above), we conclude that
x1 = x2 . We similarly deduce that x2 = x3 . From the constraint equation, we obtain
√
x1 = x2 = x3 = A/6.
Notice that we have ignored the constraints that x1 , x2 , and x3 are positive so that we
can solve the problem using Lagrange’s theorem. However, there is only one solution
to the Lagrange equations, and the solution is positive. Therefore, if a solution exists for
the problem with positivity constraints on the variables x1 , x2 , and x3 , then this solu-
tion must necessarily be equal to the solution above obtained by ignoring the positivity
constraints.
Finally, let us underline the fact that, at this stage, the point we found is not necessa-
rily the local minimizer of f . The only claim that we can do is : if there is a local minimi-
√
zer of f in the feasible set, then this local minimizer is given by x1 = x2 = x3 = A/6.

We now consider another example showing that the set of feasible points satisfying
the Lagrange condition might contain several points. Furthermore, it contains not only
the local minimizers but also the local maximizers.

Exemple 3.6. Consider the problem of extremizing the objective function

f ( x) = x12 + x22

on the ellipse
S = x = [ x1 , x2 ]⊤ : h( x) = x12 + 2x22 = 1 .


We have " # " #

2x1 2x1
∇ f ( x) = , ∇h( x) = .
2x2 4x2
Therefore, for any point x satisfying the constraint x12 + 2x22 = 1, the vector ∇h( x) is
different from the zero vector. This implies that all the feasible points are regular. We

54
Condition de Lagrange et exemples Problèmes avec des contraintes d’égalité

write now the Lagrange condition ∇L( x, λ) = 0 as a system of 3 equations with three
unknowns :
2x1 + 2λx1 = 0,
2x2 + 4λx2 = 0,
x12 + 2x22 = 1.
From the first of the equations above, we get either x1 = 0 or λ = −1. For the case where
√
x1 = 0, the second and third equations imply that λ = −1/2 and x2 = ±1/ 2. For the
case where λ = −1, the second and third equations imply that x1 = ±1 and x2 = 0.
Thus, the points that satisfy the Lagrange condition for extrema are
" # " # " # " #
0 0 1 −1
x (1) = √ , x (2) = √ , x (3) = , x (4) = .
1/ 2 −1/ 2 0 0
Because
f ( x(1) ) = f ( x(2) ) = 1/2
and
f ( x (3) ) = f ( x (4) ) = 1
we conclude that if there are minimizers, then they are located at x(1) and x(2) and if
there are maximizers, then they are located at x(3) and x(4) . It turns out that, indeed, x(1)
and x(2) are minimizers and x(3) and x(4) are maximizers.

Finally, we consider a last example of application of Lagrange’s theorem, that allows

for a variational interpretation of the largest eigenvalue of a matrix.
Exemple 3.7. Consider the following problem :
maximize ∥Ax∥
(3.2)
subject to ∥ x∥ = 1.
Here, A is a n × p matrix with real entries and x is a vector from R p . This problem
is closely related to the statistical method called principal component analysis (PCA),
the goal of which is to find a good projection of a set of points belonging to a high-
dimensional space. Indeed, if we assume that the rows of A represent p points in the n
dimensional space 1 , then the solution to (3.2) is the direction maximizing the variance
of the projections.
In order to solve (3.2), we rewrite it in the equivalent form
maximize ∥Ax∥2 = |x⊤ A⊤
{z Ax}
=: f ( x)
2
subject to ∥ x∥ − 1 = 0.
| {z }
=:h( x)

1. Assume that these points are centered so that their baricenter is the origin.

55
Directions admissibles Problèmes avec des contraintes d’égalité

and define the Lagrangian function

L( x, λ) = x⊤ A⊤ Ax + λ(∥ x∥2 − 1).

To be continued.

3.4 Directions admissibles

Dans le cas de l’optimisition sous contrainte, lorsqu’on «se promève» dans le voisi-
nage très petit d’un point x0 qui se trouve dans Ω, on n’est pas garanti de rester dans Ω.
Cela peut dépendre de la direction dans laquelle le déplacement est effectué.

Définition 3.3. Soit d ∈ R p un vecteur de norme 1. On dit que d est admissible en x ∈ Ω,

s’il existe une fonction φ : [0, 1] → Ω de classe C1 et une constante µ > 0 telle que
1. φ(0) = x
2. φ′ (0) = µd.

Proposition 3.1. Si x∗ ∈ Ω est un point régulier, alors d est une direction admissible en x∗ si
et seulement si
d⊤ ∇h j ( x∗ ) = 0, j = 1, . . . , m.

Démonstration. Nous démontrerons uniquement le fait qu’une direction admissible en

x∗ est nécessairement orthogonale à tous les vecteurs ∇h j ( x∗ ), j = 1, . . . , m. La réci-
proque, hors programme, se démontre en faisant appel au théorème de la fonction im-
plicite.
Soit d une direction admissible et φ : [0, 1] → Ω une fonction vérifiant les propriétés
décrites dans la Définition 3.3. On sait que φ(t) ∈ Ω pour tout t ∈ [0, 1], ce qui implique
que h j ◦ φ(t) = 0 pour tout j = 1, . . . , m. Il en découle que

(h j ◦ φ)′ (t) = 0, ∀t ∈ [0, 1]. (3.3)

En utilisant la formule de la matrice jacobienne d’une fonction composée, on obtient

(h j ◦ φ)′ (t) = ∇h j ( φ(t))⊤ φ′ (t). En utilisant cette formule et en écrivant (3.3) en t = 0,
on obtient ∇h j ( φ(0))⊤ φ′ (0) = 0. La définition d’une direction admissible implique que
φ(0) = x∗ et φ′ (0) = µd. On obtient donc ∇h j ( x∗ )⊤ (µd) = 0 pour tout j = 1, . . . , m.
Comme µ > 0, on en déduit le résultat souhaité.

On souhaite maintenant relier la notion d’une direction admissible en un point x∗

à la fonction objectif f . Cela se fait dans le résultat suivant dans le cas où x∗ est un
minimiseur local de f .

56
Preuve du Théorème de Lagrange Problèmes avec des contraintes d’égalité

Proposition 3.2. Si x∗ ∈ Ω est un minimiseur local de f dans Ω et d est une direction admis-
sible en x∗ , alors

d⊤ ∇ f ( x∗ ) ⩾ 0.

Démonstration. Soit φ : [0, 1] → Ω une fonction de classe C1 satisfaisant les propriétés

enumérées dans la Définition 3.3. Comme x∗ est un minimiseur local de f , il existe δ > 0
tel que

f ( φ(t)) ⩾ f ( x∗ ), ∀t ∈ [0, δ]. (3.4)

La formule de Taylor implique que

f ( φ(t)) = f ( φ(0)) + t( f ◦ φ)′ (0) + o (t).

En combinant avec (3.4), on obtient

t( f ◦ φ)′ (0) + o (t) ⩾ 0.

Comme t > 0, on peut diviser les deux côtés de l’inégalité ci-dessus par t sans changer
le sens de l’inégalité et faire tendre t vers 0. On obtient ainsi

( f ◦ φ)′ (0) ⩾ 0.

En utilisant la formule de la matrice Jacobienne d’une fonction composée, ainsi que le

fait que φ(0) = x∗ et φ′ (0) = µd, on obtient

∇ f ( φ(0))⊤ φ′ (0) = ∇ f ( x∗ )⊤ (µd) ⩾ 0.

En divisant les deux côtés par la constante positive µ, il vient ∇ f ( x∗ )⊤ d = 0 ou, de

manière équivalente, d⊤ ∇ f ( x∗ ) = 0.

Corollaire 2. On peut déduire de la dernière proposition que si x∗ est un minimiseur local

de f dans Ω, x∗ est un point régulier des contraintes et d est une direction admissible en x∗ ,
alors d⊤ ∇ f ( x∗ ) = 0. En effet, il suffit de remarque que d’après la Proposition 3.1, si d est une
direction admissible alors −d est une direction admissible. Donc, la Proposition 3.2 implique
que d⊤ ∇ f ( x∗ ) ⩾ 0 et −d⊤ ∇ f ( x∗ ) ⩾ 0. Cela entraîne que d⊤ ∇ f ( x∗ ) = 0.

3.5 Preuve du Théorème de Lagrange

Supposons que x∗ vérifie les contraintes d’égalité, h j ( x∗ ) = 0 pour tout j = 1, . . . , m,

est un point régulier et est un minimiseur local de f dans Ω. Soit u la projection or-
thogonale de ∇ f ( x∗ ) sur le sous-espace vectoriel dans R p engendré par les vecteurs

57
Conditions du second ordre Problèmes avec des contraintes d’égalité

∇h1 ( x∗ ), . . . , ∇hm ( x∗ ). Le vecteur ∇ f ( x∗ ) − u est donc orthogonal à tous les vecteurs

∇ h1 ( x ∗ ), . . . , ∇ h m ( x ∗ ).
D’une part, la Proposition 3.1 implique que ∇ f ( x∗ ) − u définit une direction admis-
sible, dans le sens où la version normalisée de ce vecteur est une direction admissible.
En vertu du Corollaire 2, on a donc

(∇ f ( x∗ ) − u)⊤ ∇ f ( x∗ ) = 0. (3.5)

D’autre part, comme ∇ f ( x∗ ) − u est orthogonal à tout vecteur appartenant au sous-

espace vectoriel engendré par ∇h1 ( x∗ ), . . . , ∇hm ( x∗ ), il est orthogonal à u. Par consé-
quent,

(∇ f ( x∗ ) − u)⊤ u = 0. (3.6)

Les égalités (3.5) et (3.6) impliquent

(∇ f ( x∗ ) − u)⊤ (∇ f ( x∗ ) − u) = ∥∇ f ( x∗ ) − u∥2 = 0.

Donc ∇ f ( x∗ ) = u. Or u ∈ Vect(∇h1 ( x∗ ), . . . , ∇hm ( x∗ )). Il en découle qu’il existe λ∗ ∈

Rm tel que
m
∇ f ( x∗ ) + ∑ λ∗j ∇h j ( x∗ ) = 0.
j =1

C’est ce qu’il fallait démontrer.

3.6 Conditions du second ordre

Dans le cas où les fonctions h j est la fonction-objectif f sont deux fois continûment
différentiables, on peut énoncer la condition nécessaire et la condition siffisante du
second-ordre. A noter que ces conditions sont très similaires à celles qu’on a déjà vues
dans le cas d’un problème d’optimisation sans contraine.

Théorème 3.2 (Condition nécessaire du second ordre). Si toutes les fonctions f , h1 , . . . , hm

sont de classe C2 , x∗ est un point régulier des containtes et minimiseur local de f dans Ω, alors
il existe λ∗ ∈ Rm tel que
1. ∇ f ( x∗ ) + ∑m ∗ ∗
j=1 λ j ∇ h j ( x ) = 0,
2. Pour toute direction admissible d en x∗ , on a d⊤ ∇2 f ( x∗ ) + ∑m ∗ 2 ∗


j=1 λ ∇ h j ( x ) d ⩾ 0.

Démonstration. Nous donnerons ici une démonstration partielle du théorème. Soit x∗ un

minimiseur local de f dans Ω et soit d une direction admissible en x∗ . On a donc

d⊤ ∇h j ( x∗ ) = 0, ∀ j = 1, . . . , m.

58
Conditions du second ordre Problèmes avec des contraintes d’égalité

Comme c’est une direction admissible, il existe une fonction φ : [0, 1] → Ω de classe C1
et une constante µ > 0 telles que

φ (0) = x ∗ ; φ′ (0) = µd. (3.7)

Ce que l’on admettra sans démonstration, c’est que sous les conditions de ce théorème,
la fonction φ peut être choisie de classe C2 . On suppose donc dans toute la suite de cette
preuve que φ est deux-fois continûment différentiable sur [0, 1].
Le théorème de Lagrange implique qu’il existe un λ∗ ∈ R tel que
m
∇ f ( x ) + ∑ λ∗j ∇h j ( x∗ ) = 0.
∗
(3.8)
j =1

On pose
m
F (t) = f ◦ φ(t) + ∑ λ∗j (h j ◦ φ)(t).
j =1

Les faits que x∗ soit un minimiseur local de f dans Ω, et que φ(0) = x∗ , impliquent qu’il
existe δ > 0 pour lequel

F ( t ) ⩾ F (0), ∀t ∈ [0, δ].

La formule de Taylor nous permet d’affirmer que

F (t) = F (0) + tF ′ (0) + 21 t2 F ′′ (0) + o (t2 ).

En combinant les deux dernières relations, on obtient

t2 ′′
tF ′ (0) + F (0) + o (t2 ) ⩾ 0, ∀t ∈ [0, δ]. (3.9)
2
La formule de la dérivée d’une fonction composée implique que
m
F ′ (t) = ∇ f ( φ(t))⊤ φ′ (t) + ∑ λ∗j ∇h j ( φ(t))⊤ φ′ (t). (3.10)
j =1

Il en découle, en combinant avec (3.7), que

m
F ′ (0) = ∇ f ( φ(0))⊤ φ′ (0) + ∑ λ∗j ∇h j ( φ(0))⊤ φ′ (0)
j =1
m
=µ ∇ f ( x∗ )⊤ d +µ ∑ λ∗j ∇ h j ( x∗ )⊤ d = 0.
j =1
| {z } | {z }
=0 d’après le Cor. 2 =0 d’après la Prop. 3.1

On déduit de (3.9) que

t2 ′′
F (0) + o (t2 ) ⩾ 0, ∀t ∈ [0, δ].
2

59
Conditions du second ordre Problèmes avec des contraintes d’égalité

En divisant les deux côtés par t2 /2 et en faisant tendre t vers 0, on obtient

F ′′ (0) ⩾ 0.

Pour calculer la dérivée seconde de F, on dérive l’équation (3.10) :

F ′′ (t) = φ′ (t)⊤ ∇2 f ( φ(t)) φ′ (t) + ∇ f ( φ(t))⊤ φ′′ (t)

m  
+ ∑ λ∗j φ′ (t)⊤ ∇2 h j ( φ(t)) φ′ (t) + ∇h j ( φ(t))⊤ φ′′ (t) .
j =1

En remplaçant t par 0 et en regroupant les termes, on obtient

m
F ′′ (0) = µ2 d⊤ ∇2 f ( x∗ )d + µ2 ∑ λ∗j d⊤ ∇2 h j ( x∗ )d
j =1
n m o
+ ∇ f ( x∗ ) + ∑ λ∗j ∇h j ( x∗ ) ⊤ ′′
φ (0).
j =1
| {z }
=0 d’après (3.8)

On obtient donc
 m 
′′
F (0) = µ d 2 ⊤
∇ f ( x )d + ∑
2 ∗
λ∗j ∇2 h j ( x∗ ) d ⩾ 0,
j =1

ce qu’il fallait démontrer.

Exemple 3.8. L’objectif de cet exemple est de trouver la projection d’un point a dans R p
sur la sphère unitaire S = { x ∈ R p : ∥ x∥ = 1}. Cela revient à résoudre le problème
d’optimisation

minimiser ∥ x − a ∥2
sous contrainte ∥ x∥2 = 1.

Il s’agit d’un problème d’optimisation contraint avec des contraintes d’égalité. L’en-
semble admissible est la sphère unitaire S, la fonction de coût est f ( x) = ∥ x − a∥2 et
il y a seulement une contrainte donnée par la fonction h( x) = ∥ x∥2 − 1. Nous notons
d’abord que tous les points de l’ensemble admissible sont réguliers. En effet, si un point
x∗ est dans l’ensemble admissible, alors x∗ ̸= 0. Cela implique que

∇h( x∗ ) = 2x∗ ̸= 0.

Ainsi x∗ est régulier. L’étape suivante est d’écrire les conditions de Lagrange : si x∗ est
un minimiseur local, alors il existe λ∗ ∈ R tel que

∇ f ( x∗ ) + λ∗ ∇h( x∗ ) = 0.

60
Conditions du second ordre Problèmes avec des contraintes d’égalité

F IGURE 3.4 – Illustration de Example 3.8 dans le cas n = 2.

En calculant les gradients, nous obtenons 2( x∗ − a) + 2λ∗ x∗ = 0. Par conséquent,

a
x∗ = .
1 + λ∗
Puisque, de plus, x∗ doit satisfaire la contrainte h( x∗ ) = 0, nous obtenons

a
=1 ⇐⇒ 1 + λ∗ = ±∥ a∥.
1 + λ∗

Ainsi, il y a deux candidats pour résoudre le problème :

a a
x1∗ = et x2∗ = − .
∥ a∥ ∥ a∥
On vérifie facilement que f ( x1∗ ) < f ( x2∗ ). Par conséquent, seul x1∗ peut être un mini-
miseur local de f . Afin d’être sûr qu’il est effectivement un minimiseur local, nous vé-
rifions la condition suffisante du second ordre. La valeur de λ correspondant à x1∗ est
λ1∗ = ∥ a∥ − 1. Pour cette valeur, nous avons
 
∇2x,x f ( x1∗ ) + λ1∗ h( x1∗ ) = 2I p + 2λ1∗ I p = 2∥ a∥ I p ,

où I p est la matrice identité n × n. Le calcul ci-dessus montre que la matrice hessienne

∇2x,x f ( x1∗ ) + λ1∗ ∇h( x1∗ ) est définie positive. Par conséquent, la CSOD est satisfaite et

x1∗ = a/∥ a∥ est le seul minimiseur local de f sous la contrainte h( x) = 0. En conclusion,

si nous voulons projeter un point a sur la sphère unitaire, il suffit de diviser a par sa
norme.

Théorème 3.3 (Condition suffisante du second ordre). Soit D ⊆ R p un ouvert et f , h1 , . . . , hm :

D → R de classe C2 . Soit x∗ ∈ Ω un point régulier des containtes. S’il existe λ∗ ∈ Rm tel que
1. ∇ f ( x∗ ) + ∑m ∗ ∗
j=1 λ j ∇ h j ( x ) = 0,

61
Résumé du Chapitre 3 Problèmes avec des contraintes d’égalité

2. Pour toute direction admissible d en x∗ , on a d⊤ ∇2 f ( x∗ ) + ∑m ∗ 2 ∗

j=1 λ ∇ h j ( x ) d > 0,
alors x∗ est un minimiseur local strict de f dans Ω.

Ce résultat sera admis sans démonstration.

3.7 Résumé du Chapitre 3

Le problème considéré dans ce chapitre est

minimiser f ( x)
sous contrainte hi ( x) = 0, i = 1, . . . , m,
où x ∈ R p , f : R p → R, h j : R p → R, j = 1, . . . , m, et m ⩽ n. En notation vectorielle, le
problème est le suivant :
minimiser f ( x)
sous contrainte h( x) = 0,
où h : R p → Rm est de classe C1 .

Point régulier et direction admissible

• On dit que le point x∗ satisfaisant les contraintes h( x∗ ) = 0 est un point régulier

des contraintes si les vecteurs gradients ∇h1 ( x∗ ), . . ., ∇hm ( x∗ ) sont linéairement
indépendants. Lorsque m = 1, cela signifie que ∇h1 ( x∗ ) ̸= 0.
• On dit que 2 d ∈ S p−1 est admissible en x ∈ Ω, s’il existe une fonction φ : [0, 1] →
Ω de classe C1 et une constante µ > 0 telle que
1. φ(0) = x
2. φ′ (0) = µd.

Propriétés importantes

• Si x ∈ Ω est un point régulier, alors d est une direction admissible en x si et seule-

ment si
d⊤ ∇h j ( x) = 0, ∀ j = 1, . . . , m.
• Si x∗ ∈ Ω est un minimiseur local de f dans Ω et d est une direction admissible en
x∗ , alors
d⊤ ∇ f ( x∗ ) ⩾ 0.
Si, de plus, x∗ est régulier, alors d⊤ ∇ f ( x∗ ) = 0.
2. S p−1 est la sphère de rayon 1 centrée en 0 p de R p .

62
Résumé du Chapitre 3 Problèmes avec des contraintes d’égalité

Théorème de Lagrange

Soit x∗ un minimiseur (ou maximiseur) local de f : R p → R, sous contrainte h( x) =

0, h : R p → Rm , m ⩽ p. Si x∗ est un point régulier, alors il existe λ∗ ∈ Rm tel que
m
∇ f ( x∗ ) + ∑ λ∗j ∇h j ( x∗ ) = 0.
j =1

Ce théorème est également appelé «théorème des extrema liés».

Vocabulaire

• La fonction lagrangienne ou le lagrangien : L : R p × Rm → R, donnée par

L( x, λ) = f ( x) + λ⊤ h( x).

• Les coefficients du vecteur λ sont appelés multiplicateurs de Lagrange.

Condition nécessaire de second ordre

Soit D ⊆ R p un ouvert. Soit f , h1 , . . . , hm : D → R des fonctions de classe C2 . Soit x∗

un minimiseur local de f dans Ω := { x ∈ D : h( x) = 0m }. Si x∗ est un point régulier
des containtes, alors il existe λ∗ ∈ Rm tel que
m
1. ∇ f ( x∗ ) + ∑ λ∗j ∇h j ( x∗ ) = 0,
j =1
m
2. Pour toute direction admissible d en x∗ , d⊤ ∇2 f ( x∗ ) + ∑ λ∗ ∇2 h j ( x∗ ) d ⩾ 0.


j =1

Condition suffisante de second ordre

Soit D ⊆ R p un ouvert et f , h1 , . . . , hm : D → R de classe C2 . Soit x∗ ∈ Ω un point

régulier des containtes. S’il existe λ∗ ∈ Rm tel que
m
1. ∇ f ( x∗ ) + ∑ λ∗j ∇h j ( x∗ ) = 0,
j =1
m
2. Pour toute direction admissible d en x∗ , d⊤ ∇2 f ( x∗ ) + ∑ λ∗ ∇2 h j ( x∗ ) d > 0,


j =1
alors x∗ est un minimiseur local strict de f dans Ω.

63
 Problèmes avec des contraintes
4
d’inégalité

4.1 Formulation du problème et définitions

Dans le chapitre précédent, nous avons analysé des problèmes d’optimisation sous
contrainte contenant uniquement des contraintes d’égalité. Dans ce chapitre, nous dis-
cutons des problèmes de minimisation qui contiennent également des contraintes d’in-
égalité. Comme nous le verrons, les problèmes avec des contraintes d’inégalité peuvent
également être traités à l’aide de multiplicateurs de Lagrange.
Soit D ⊆ R p un ensemble ouvert. On considère le problème suivant

minimiser f ( x) (4.1)
sous les contraintes h( x) = 0m ,
g ( x) ⩽ 0n ,

où f : D → R, h : D → Rm , m ⩽ p et g : D → Rn . L’ensemble réalisable dans ce cas est

donné par

Ω = x ∈ D : h( x) = 0m et g ( x) ⩽ 0n .


Pour le problème général (4.1), on adopte les definitions suivantes.

Théorème de Karush-Kuhn-Tucker Problèmes avec des contraintes d’inégalité

Définition 4.1. Une contrainte d’inégalité gi ( x) ⩽ 0 est dite active (ou saturée) en x∗ si
gi ( x∗ ) = 0. Elle est inactive en x∗ si gi ( x∗ ) < 0.

Par convention, nous considérons qu’une contrainte d’égalité h j ( x) = 0 est toujours

active.

Définition 4.2. Soit x∗ tel que h( x∗ ) = 0m , g ( x∗ ) ⩽ 0n , et soit I0 ( x∗ ) l’ensemble des

indices des contraintes d’inégalité actives :

I0 ( x∗ ) := {i : gi ( x∗ ) = 0}.

Alors, nous disons que x∗ est un point régulier si les vecteurs

∇ h j ( x ∗ ) , ∇ gi ( x ∗ ) , 1 ⩽ j ⩽ m, i ∈ I0 ( x∗ )

sont linéairement indépendants.

4.2 Théorème de Karush-Kuhn-Tucker

Nous énonçons maintenant une condition nécessaire de premier ordre pour qu’un
point soit un minimiseur local. Nous appelons cette condition la condition de Karush-
Kuhn-Tucker (KKT). Dans la littérature, cette condition est parfois aussi appelée la
condition de Kuhn-Tucker.

Théorème 4.1 (Théorème de Karush-Kuhn-Tucker (KKT)). Soit f , h, g ∈ C 1 . Soit x∗ un

point régulier et un minimiseur local pour le problème de minimisation de f sous les contraintes
h( x) = 0m , g ( x) ⩽ 0n . Alors, il existe λ∗ ∈ Rm et µ∗ ∈ Rn tels que :
[KKT-1] µ∗ ⩾ 0.
 
[KKT-2] ∇ x f ( x∗ ) + λ∗ ⊤ h( x∗ ) + µ∗⊤ g ( x∗ ) = 0 p .
[KKT-3] µi∗ gi ( x∗ ) = 0 pour tout i = 1, . . . , n.

Dans le Theorem 4.1, nous désignons λ∗ comme le vecteur des multiplicateurs de

Lagrange et µ∗ comme le vecteur des multiplicateurs de Karush-Kuhn-Tucker (KKT).
Nous nous référons à leurs composantes comme des multiplicateurs de Lagrange et des
multiplicateurs de Karush-Kuhn-Tucker (KKT), respectivement.

Démonstration. Nous allons démontrer le théorème de Karush-Kuhn-Tucker. Soit x∗ un

point qui satisfait les conditions du théorème. Définissons les deux ensembles suivants
 \ 
c ∗ −1
gi (] − ∞, 0[]) ,

D0 = x ∈ D : gi ( x) < 0, ∀i ∈ I0 ( x ) = D ∩
i ̸∈ I0 ( x∗ )

Ω0 = x ∈ D0 : h( x) = 0m ; gi ( x) = 0, ∀i ∈ I0 ( x∗ ) .


66
Théorème de Karush-Kuhn-Tucker Problèmes avec des contraintes d’inégalité

L’ensemble D0 étant défini comme une intersection d’un nombre fini d’ensembles ou-
verts, est un ouvert de R p . De plus, comme x∗ est un miniseur local de f dans Ω et
x∗ ∈ Ω0 ⊆ Ω, x∗ sera également un minimiseur local de f dans Ω0 . Or, la minimisa-
tion de f dans Ω0 est un problème d’optimisation qui ne comporte que des contraintes
d’égalité. En outre, la definition d’un point régulier dans le cas où des contraintes d’in-
égalité sont présentes implique que x∗ est un point régulier de Ω0 également. On peut
donc utiliser le théorème de Lagrange pour établir l’existance d’un vecteur λ∗ ∈ Rm et
de constantes µi∗ ∈ R pour i ∈ I0 ( x∗ ) tels que
n m o
∇ f (x ) + ∑
∗
λ∗j h j ( x∗ ) + ∑ µi∗ gi ( x∗ ) = 0p.
j =1 i ∈ I0 ( x∗ )

En complétant par des zéros, on peut définir le vecteur µ∗ comme un élément de Rn

(c’est-à-dire µi∗ = 0 pour i ∈ I0c ( x∗ )). Ce vecteur vérifie clairement les conditions [KKT-
2] et [KKT-3]. La démonstration du fait que ce vecteur µ∗ vérifie également la condition
[KKT-1] repose sur le lemme de Farkas, hors programme.

Exemple 4.1. Considérons le problème

minimiser f ( x1 , x2 ) = x12 + x22 + x1 x2 − 3x1

sous les contraintes x1 ⩾ 0, x2 ⩾ 0.

Dans ce problème, il n’y a pas de multiplicateur de Lagrange car il n’y a pas de contrainte
d’égalité. En revanche, il y a deux contraintes d’inégalité, ce qui implique qu’il faut in-
troduire deux multiplicateurs de KKT notés µ1 , µ2 .
Les conditions KKT pour ce problème sont

µ1 ⩾ 0, µ2 ⩾ 0,
" # " #
1 0
∇ f ( x1 , x2 ) − µ1 − µ2 = 0,
0 1
µ1 x1 + µ2 x2 = 0.

De plus
∇ f ( x) = [2x1 + x2 − 3, x1 + 2x2 ]⊤ ,
ce qui entraîne que

2x1 + x2 − µ1 = 3,
x1 + 2x2 − µ2 = 0,
µ1 x1 + µ2 x2 = 0.

67
Méthode de résolution générale Problèmes avec des contraintes d’inégalité

Nous avons donc quatre inconnues, trois équations et des contraintes d’inégalité pour
chacune des quatre inconnues. Pour trouver une solution (µ∗ , x∗ ), on considère d’abord
le cas
µ1∗ = 0, x2∗ = 0.
On a alors
3 3
x1∗ = , µ2∗ = .
2 2
Ces valeurs de x∗ et µ∗ vérifient toutes les conditions KKT.
De même, dans le cas
µ2∗ = 0, x1∗ = 0,
il vient
x2∗ = 0, µ1∗ = −3.
Ces valeurs ne vérifient pas la contrainte de positivité de µ1∗ . Donc, dans ce cas, les
conditions KKT n’ont pas de solution.
On peut donc conclure du Théorème de KKT que si le problème d’optimisation consi-
déré a une solution, celle-ci est donnée par x∗ = ( 23 ; 0).

4.3 Méthode de résolution générale

Le but de cette partie est de décrire une méthode générale, reposant sur le Théo-
rème de KKT, qui permet de résoudre les problèmes d’optimisation sous des contraintes
d’égalité et d’inégalité. Les différentes étapes de la méthodes sont les suivantes :
1. Ecrire le problème sous la forme canonique : déterminer f , g, h et D . Rappelons
que la forme canonique est

minimiser f ( x)

x ∈ D



sous les contraintes h( x) = 0m


 g ( x) ⩽ 0n .


2. Montrer que le problème a une solution. Pour cela, il peut y avoir deux cas de
figure.
Cas A : La fonction f est continue et les contraintes définissent un ensemble fermé
et borné, donc compact. Le Théorème de Weierstrass implique alors que f
admet son minimum dans Ω.
Cas B : La fonction f est continue, lim∥ x∥→∞ f ( x) = +∞ et les contraintes définissent
un ensemble fermé. Dans ce cas aussi, f admet son minimum dans Ω.

68
Méthode de résolution générale Problèmes avec des contraintes d’inégalité

3. Déterminer les points réguliers des contraintes. Mettre de côté les points qui ne le
sont pas. On les utilisera à l’étape 6.
4. Ecrire le lagrangien du problème et calculer son gradient par rapport à la variable
de minimisation.
5. Ecrire les conditions KKT et trouver tous les points réguliers qui vérifient ces
contraintes.
6. Evaluer f en tout point trouvé dans la question précédente, ainsi qu’en tout x qui
n’est pas régulier.
7. Conclure, en disant que les points considérés à l’étape précédentes qui conduisent
à la plus petite valeur de f sont les minima globaux de f dans Ω.
Appliquons cette méthode au problème suivant :
max x2 + y
sous les contraintes x ⩾ 0, y ⩾ x2 , x + y = 1.
1. On a p = 2, m = 1, n = 2,
f ( x, y) = − x2 − y,
h( x, y) = x + y − 1,
g1 ( x, y) = − x,
g2 ( x, y) = x2 − y.

2. Il est clair que la fonction f est continue.

De plus, l’ensemble défini par les contraintes est borné. En effet, x ⩾ 0 et y2 ⩾ x
impliquent que min( x, y) ⩾ 0. En outre, x + y = 1 implique que max( x, y) ⩽ 1.
Enfin, comme Ω est l’image réciproque de l’ensemble fermé ) − ∞, 0]×] − ∞, 0] ×
{0} par l’application continue ( g1 , g2 , h) : R2 → R3 , Ω est fermé.
En vertue du Théorème de Weierstrass, f admet son minimum dans Ω.
3. Commençons par calculer les gradients des fonctions h, g1 et g2 :
" # " # " #
1 −1 2x
∇h( x, y) = ; ∇ g1 ( x, y) = ; ∇ g2 ( x, y) = .
1 0 −1
1er cas : Aucune des deux contraintes d’inégalité n’est saturée.
Dans ce cas, ( x, y) est régulier car la famille {∇h( x, y) = (1; 1)⊤ } est libre.
2e cas : g1 ( x, y) = 0.
On a alors x = 0, ce qui implique que y = 1, grâce à la contrainte d’éga-
lité. Par conséquent, dans ce cas la seconde contrainte d’inégalité ne peut pas
être saturée. On doit donc vérifier l’indépendance linéaire des deux vecteurs
∇h(0, 1) et ∇ g1 (0, 1). Dans ce problème, cette indépendance est évidente car
les vecteurs (1; 1)⊤ , (−1; 0)⊤ ne sont clairement pas colinéaires. Il en résulte
que tout point ( x, y) ∈ Ω tel que x = 0 est régulier.

69
Méthode de résolution générale Problèmes avec des contraintes d’inégalité

3e cas : x > 0 et g2 ( x, y) = 0.
La famille
" # " #
1 2x
∇h( x, y) = ; ∇h( x, y) =
1 −1
est libre car la condition x > 0 exclue le cas de colinéarité x = −1/2.
Conclusion de cette étape : tout point ( x, y) ∈ Ω est un point régulier des contraintes.
4. Le lagrangien est donné par

L( x, y; λ, µ1 , µ2 ) = − x2 − y + λ( x + y − 1) − µ1 x + µ2 ( x2 − y).
Son gradient par rapport à ( x, y) est donné par
" #
−2x + λ − µ1 + 2µ2 x
∇ x,y L( x, y; λ, µ1 , µ2 ) = .
−1 + λ − µ2
5. Les conditions KKT sont données par

µ1 ⩾ 0, µ2 ⩾ 0,
2x (µ2 − 1) + λ − µ1 = 0 (4.2)
− 1 + λ − µ2 = 0 (4.3)
µ1 x = 0 (4.4)
µ2 ( x 2 − y ) = 0 (4.5)
2
x ⩾ 0, y⩾x
x + y = 1. (4.6)

On déduit de (4.4) que µ1 = 0 ou x = 0. De même, on déduit de (4.5) que µ2 = 0

ou y = x2 . On a donc quatre cas à considérer.
1er cas : x = 0 et y = x2 .
Dans ce cas, on obtient y = 0, donc la contrainte x + y = 1 n’est pas satisfaite. Cela
implique que dans ce cas il n’y a pas de point satisfaisant les conditions KKT.
2e cas : x = 0 et µ2 = 0.
En utilisant (4.2), (4.3) et (4.6), respectivement, on obtient λ = µ1 , λ = 1 et y = 1.
Il y a donc une seule solution des conditions KKT donnée par

( x ∗ , y∗ , λ∗ , µ1∗ , µ2∗ ) = (0; 1; 1; 1; 0).

3e cas : µ1 = 0 et y = x2 .
La condition (4.6) implique alors que x2 + x − 1 = 0. Cette équation a deux solu-
tions, dont une seule vérifie la contrainte de positivité. On trouve donc
√
5−1
x= .
2

70
KKT et convexité Problèmes avec des contraintes d’inégalité

Les équations (4.2) et (4.3) entraînent que µ2 = λ − 1 et

2x (λ − 2) + λ = 0.

Il en découle que
√ √
4x 2 5−2 10 − 2 5
λ= = √ = .
2x + 1 5 5
On en déduit que
√
5−2 5
µ2 = >0
5

Conclusion : il y a une solution des conditions KKT donnée par

√ √ √ √ 
∗ ∗ ∗ ∗ ∗ 5 − 1 3 − 5 10 − 2 5 5−2 5
( x , y , λ , µ1 , µ2 ) = ; ; ; 0; .
2 2 5 5

4e cas : µ1 = 0 et µ2 = 0.
On a alors λ = 1 d’après (4.3) et x = 1/2 d’après (4.2). La condition (4.6) implique
que y = 1/2. Cela définit un autre point qui vérifie les conditions KKT :

( x ∗ , y∗ , λ∗ , µ1∗ , µ2∗ ) = 12 ; 12 ; 1; 0; 0 .

6. On a
√ √ 
5−1 3− 5 √
f 12 , 12 = −3/4.


f (0, 1) = −1, f ; = 5 − 3,
2 2
√ √

5−1 3− 5
Par conséquent, les points ( x, y) = 2 ; 2 et ( x, y) = ( 12 , 12 ) ne peuvent pas
être un point de minimum de f dans Ω.
7. On sait que le problème a une solution.√Le Théorème
√
KKT implique que cette
5−1 3− 5 1 1

solution appartient à l’ensemble (0, 1); 2 ; 2 ; ( 2 , 2 ) . Dans cet ensemble,
les deux derniers points ne sont pas des minimiseurs de la fonction f .
Par conséquent, le problème a une seule solution donnée par ( x ∗ , y∗ ) = (0, 1). La
valeur minimale de f est alors égale à −1.

4.4 Conditions KKT dans des problèmes convexes

Supposons qu’on considère le problème

minimiser f ( x)

x ∈ D
sous les contraintes
 h( x) = 0m , g ( x) ⩽ 0n .

71
KKT et convexité Problèmes avec des contraintes d’inégalité

L’ensemble des x ∈ R p qui vérifient toutes les contraintes ci-dessus sera noté Ω. Rap-
pelons que D est un ouvert de R p alors que les fonctions f , g, h définies sur D sont de
classe C1 .
Nous nous plaçons ici dans le cas particulier où l’ensemble réalisable Ω est convexe
et la fonction f est également convexe. Nous montrerons que dans ce cas particulier les
conditions KKT sont non seulement nécessaires mais également suffisantes. Pour cela,
commençons par deux résultats auxiliaires.

Lemme 4.1. Soit D un ouvert de R p et h : D → Rm une fonction de classe C1 . Si Ω ⊆ D est

convexe et inclus dans h−1 (0), alors

∇h( x)⊤ (y − x) = 0, ∀ x, y ∈ Ω.

Démonstration. Nous fixons deux points x, y ∈ Ω. Comme Ω est convexe, on a

x + t(y − x) = (1 − t) x + ty ∈ Ω ⊆ h−1 (0).

Par conséquent


h x + t(y − x) = 0 (4.7)

Définissons la fonction ψ : [0, 1] → R par ψ(t) = h( x + t(y − x)). D’après (4.7), il vient
ψ(t) = 0 pour tout t ∈ [0, 1]. Nous pouvons en déduire que

ψ′ (t) = 0, ∀t ∈ [0, 1].

En outre, la règle de différentiation d’un fonction composée implique que

⊤
ψ ′ ( t ) = ∇ h x + t ( y − x ) ( y − x ).

En remplaçant dans cette égalité t = 0, nous obtenons le résultat énoncé dans le lemme.

Lemme 4.2. Soit D un ouvert de R p et g : D → R une fonction de classe C1 . Si Ω ⊆ D est

convexe et inclus dans g−1 (] − ∞, 0]), alors pour tout x ∈ Ω satisfaisant g( x) = 0,

∇ g( x)⊤ (y − x) ⩽ 0, ∀y ∈ Ω.

Démonstration. Nous fixons deux points x, y ∈ Ω tels que g( x) = 0. Comme Ω est

convexe, on a

x + t(y − x) = (1 − t) x + ty ∈ Ω ⊆ g−1 (] − ∞, 0]).

Par conséquent


g x + t(y − x) ⩽ 0, ∀t ∈ [0, 1]. (4.8)

72
KKT et convexité Problèmes avec des contraintes d’inégalité

Définissons la fonction ψ : [0, 1] → R par ψ(t) = g( x + t(y − x)). D’après (4.8), il vient
ψ(t) ⩽ 0 pour tout t ∈ [0, 1]. De plus, ψ(0) = g( x) = 0. Nous pouvons en déduire que
ψ(t)
ψ′ (0) = lim ⩽ 0.
t →0 t

En outre, la règle de différentiation d’un fonction composée implique que

⊤
ψ ′ ( t ) = ∇ g x + t ( y − x ) ( y − x ).

En remplaçant dans cette égalité t = 0, nous obtenons le résultat énoncé dans le lemme.

Maintenant nous sommes en mesure d’énoncer et de démontrer le résultat principal.

Théorème 4.2. Soit D est un ouvert de R p et f : D → R, g : D → Rn , h : D → Rm des

fonctions de classe C1 . Supposons que la fonction f et l’ensemble réalisable

Ω = { x ∈ D : h( x) = 0, g ( x) ⩽ 0}

sont convexes. Si x∗ ∈ Ω satisfait les conditions KKT, alors x∗ est un minimiseur global de f
dans Ω.

Démonstration. Comme f est convexe, on a

f ( x ) ⩾ f ( x ∗ ) + ∇ f ( x ∗ ) ⊤ ( x − x ∗ ), ∀ x ∈ Ω. (4.9)

Comme x∗ vérifie les conditions KKT, il existe µ∗ ∈ Rn+ et λ∗ ∈ Rm tels que

m
∇ f ( x∗ ) = − ∑ µi∗ ∇ gi ( x∗ ) − ∑ λ∗j ∇h j ( x∗ ). (4.10)
i ∈ I0 ( x∗ ) j =1

En combinant (4.9) et (4.10), on obtient

m
f ( x) ⩾ f ( x∗ ) − ∑ µi∗ ∇ gi ( x∗ )⊤ ( x − x∗ ) − ∑ λ∗j ∇h j ( x∗ )⊤ ( x − x∗ ), (4.11)
i ∈ I0 ( x∗ ) j =1

pour tout x ∈ Ω.
Le Lemme 4.1 implique que ∇h j ( x∗ )⊤ ( x − x∗ ) = 0 pour tout j = 1, . . . , m. De même,
étant donné que pour tout i ∈ I0 ( x∗ ) la contrainte gi ( x) ⩽ 0 est saturée en x∗ , on peut
appliquer le Lemme 4.2 pour affirmer que ∇ gi ( x∗ )⊤ ( x − x∗ ) ⩽ 0 pour tout i ∈ I0 ( x∗ )
et pour tout x ∈ Ω. Il en découle que la première somme dans (4.12) est inférieure ou
égale à zéro, alors que la seconde somme s’annule. Cela implique que

f ( x ) ⩾ f ( x ∗ ), ∀ x ∈ Ω. (4.12)

C’est ce qu’il fallait démontrer.

73
 Liste des questions de cours dont trois
5
figurerons dans le sujet de l’examen final

Chapitre 1
1. (2 points) Donner la démonstration de la forme suivante de la formule de Taylor :
Si Ω est un convexe ouvert de R p et f : Ω → R est continûment différentiable dans Ω,
alors pour tout x, x0 ∈ Ω,
Z 1
f ( x ) − f ( x0 ) = ∇ f ( x0 + t( x − x0 ))⊤ dt( x − x0 ). (5.1)
0

2. (2 points) Donner la démonstration de la forme suivante de la formule de Taylor :

Soit Ω un convexe ouvert de R p . Si la fonction f : Ω → R est deux fois continûment
différentiable dans Ω, alors pour tout x, x0 ∈ Ω, il existe un point z appartenant au
segment [ x0 , x], tel que
1
f ( x) = f ( x0 ) + ∇ f ( x0 )⊤ ( x − x0 ) + ( x − x0 )⊤ ∇2 f (z)( x − x0 ) .
| {z } 2| {z }
approximation affine forme quadr. de matrice ∇2 f (z)

3. (2 points) Démontrer l’assertion suivante : Si la fonction convexe f est continûment

différentiable dans un convexe Ω ⊂ R p , alors

f ( x ) ⩾ f ( x0 ) + ∇ f ( x0 ) ⊤ ( x − x0 )

pour tout x, x0 ∈ Ω.
 Liste des questions de cours

4. (2 points) Démontrer l’assertion suivante : Si la fonction f est continûment différen-

tiable dans un convexe Ω ⊂ R p et vérifie

f ( x ) ⩾ f ( x0 ) + ∇ f ( x0 ) ⊤ ( x − x0 )

pour tout x, x0 ∈ Ω, alors ∇ f est croissante, c’est-à-dire ( x − x0 )⊤ (∇ f ( x) − ∇ f ( x0 )) ⩾

0 pour tout x, x0 ∈ Ω.
5. (3 points) Démontrer l’assertion suivante : Si la fonction f est continûment différen-
tiable dans un convexe Ω ⊂ R p et vérifie ( x − x0 )⊤ (∇ f ( x) − ∇ f ( x0 )) ⩾ 0 pour tout
x, x0 ∈ Ω, alors f est convexe.
6. (3 points) Démontrer l’assertion suivante : Si la fonction f est convexe et deux fois
continûment différentiable dans Ω, alors la hessienne ∇2 f ( x) de f en tout point x est
positive, ∇2 f ( x) ≽ 0.
7. (2 points) Démontrer l’assertion suivante : [Conditions Nécessaires du Premier Ordre]
Si x∗ est un minimiseur local de f et f est continûment différentiable dans un voisinage
ouvert de x∗ , alors ∇ f ( x∗ ) = 0.
8. (3 points) Démontrer l’assertion suivante : [Conditions Nécessaires du Second Ordre]
Si x∗ est un minimiseur local de f et ∇2 f existe et est continue dans un voisinage ouvert
de x∗ , alors ∇ f ( x∗ ) = 0 et ∇2 f ( x∗ ) est positive.
9. (2 points) Démontrer l’assertion suivante : Supposons que ∇2 f est continue dans un
voisinage ouvert de x∗ et que ∇ f ( x∗ ) = 0 et ∇2 f ( x∗ ) est défini positive. Alors x∗ est un
minimum local strict de f .
10. (3 points) Démontrer l’assertion suivante : Lorsque f est convexe, tout minimiseur
local x∗ est un minimiseur global de f .
Chapitre 2
11. (2 points) Soit [ a, b] ⊂ R un intervalle fini et f : [ a, b] → R. Définir la méthode du
nombre d’or qui cherche à approximer le point de minimum de f : [ a, b] → R.
12. (3 points) Soit [ a, b] ⊂ R un intervalle fini et f : [ a, b] → R. Soit { xk : k ∈ N}
la suite obtenue par la méthode du nombre d’or et soit x ∗ un minimiseur de f .
Montrer que si f est unimodale, alors

| xn − x ∗ | ⩽ 0.5(1 − γ)n (b − a),

où γ ∈ (0, 1/2) est un paramètre de la méthode.

13. (2 points) Soit [ a, b] ⊂ R un intervalle fini et f : [ a, b] → R. Définir la méthode du
dichotomie qui cherche à approximer le point de minimum de f : [ a, b] → R.
14. (3 points) Soit { xk ; k ∈ N} la suite obtenue par la descente de grandient sur la
fonction convexe f de classe C2 . Montrer que si x ∗ est un minimiseur local de f ,
λmax (∇2 f ( x)) ⩽ M pour tout x et h ⩽ 2/M, alors ∥ xk+1 − x∗ ∥ ⩽ ∥ xk − x∗ ∥.

76
 Liste des questions de cours

15. (3 points) Soit { xk ; k ∈ N} la suite obtenue par la descente de grandient sur la

fonction convexe f de classe C2 . Montrer que si x ∗ est un minimiseur local de f ,
λmax (∇2 f ( x)) ⩽ M pour tout x et h ⩽ 2/M, alors
 M 
f ( xk+1 ) ⩽ f ( xk ) − h 1 − h ∥∇ f ( xk )∥2 .
2
16. (4 points) Démontrer l’assertion suivante : Soit { xk ; k ∈ N} la suite obtenue par la
descente de grandient sur la fonction convexe f de classe C2 dont x ∗ est un minimiseur
local. Supposons que

f ( xk+1 ) ⩽ f ( xk ) − 12 h∥∇ f ( xk )∥2 , ∀k ∈ N.

Alors,
∥ x0 − x ∗ ∥2
f ( xK ) − f ( x∗ ) ⩽ .
2hK
17. (2 points) Donner la définition d’une fonction m-fortement convexe où m > 0.
Énoncer le théorème qui décrit la convergence exponentielle de l’algorithme de
descente de gradient dans le cas où f est fortement convexe.
18. (2 points) Donner la définition d’une fonction m-fortement convexe où m > 0.
Énoncer le théorème qui décrit la convergence sur-exponentielle de l’algorithme
de Newton dans le cas où f : [ a, b] → R est fortement convexe et sa dérivée
troisième est bornée.
Chapitre 3
19. (2 points) Ecrire la forme canonique d’un problème d’optimisation sous contraintes
d’égalité. Donner la définition d’un point régulier des contraintes et d’une direc-
tion admissible.
20. (3 points) On considère le problème de minimisation de f : R p → R sous la
contrainte h( x) = 0m , où f et h sont de classe C1 . Montrer que si x∗ est un point
régulier et d est une direction admissible, alors d⊤ ∇h j ( x∗ ) = 0 pour tout j =
1, . . . , m.
21. (3 points) Montrer que si x∗ est un minimiseur local de f dans Ω = { x ∈ R p :
h( x) = 0m }, où f et h sont de classe C1 , alors pour toute direction admissible d,
on a d⊤ ∇ f ( x∗ ) ⩾ 0.
22. (2 points) Enoncer le théorème de Lagrange.
23. (4 points) Enoncer et démontrer le théorème de Lagrange. On admettra les deux
résultats suivants.
(a) Si x est régulier, une direction d est admissible en x si et seulement si d est
orthogonale à tous les vecteurs ∇h j ( x), j = 1, . . . , m.
(b) Si x∗ est un minimiseur local de f et d est une direction admissible en x∗ , alors
d⊤ ∇ f ( x∗ ) = 0.

77
 Liste des questions de cours

24. (2 points) Enoncer la condition nécessaire du second ordre et la condition suffi-

sante du secodn ordre dans le cas où on minimise la fonction f sous la contrainte
h( x) = 0m .
Chapitre 4
25. (2 points) Rappeler la définition d’une contrainte d’inégalité saturée, d’un point
régulier des contraintes et énoncer le théorème KKT.
26. (4 points) Démontrer que si x∗ est un minimiseur local de f sous les contraintes

h( x) = 0m , g ( x) ⩽ 0n ,

où f , g, h sont de classe C1 , et x∗ est un point régulier des contraintes, alors il existe

λ∗ ∈ Rm et µ∗ ∈ Rn tels que
m n
∇ f ( x∗ ) + ∑ λ∗j ∇h j ( x∗ ) + ∑ µi∗ ∇ gi ( x∗ ) = 0 p ,
j =1 i =1

et

µi∗ gi ( x∗ ) = 0, ∀i = 1, . . . , n.

27. (3 points) Montrer que si D est un ouvert et h : D → R une fonction de classe C1 ,

pour tout Ω ⊆ D convexe et inclus dans h−1 (0) on a

∇h( x)⊤ (y − x) = 0, ∀ x, y ∈ Ω.

28. (3 points) Soit D est un ouvert de R p et f : D → R, h : D → Rm des fonctions de

classe C1 . Supposons que la fonction f et l’ensemble réalisable

Ω = { x ∈ D : h ( x ) = 0}

sont convexes. Montrer que si x∗ ∈ Ω satisfait les conditions KKT, alors x∗ est un
minimiseur global de f dans Ω. (On admettra sans démonstration que ∇h j ( x∗ )⊤ ( x −
x∗ ) = 0 pour tout x ∈ Ω et pour tout j.)

78
 Liste des questions de cours

Contenu prévisionnel des séances

• Séance 1 : Parties 1.1-1.5

• Séance 2 : Partie 1.6
• Séance 3 : Partie 1.7 et Partie 1.8 jusqu’au Théorème 1.7, preuve comprise.
• Séance 4 : Parties 1.8 et 1.9
• Séance 5 : Parties 2.1 ; 2.2 ; 2.3
• Séance 6 : Partie 2.4 jusqu’à l’énoncé du Thm 2.3 compris (convergence de la des-
cente de gradient dans le cas convexe mais pas fortement convexe)
• Séance 7 : La preuve du Thm 2.3, présentations graphiques de la descente de gra-
dient, + 2 lemmes qui disent que A) si la hessienne a toutes ses valeurs propres
entre a et b, alors f ( x ) − f (y) = H ( x − y) où H est une matrice symétrique avec
des valeurs propres entre a et b, et B) si la matrice symétrique A a toutes ses valeurs
propres entre a et b, alors ∥ Ax ∥ ⩽ max(| a|, |b|)∥ x ∥.
• Séance 8 : L’énoncé et la preuve du Thm 2.4. Définition de la méthode de Newton ;
énoncé du Thm 2.5.
• Séance 9 : Preuve du Thm 2.4 (convergence de la méthode de Newton en 1D),
et Sections 3.1-3.3 avec l’énoncé du thm. de Lagrange et les remarques, ainsi que
l’exemple 3.4.
• Séance 10 (a été courte) : Directions admissibles : définition, exemples et les preuves
de deux propositions.
• Séance 11 : preuve du Théorème de Lagrange. Conditions du second ordre.
• Séance 12 : Chapitre 4 : Intro, Théorème de KKT, Preuve, exemple.
• Séance 13 : Méthodologie générale de résolution d’un problème d’optimisation
avec des contraintes d’égalité et d’inégalité. KKT dans des problèmes convexes,
extension au cas non-différentiable via la notion de sous-gradient.
• Séance 14 : Dualité.

79