Optimisation numérique

Roland Becker
14 juillet 2025

Table des matières

1 Introduction 1
1.1 Rappel : Notations . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Optimisation sans contraintes 5

2.1 Rappel : conditions d’optimalité . . . . . . . . . . . . . . . . . . 6
2.2 Rappel : conditions de Goldstein-Powell-Wolfe . . . . . . . . . . 6
2.3 Rappel : méthode du gradient . . . . . . . . . . . . . . . . . . . . 7
2.4 Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.5 Méthode d’ordre deux abstraite . . . . . . . . . . . . . . . . . . . 10
2.6 Quasi-Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.6.1 Cas d’une équation . . . . . . . . . . . . . . . . . . . . . 11
2.6.2 Cas de la minimsation . . . . . . . . . . . . . . . . . . . 13
2.7 Région de confiance . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.8 Moindres carrés . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Optimisation avec contraintes 22

3.1 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Méthodes avec projection . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Le cas sans contraintes sous forme d’inégalités . . . . . . . . . . 26
3.3.1 Lagrange-Newton . . . . . . . . . . . . . . . . . . . . . 26
3.3.2 Elimination de variables . . . . . . . . . . . . . . . . . . 28
3.4 SQP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

1 Introduction
Les problèmes d’optimisation sont souvent classé par des critères comme
— linéaire (voir programmation linéaire),
— contraintes (d’égalite, d’inégalité, entiers),
— continue - discret,
— nombre de variables.
Il existe une multitude de problèmes d’optimisation dont la résolution, ou plutôt
la recherche de solutions approchées, nécessite des algorithmes itératifs. En effet,
souvent il n’existe pas de formule pour calculer une solution ou bien son évaluation
est trop coûteuse. Un tel algorithme est appelé algorithme d’optimisation. Le but
de l’optimisation numérique est d’étudier ces algorithmes et en développer de nou-
veaux.

1
L’étude des algorithmes typiquement concerne des questions comme :
— Convergence,
— Vitesse de convergence,
— Robustesse (dépendance par rapport à certains paramètres),
— Globalisation (dépendance par rapport aux données initiales).
Dans ce cours nous développons un certains nombre d’algorithmes d’optimisation
sous/sans contraintes et nous les appliquons ensuite à des problèmes de contrôle
optimale.
On considère une quantité x ∈ Rn qui évolue dans le temps pendant un intervalle
I = [0, T ] (on ne perd pas rien en supposant que le temps initial est t = 0). On
suppose que l’on connaı̂t l’état initial et que le changement en temps est décrit par
une loi de la forme : (
ẋ(t) = f (x(t), u(t)),
(1)
x(0) = x0 .
Dans (1), la loi est décrit par une fonctions f qui dépend de paramètres supplémentaires
u ∈ Rp :
f : Rn × Rp → Rn .
(Plus généralement, on peut supposer que f n’est défini que sur un sous-ensemble.)
En supposant que f est une fonction différentiable et bornée, il existe pour u ∈
C(I, Rp ) donnée une unique solution x ∈ C 1 (I, Rn ). Le problème du contrôle
optimal consiste à trouver un contrôle u tel que l’état x ait des propriétés voulues.
Par exemple, on peut minimiser l’écart avec une valeur cible x,
Z
1
J(x) := |x(t) − x|2 dt, (2)
2 T

ou on peut chercher le temps T minimal tel que l’état atteint la cible, x(T ) = x.

1.1 Rappel : Notations

Remarque générale. Dans la permière partie du cours, x dénote la variable indépendante
et f la fonction à minimiser. Dans la seconde partie concernée par le contrôle op-
timal, on minimise une fonction J dépendant d’une variable u, en gardant x et f
pour l’équations différentielle.

Nous considérons des problème en dimension finie, cad l’espace de travail est Rn
avec des éléments x = (x1 , . . . , xn ) ∈ Rn . Le produit scalaire euclidien est noté
n √
par x · y = xT y =
P
xi yi et la norme associée par |x| = x · x, de sorte que
i=1
n
2
x2i . Un opérateur Rn → Rn est représenté par une matrice A ∈ Rn×n .
P
|x| =
i=1
On écrit Ax pour le produit scalaire et y T Ax pour le forme quadratique.
Soit S ⊂ Rn et f : S → R. On considère le problème abstrait

min f (x) (3)

x∈S

Définition 1. — x ∈ S est solution locale, s’il existe δ > 0 tel que

x ∈ S et |x − x∗ | ≤ δ =⇒ f (x∗ ) ≤ f (x).

2
 — x ∈ S est solution globale si

x ∈ S =⇒ f (x∗ ) ≤ f (x).

— x∗ ∈ S est solution globale unique si

x ∈ S et x ̸= x∗ =⇒ f (x∗ ) < f (x).

— x∗ ∈ S est solution locale unique, s’il existe δ > 0 tel que

x ∈ S et |x − x∗ | ≤ δ =⇒ f (x∗ ) ≤ f (x).

Proposition 1. Si f est convexe, toute solution locale est solution globale.

On va considérer des algorithmes de la forme

Algorithme 1 : Algorithme générique (à un pas)

(0) Choisir x0 , k = 0.
(1)
xk+1 = xk + tk pk .
Incrémenter k et retour à (1).

Définition 2. Soit x∗ une solution. On dit qu’un algorithme converge de façon

i) linéaire (géométrique) s’il existe c < 1 tel que

|xk+1 − x∗ | ≤ c |xk − x∗ |

ii) quadratique s’il existe C tel que

|xk+1 − x∗ | ≤ C |xk − x∗ |2

iii) super-linéaire s’il existe une suite ck tel que

|xk+1 − x∗ | ≤ ck |xk − x∗ |

et ck → 0 pour k → ∞.
Cela est appelé q-convergence. Pour la r-convergence voir TD.
L’algorithme générique sera parfaitement définit si on donne des règles de calcul
pour pk et tk .

pk = Φ(xk , f, ∇f, ∇2 f ), tk = Ψ(xk , pk , f, ∇f, ∇2 f ) (4)

La fonction Φ décrit le choix de la direction et la fonction Ψ la règle pour déterminer

le longueur du pas.
Définition 3. Soit y = T (x) = a+Ax une transformation affine-linéaire régulière.
Soit (xk )k la suite générée par l’algorithme générique et soit (yk )k la suite générée
avec condition initiale y0 = T (x0 ). Si l’on a yk = T (xk ) on dit que l’algorithme
est invariant par transformations affines. Si la même propriété a lieu avec des
matrices A diagonales, on dit que l’algorithme est invariant par transformations
d’échelle.

3
Définition 4. Soit S ⊂ Rn et F : S → Rm . On dit que F que F est (Fréchet)-
différentiable en x ∈ S s’il existe un opérateur linéaire A : Rn → Rm tel que
pour toute suite suite (xk )k ⊂ S vérifiant xk → x on a

∥F (xk ) − F (x) − A(xk − x)∥ = o(∥xk − x∥). (5)

Dans ce cas on note F ′ (x) = DF (x) = A. Dans le cas m = 1 on écrit aussi

∇F (x) = AT (vecteur colonnes) et dans le cas F = ∇f (donc m = n) on écrit
∇2 f = A.
Si pour tout y ∈ Rn la limite

F (x + εy) − F (x)
lim (6)
ε→0 (ε>0) ε

existe et dépend de façon linéaire de y, F est appelé Gateaux-différentaible en x.

Définition 5. La fonction g : S → Rm est lipschitzienne de rapport L si pour tout

x, y ∈ S on a
|g(x) − g(y)| ≤ L |x − y|. (7)

Soit S ⊂ Rn un ouvert convexe. Si f : S → R est deux-fois continûment

différentiable en x ∈ S, on note

∂f ∂ 2f
g = g(x) = ∇f (x) = ( )1≤i≤n , H = H(x) = ∇2 f (x) = ( )1≤i,j≤n .
∂xi ∂xi ∂xj

On rappelle le théorème fondamental de l’analyse. En posant pour x, y ∈ S ϕ(s) =

f (x + s(y − x))
Z 1 Z 1
′
f (y)−f (x) = ϕ(1)−ϕ(0) = ϕ (s) ds = ∇f (x+s(y−x))·(y−x) ds. (8)
0 0

Cette identité étant vraie dans le cas vectoriel, on obtient avec g(y) := ∇f (x +
s(y − x)) Z 1
g(y) − g(x) = s ∇2 f (x + t(y − x))(y − x) dt,
0
ce qui implique
Z 1 Z 1
f (y) − f (x) = g(x) · (y − x) + s (y − x)T ∇2 f (x + st(y − x))(y − x) dtds.
0 0

Comme ∇f 2 est supposée continue, on obtient en particulier

1
f (y) − f (x) = g · (y − x) + (y − x)T H(y − x) + o(|y − x|2 ). (9)
2
On rappelle l’écriture utilisant le symbole de Landau o(h) qui signifie que A(h) =
o(h) ssi A(h)/h → 0 si h → 0.

4
2 Optimisation sans contraintes
On considère ici le problème d’optimisation suivant. Soit S ⊂ Rn un ensemble
(souvent supposé ouvert et convexe) et f : S → R une fonction souvent supposée
C 2 . On considère le problème abstrait

min f (x) (10)

x∈S

On donne d’abord un résultat d’existence de solution abstrait basé sur la coercivité

et continuité et une condition suffisante pour l’unicité basé sur la convexité.
Pour le développement d’algorithmes, il est alors important de caractériser les so-
lutions, ce qui est fait par les conditions d’optimalité.
Définition 6. On dit que f : S → R est coercive si pour (xk )k ⊂ S et xk → ∞ on
a f (xk ) → ∞.
Définition 7. Un ensemble S ⊂ Rn est convexe si pour x, y ∈ S et 0 ≤ λ ≤ 1 on
a λx + (1 − λ)y ∈ S. Si S ⊂ Rn est convexe, on dit que f : S → R est convexe si
pour 0 ≤ λ ≤ 1 on a f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y). f est strictement
convexe si pour 0 < λ < 1 on a f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y).
Théorème 1. (Weierstrass). On suppose S fermé. On suppose que f est coercive.
De plus on suppose que f est semi-continue inférieurement. Alors il existe au moins
une solution x∗ au problème (10).
Démonstration. Visiblement on a

inf f (x) > −∞.

x∈S

Soit donc (xk )k ⊂ S une suite telle que f (xk ) → inf x∈S f (x). A cause de la
coércivité on ne peut avoir xk → ∞. D’après Heine-Borel il existe une sous-suite
(xkn )n et x∗ ∈ S, S étant fermé, tels que lim xkn = x∗ . On a alors
n→∞

f (x∗ ) ≤ lim inf f (xkn ) = inf f (x).

n→∞ x∈S

Ce qui prouve bien que x∗ est un point où f atteint son minimum.
Pour établir l’unicité, on utilise la convexité.
Théorème 2. Soit S un ensemble convexe, f une fonction strictement convexe et
x∗ une solution locale. Alors x∗ est l’unique solution globale.
Démonstration. Soit y ∗ ∈ S une autre solution locale. Supposons f (y ∗ ) < f (x∗ )
On a alors pour t ∈ [0, 1[

f (x∗ + t(y ∗ − x∗ )) < f (x∗ ).

Donc x∗ n’est pas solution locale. Donc f (y ∗ ) = f (x∗ ). La stricte convéxité donne
x∗ + y ∗ 1 1
f( ) < f (x∗ ) + f (y ∗ ) = f (y ∗ ),
2 2 2
encore une contradiction. Cela implique x∗ = y ∗ d’après la définition de la stricte
convexité.

5
2.1 Rappel : conditions d’optimalité
Le théorème de Taylor donne l’interprétation du gradient et de la Hessienne :
1
f (x + p) = f (x) + g · p + pT Hp + o(|p|2 ). (11)
2
A premier ordre (p suffisament petit), on voit que f décroit en direction de p si
g · p. On appelle alors p une direction de descente. On dit que x est un point
stationnaire si g = g(x) = 0. Dans un point stationnaire, H donne la topographie
locale : si pT Hp ≥ 0 on ne peut pas réduire f et on est donc au bas de la vallée.
De façon plus générale, on peut trouver QPorthogonale et Λ diagonale telles que
HQ = QΛ. Pn Il s’en2 suit que pour p = di qi (qi le vecteurs colonnes de Q)
T
p Hp = i=1 λi di et le signe de la valeur propre dit s’il s’agit d’une directon
ascendante ou descendante.
Théorème 3. (Equation d’Euler et condition de Legendre) On suppose S ouvert
et f différentiable. Soit x∗ une solution locale. Alors on a
g(x∗ ) = ∇f (x∗ ) = 0. (12)
Si f est C 2 , on a de plus
H(x∗ ) = ∇2 f (x∗ ) ≥ 0. (13)
Inversement, si x∗ ∈ S est un point tel que g(x∗ ) = 0 et H(x∗ ) > 0, alors x∗ est
une solution locale unique.

2.2 Rappel : conditions de Goldstein-Powell-Wolfe

On peut donner des conditions abstraites pour la convergence de l’algorithme générique.
Lemme 1. Soit f coercive et différentiable et gk = ∇f (xk ). Soient 0 < ρ < 1 et
σ ∈]ρ, 1[ donnés. Sous la condition
pk · gk < 0 (14)
on peut trouver tk > 0 tel que avec xk+1 = xk + tk pk les conditions de Wolfe
f (xk+1 ) ≤ f (xk ) + ρ tk gk · pk
(15)
gk+1 · pk ≥ σgk · pk
soient satisfaites.
Démonstration. Soit ϕ(t) := f (xk + tpk ). Les conditions (15) deviennent alors
ϕ(t) ≤ ϕ(0) + ρ tϕ′ (0)
(16)
ϕ′ (t) ≥ σϕ′ (0).
D’après l’hypothèse ϕ′ (0) = gk · pk < 0. . . . . . . . . . . . . . . . .
Théorème 4. Soit f coercive et différentiable avec dérivée lipschitzienne. On sup-
pose que |pk | > 0 et que |gk | > 0.
gk · pk
− ≥ µ > 0. (17)
|gk | |pk |
Si les pas tk sont choisis de façon que les conditons (15) sont satisfaits, on a
gk → 0. (18)

6
Démonstration. On a d’abord que f (xk ) − f (k+1 ) ≥ 0 et
m
X
f (xk ) − f (k+1 ) = f (x0 ) − f (xm+1 ) < +∞ (19)
k=0

à cause de la coercivité. D’après l’hypothèse on a

|gk | |xk+1 − xk | = tk |gk | |pk | ≤ −µ−1 tk gk · pk (20)

D’après la deuxième condition de Wolfe on a

(σ − 1)gk · pk ≤ (gk+1 − gk ) · pk
≤ L |xk+1 − xk | |pk |

D’après le première condition de Wolfe on a alors

σ − 1 gk · pk
|gk |2 ≤ |xk+1 − xk | |gk | ≤ −µ−1 tk gk · pk
L |gk| |pk |
≤ ≤ µ−1 (f (xk ) − f (xk+1 )) .

Cela implique la condition de Zoutendijk

∞  2
X
2 −gk · pk
|gk | < +∞. (21)
k=0
|gk | |pk |
 2
Cela donne |gk |2 |g−gk |k|p·pkk| . Comme l’angle ne peut pas tendre vers zéro d’après
l’hypothèse, on obtient le résultat.

Remarque 1. Rien n’est dit sur la condition d’ordre deux. Rien n’est dit sur la
vitesse de convergence. La monotonie est imposé, ce qui peut être trop fort. Il existe
des algorithmes qui réalise (15).

2.3 Rappel : méthode du gradient

Le choix le plus simple pour satisfaire (17) du théorème est de prendre

pk = −gk . (22)

Cela s’appelle la méthode du gradient (’steepest descent’).

Algorithme 2 : Méthode du gradient

1. (Initialisaton) t0 > 0 et x0 . k = 0
2. (Recherche du pas) déterminer tk
3. (Itération) xk+1 = xk − tk gk
4. (Critère d’arrêt) Si |xk+1 − xk | ≤ ε stop. Sinon incrémente k.

Cet algorithme est déconseillé, mais nous donnons un résultat de convergence, car
sa démonstration est instructive.

7
Théorème 5. Soit f ∈ C 1 (Rn ), coercive et strictement convexe. De plus on sup-
pose que ∇f est lipschitzien avec rapport L. Si les pas vérifie

t ≤ tk ≤ t, 0 < t < t < 2/L, (23)

la méthode du gradient converge vers le minimum de f .

Démonstration. On a existence d’un minumum unique x∗ tel que ∇f (x∗ ) = 0.

Alors on a

f (xk+1 ) − f (xk ) = ∇f (xk ) · (xk+1 − xk )

Z 1 
+ (∇f (xk + t(xk+1 − xk )) − ∇f (xk ) dt · (xk+1 − xk )
0
1 L
≤ − |xk+1 − xk |2 + |xk+1 − xk |2 .
tk 2
On a donc  
L 1
f (xk+1 ) − f (xk ) ≤ − |xk+1 − xk |2 .
2 t
La suite (f (xk )) et donc strictement décroissante et donc convergente (elle est
minorée). Cela implique que f (xk+1 ) − f (xk ) tend vers 0 et que (xk ) est bornée
par coercivité. De plus on a
 −1
2 1 L
|xk+1 − xk | ≤ − (f (xk+1 ) − f (xk )) → 0.
t 2

Il s’en suit que ∇f (xk ) = xk+1tk−xk tend vers 0. Soit x̄ un point d’adhérence de (xk ).
On a donc ∇f (x̄) = 0 et par conséquent x̄ = x∗ . Donc toute la suite converge vers
x∗ .

Remarque 2. Pour se rendre compte à quel point la méthode du gradient peut être
mauvaise pour des problèmes mal conditionnés, on considère l’exemple f (x) =
xT Ax − bT x avec pas fixe. La méthode devient la méthode de Richardson avec
facteur de relaxation tk = t :

xk+1 = xk + t (b − Axk ) . (24)

Cette méthode est moins bonne que Jacobi.

2.4 Newton
Algorithme 3 : Méthode de Newton
1. (Initialisaton) t0 > 0 et x0 . k = 0
2. (Résolution) Hk pk = −gk
3. (Recherche du pas) déterminer tk
4. (Mise à jour) xk+1 = xk + tk pk
5. (Critère d’arrêt) Si |xk+1 − xk | ≤ ε stop. Sinon incrémente k.

8
Remarque 3. Quand est-ce que les tk vérifie les conditions de Wolfe. D’abord on
a
−pk · gk = gkT Hk−1 gk ≥ c |gK | |pk |
si et seulement si Hk > 0 et λmax (Hk ) ≤ C.
Supposons que pk → 0. On a donc
1
f (xk+1 ) − f (xk ) = gk · pk + pTk Hk pk + o(p2k )
2
1
= gk · pk + o(p2k )
2
Par conséquent pour k suffisamment la règle d’Armijo est satisfaite. De la même
manière on vérifie la condition de Wolfe. Tout cela pour tk = 1.
On verra plus loin une autre méthode pour rendre la méthode plus robuste (“région
de confiance”).
La méthode de Newton dans l’optimisation peut être vue de deux facon différente :
1. On se sert de la condition d’ordre un et on applique Newton à la résolution
de ∇f (x) = 0. La condition d’ordre deux suffisante pour garantir l’exis-
tence des itérés, si on commence suffisamment près ( ?).
2. A chaque itération, on quadratise la fonctionnelle à minimiser : soit xk
donné, on a alors avec gk = ∇f (xk et Hk = ∇f 2 (xk )
1
f (xk + p) = f (xk ) + f˜(p) + o(|p|2 ), f˜(p) = gk · p + pT Hk p. (25)
2
L’idée est alors de trouver pk comme solution de infn f˜(p). Cela est pos-
p∈R
sible dans le cas régulier Hk > 0.
Cette équivalence (dans le cas strictement convexe) illustre les faiblesses de l’al-
gorithme de Newton :
1. Que faire dans le cas Hk ̸> 0 ?
2. Si le pas est ’grand’, le développement de Taylor qui justifie l’approche de-
vient critique : le comportement de f peut fortement dévier d’une fonction
quadratique. Que faire ?
Théorème 6. Soit f ∈ C 2 (Rn ) et x∗ solution de ∇f (x) = 0. On suppose que
1. ∇2 f (x∗ ) est inversible,
2. |∇2 f (x) − ∇f (y)| ≤ L |x − y|.
Si lim inf k tk = t > 0 |x0 − x∗ | ≤ η, η = min L∥Hk−1 ∥/2, t, l’algorithme de
Newton converge vers x∗ . De plus, si tk → 1 suffisamment rapide
|x∗ − xk+1 | ≤ C |x∗ − xk |2 (26)
Démonstration. Soit ek := x∗ − xk . D’après la définition de la méthode et la
stationnarité de x∗
∇2 f (xk )(xk+1 − xk ) = tk (∇f (x∗ ) − ∇f (xk )) = . (27)
Cela donne
Z 1
2 2
∇2 f (xk ) − ∇2 f (xk + sek )(ek ) ds

∇ f (xk )(ek+1 ) = (1−tk )∇ f (xk )(ek )+tk
0

9
Ceci implique
L
|ek+1 | ≤ (1 − tk )|ek | + tk ∥Hk−1 ∥ |ek |2 .
2
Ceci permet de montrer par récurrence que xk ∈ Bη (x∗ ), si η ≤ 1.
Le théorème montre bien qu’on peut converger vers un point stationnaire qui n’est
pas un minimum, et cela se produit facilement dans la pratique. (Dans d’autres
contexte que l’optimisation, cela peut être un avantage.)

2.5 Méthode d’ordre deux abstraite

On considère une fonction lisse f et on considère l’algorithme avec des matrices
symétriques inversibles Bk On a donc l’algorithme générique avec

Algorithme 4 : Algorithme d’ordre deux abstrait

1. (Initialisaton) t0 > 0 et x0 . k = 0
2. (Mise à jour) xk+1 = xk − tk Bk−1 gk

pk = −Bk−1 gk .

On voit que sous la condition Bk ≥ 0 la direction pk est choisi comme solution du

problème de minimisation quadratique
1
infn f˜k (p), f˜k (p) := f (xk ) + gk · p + pT Bk p. (28)
p∈R 2

Le théorème de Wolfe demande que λmin (Bk−1 ) ≥ c > 0. Les tk peuvent alors être
choisir pour garantir la convergence vers un point stationnaire.
On se demande maintenant sous quelles conditions l’algorithme converge de façon
superlinéaire.
Théorème 7. (Dennis-Moré) Soit f ∈ C 2 (Rn ) avec ∇2 f Lipschitz. On suppose
qu’il existe une solution x∗ avec ∇2 f (x∗ ) régulier.
On considère la suite (xk ) généré par l’algorithme 4 avec tk = 1. On suppose que
xk → x∗ , xk ̸= x∗ et gk ̸= 0.
Alors sont équivalents avec ek := x∗ −xk , sk = xk+1 −xk (= pk ) et yk := gk+1 −gk :

|ek+1 |
lim = 0, (29)
k→∞ |ek |
|Bk sk − yk |
lim = 0. (30)
k→∞ |pk |
Démonstration. La définition de méthode donne

Bk sk − yk = −gk − (gk+1 − gk ) = −gk+1

= ∇f (x∗ ) − ∇f (xk+1 ) = H k ek+1

avec Z 1
H = k
∇2 f (x∗ − tek+1 ) dt. (31)
0

10
Donc
|Bk sk − yk | |Bk sk − yk | |ek | |ek+1 | |ek |
= ≤ ∥H k ∥
|sk | |ek | |sk | |ek | |sk |
Il reste à estimer

|sk | = |ek+1 − ek | ≥ ||ek | − |ek+1 || ≥ c |ek |.

pour k grand. Dans l’autre sens on a

|ek+1 |
−1 |Bk sk − yk | |sk |

≤ ∥ Hk ∥
|ek | |sk | |ek |

Comme
ek+1 = Bk−1 Bk − H k ek ,


(32)
on a
|sk | = |ek+1 − ek | = |Bk−1 H k ek | ≤ C |ek |.

Remarque 4. Comme yk ≈ ∇2 f (xk )sk , on voit que dans la direction sk , la matrice

Bk doit se comporter comme la héssienne : Bk sk ≈ Hk sk .
Il exitse des méthodes superlinéaire avec Bk ̸→ ∇2 f (x∗ ).

2.6 Quasi-Newton
2.6.1 Cas d’une équation
On cherche une méthode sans l’information complète de la héssienne, mais avec
vitesse de convergence super-linéaire. Cela nécessite d’après le théorème 7 (qui
s’applique aussi au cas de la résolution d’une équation non-linéaire)

|Bk sk − yk |
lim = 0, (33)
k→∞ |sk |

où sk = xk+1 − xk = tk pk . Cette condition ne pouvant être imposée, on impose

l’équation de la secante
Bk+1 sk = yk . (34)
L’idée générale est de vérifier cette équation de façon itérative. On cherche donc
Bk+1 de la forme
Bk+1 = Bk + δBk (35)
Etant donné (34) on a

|Bk sk − yk | |(Bk − Bk+1 )sk |

= ≤ ∥Bk − Bk+1 ∥ = ∥δBk ∥.
|sk | |sk |

Il paraı̂t raisonnable de s’intéresser à des matrices δB simple avec ∥δBk ∥ petit. Si

on cherche δB sous forme très simple d’une matrice de rang un, δB = abT , on voit
tout de suite que (34) implique

r k bT
δB = , rk := yk − Bk sk .
b · sk

11
Le choix le plus simple (de toute façon il faut garantir b · sk = 0) est b = sk et on
obtient la méthode de Broyden-Rang1 :

rk sTk
δB = . (36)
|sk |2

Avant d’analyser cette méthode, on rappelle quelque propriétés de la norme matri-

cielle de Frobenius n
X
∥A∥F := A2ij .
i,j=1

Lemme 2.

∥A∥2F = tr(AT A), ∥A∥2F = ⟨A, A⟩F , ⟨A, B⟩F := tr(AT B) (37)
∥AB∥F ≤ ∥A∥F ∥B∥F , ∥ppT ∥2F = ∥p∥2 (38)

Théorème 8. Soit
A := δ ∈ Rn×n :

δ sk = rk . (39)
La formule de Broyden (36) définit δB comme la solution unique du problème de
minimisation :
inf ∥δ∥F (40)
δ∈A

Démonstration. On a pour δ ∈ A :

rk sTk δsk sTk

δB = = .
|sk |2 |sk |2

Remarquant que
!2
X X
∥ppT ∥2F = p2i p2j = p2i = |p|2
ij i

on trouve (on utilise que ∥ · ∥F est une norme matricielle)

∥δ∥F ∥sk sTk ∥F

∥δB∥F ≤ ≤ ∥δ∥F .
|sk |2

On remarque que A est un espace affine et ∥ · ∥F une fonctionnelle strictement

convexe ce qui donne l’existence et l’unicité.
Un autre choix qui donne une matrice symétrique est (abT est symétrique si a = b) :

rk rkT
δB = , rk := yk − Bk sk . (41)
rk · sk
Si la condition initiale est suffisamment proche d’une solution x∗ et la condition
de la héssienne suffisamment proche de la héssienne dans la solution, on peut
démontrer la convergence super-linéaire. Ce résultat n’implique pas la convergence
Bk → ∇f 2 (x∗ ).

12
 Algorithme 5 : Update sur la héssienne
1. (Initialisaton) t0 > 0, B0 = I et x0 . k = 0
2. (Direction) Bk pk = −gk
3. (Pas) xk+1 = xk + tk pk
4. (Update) Bk+1 = Bk + δk

Algorithme 6 : Update sur l’inverse de la héssienne

1. (Initialisaton) t0 > 0, C0 = I et x0 . k = 0
2. (Direction) pk = −Ck gk
3. (Pas) xk+1 = xk + tk pk
4. (Update) Ck+1 = Ck + εk

2.6.2 Cas de la minimsation

Un algorithme utilisant une mise à jour de la héssienne à la forme suivante.
On peut également procéder de la façon suivante. Au lieu d’améliorer la héssienne
elle-même, on approche directement son inverse. Cela a d’abord l’avantage d’éviter
la résolution du système linéaire à chaque pas. Dans le cas d’un mauvais condion-
nement, on peut avoir un algorithme mieux conditionné, selon la formule de mise
à jour.
On remarque la condition pour la convergence superlinéaire est maintenant :

|sk − Hk yk |
lim = 0. (42)
k→∞ |sk |2

L’équation de la sécante est alors

Hk+1 yk = sk , yk = gk+1 − gk . (43)

Dans le cas de la minimisation, les méthodes de rang 1 ne sont guère utilisées : on

ne peut pas garantir la symétrie et la positivité en même temps. On sera naturelle-
ment amené à considérer donc des méthodes de mise à jour avec des incréments de
rang 2.
Nous allons déduire différentes formules classiques d’une approche générale. Pour
cela nous avons besoin du résultat classique pour la minimisation sous contraintes
d’égalité.

Lemme 3. Soit f : Rn → R différentiable et A ∈ Rn×m (m ≤ n) de rang maximal.

Si x∗ est un extremum local, il existe z ∗ ∈ Rm (multiplicateur de Lagrange) tel
que
∇f (x∗ ) − AT z ∗ = 0. (44)
Le multiplicateur z ∗ est unique.

Démonstration. Soit W = ker(A). On sait d’après le théorème ?? que

⟨∇f (x∗ ), w⟩ = 0 ∀w ∈ W,

13
c’est-à-dire que ∇f (x∗ ) ∈ W ⊥ . On rappelle le résultat de l’algèbre linéaire :
Rn = ker(A) ⊕ im(AT ),
que l’on applique à ∇f (x∗ ). L’unicité est évidente.
Remarque 5. Dans le cas m = n x∗ = 0 est le seul point admissible et donc
solution du problème de minimisation. On a z = A−T ∇f (0). Si z = 0, x∗ =
0 serait une solution du problème sans contraintes. Si on considère le problème
perturbé
infn f (x) sous contrainte Ax = e, (45)
x∈R

avec e ∈ Rn , et on introduit la fonction v(e) = f (x∗ (e)) = f (A−1 )e, on a

∇v(0) = A−T ∇f (0) = z ∗ .
On obtient donc l’interprétation du multiplicateur de Lagrange.
Remarque 6. On voit que (44) exprime la stationnarité par rapport à x de la
fonction lagrangienne
L(x, z) := f (x) − ⟨Ax, z⟩. (46)
On remarque la contrainte est équivalente à L′z (x∗ , z ∗ ) = 0. Le théorème dit alors
qu’un extremum sous contrainte rend la lagrangienne stationnaire :
L′ (x∗ , z ∗ ) = 0.
Nous avons besoin d’une généralisation de la norme de Frobenius. Soit M ∈ Rn×n
une matrice symétrique positive. Il existe donc la racine carré M 1/2 . On définit une
norme matricielle
p
∥A∥M := ⟨A, A⟩M , ⟨A, B⟩M := ⟨M 1/2 A, M 1/2 B⟩F = tr(M AT M B). (47)
Théorème 9. Soit M ∈ Rn×n une matrice symétrique positive, p, r ∈ Rn , p =
̸ 0.
Soit
A := δ ∈ Rn×n : δ T = δ et δ p = r .

(48)
La solution unique du problème de minimisation
inf ∥δ∥2M (49)
δ∈A

est donnée par

rcT + crT r·p T
δ∗ = − cc , c = M −1 p. (50)
c·p (c · p)2
Démonstration. Nous appliquons les multiplicateurs de Lagrange. Pour cela, on
définit L(δ, z, Z) : Rn×n × Rn × Rn×n → R
1
L(δ, z, Z) := ∥δ∥2M − ⟨δp − r, z⟩ − (δ − δ T )Z, (51)
4
qui tient compte des deux contraintes linéaires définissant A. Un calcul directe
donne la condition nécessaire : pour tout ε ∈ Rn×n
1
0 = L′δ (δ, z, Z)(ε) = ⟨δ, ε⟩M − ⟨εp, z⟩ − (ε − εT )Z. (52)
2
14
On utilise (52) avec ε = ei eTj + ej eTi :

M δM = pz T + zpT . (53)

Pour éliminer z, on multiplie (53) avec

c = M −1 p,

ce qui donne
M r = M δc = p(z · c) + z(p · c). (54)
En multipliant (54) par c on a

M r · c = 2(z · c)(p · c),

ce qui donne avec (54)

Mr Mr · c
z= − p.
p · c 2(p · c)2
Avec (53) on arrive à

p(M r)T + (M r)pT Mr · c T

M δM = − pp . (55)
p·c (p · c)2

Finalement, on utilise A(abT ) = (Aa)bT pour obtenir en multilpiant (55) des deux
côtés par M −1
crT + rcT Mr · c T
δ= − cc
p·c (p · c)2

Corollaire 1. La formule PSB (Powell symétrique Broyden),

(yk − Bk sk )sTk + sk (yk − Bk sk )T (yk − Bk sk ) · sk T

δk = 2
− pp (56)
|sk | |sk |4
minimes Bk+1 − Bk dans l’ensemble des matrice symétrique vérifiant l’équation
de la sécante au sens de la norme de Frobenius.
Démonstration. On utilise le théorème 9 avec M = I.
Corollaire 2. La formule SR1 (Powell symétrique Broyden),

(yk − Bk sk )(yk − Bk sk )T
δk = (57)
sk · (yk − Bk sk )
minimes Bk+1 − Bk dans l’ensemble des matrice symétrique vérifiant l’équation
de la sécante au sens de la norme de Frobenius pondérée ∥ · ∥M pour toute matrice
M vérifiant M (yk − Bk sk ) = sk .
Démonstration. On utilise le théorème théorème 9 avec M vérifiant M rk = sk .
D’après le lemme suivant cela nécessite sk ·rk > 0, ce qui revient à sk ·(gk+1 −gk ) >
sTk Bk sk .
Lemme 4. Soient a, b ∈ Rn , b ̸= 0. Il existe une matrice symétrique positive
N ∈ Rn×n telle que N a = b si et seulement si a · b > 0.

15
Démonstration. Pour la nécessité, on multiplie N a = b par a.
Pour la suffisance, on cherche N de la forme N = I + λaaT + µbbT . La condition
N a = b implique λ = −1/|a|2 et µ = 1/(a · b) > 0. Il reste a démontrer la
positivité de N . Soit x ∈ Rn .
(a · x)2 (b · x)2
2xT N x = |x|2 − +
|a|2 ·b}
| a{z
| {z }
=I +II
D’après Cauchy-Schwarz, I ≥ 0 et I = 0 si et seulement x = λa et dans ce cas on
a II > 0.
Théorème 10. Soit N ∈ Rn×n une matrice symétrique positive, C̃ ∈ Rn×n une
matrice symétrique et p, y ∈ Rn , y ̸= 0. Soit
A := C ∈ Rn×n : C T = C et C y = p .

(58)
La solution unique du problème de minimisation
inf ∥C − C̃∥2N (59)
C∈A

est donnée par

sdT + dsT s·y
C∗ = C + − ddT , d = N −1 y, s = p − C̃y. (60)
d·y (d · y)2
Démonstration. On cherche C ∗ sous la forme C ∗ = C̃ + ε. D’après les hypothèses
C ∗ est symétrique si et seulement si ε est symétrique. De plus, la contrainte Cy = p
devient εy = s. Le problème de minimisation est alors équivalent à
inf ∥ε∥2N , B := εT = ε et εy = s .

(61)
ε∈B

Le théorème 9 donne la solution de ce problème :

sdT + dsT s·y
ε∗ = − 2
ddT ,
d·y (d · y)
ce qui donne (60).
La formule de loin la plus utilisée est donnée par le prochain corollaire.
Corollaire 3. La formule BFGS (Broyden, Fletcher, Goldfarb, Shanno),
(sk − Ck yk )ykT + yk (sk − Ck yk )T (sk − Ck yk ) · yk T
εk = − pp (62)
sk · y k (sk · yk )2
minimes Ck+1 − Ck dans l’ensemble des matrices symétriques vérifiant l’équation
de la sécante au sens de la norme de Frobenius ∥·∥N pout route matrice N vérifiant
N sk = yk . Une telle matrice N existe, si les conditions de Wolfe sont satisfaites.
Démonstration. On utilise le théorème 9 avec une matrice N vérifiant N sk = yk ,
donc d = sk . Finalement, on remarke que si les conditions de Wolfe sont satisfaite
il existe 0 < σ < 1 tel que
sk · yk = tk pk · yk = tk pk · gk+1 − tk pk · gk ≥ tk (σ − 1)pk · gk > 0,
car pk est une direction de descente.

16
Corollaire 4. La formule de BFGS est aussi donné par

sk ykT yk sTk sk sTk

   
Ck+1 = I − Ck I − + . (63)
sk · y k sk · yk sk · yk

Cela montre la positivité des Ck . La suite des inverse Bk est donné par

yk ykT Bk sk sT B
Bk+1 = Bk + − T k . (64)
sk · y k sk Bk sk

Théorème 11. Pour une fonctionnelle f quadratique, BFGS partant de H0 = I

avec recherche de pas optimale produit les mêmes itérés que le gradient conjugué.

2.7 Région de confiance

Pour pallier aux inconvénients de l’algorithme de Newton (et de ses voisins), on
propose à chaque itération de restreindre la validité du développement de Taylor.
Dans la cas générique on cherche à résoudre le problème :
1
inf f˜k (p), f˜k (p) := f (xk ) + gk · p + pT Bk p. (65)
p∈Br 2
où la valeur du rayon r de la boule Br exprime la confiance que l’on accorde au
modèle approché f˜.
On remarque que (65) apport une solution au problème de la courbure négative. Il
est donc tout à fait possible de considérer le cas Bk ̸≥ 0, par exemple Newton.

Théorème 12. Un vecteur p∗ est solution du problème

1
inf ϕ(p), ϕ(p) = g · p + pT Bp (66)
p∈Br 2

avec B = B T si et seulement s’il existe µ ≥ 0 tel que

(B + µI)p∗ = −g, (67)

µ(|p| − r) = 0, (68)
B + µI ≥ 0. (69)

Remarque 7. Si g ̸= 0 la matrice B + µI est régulière. Cela se vérifie facilement

dans le cas n = 1 et se généralise par diagonalisation au cas général.

Démonstration. =⇒
Soit p∗ solution du problème. La condition d’ordre un est

∇ϕ(p∗ ) · (q − p∗ ) ≥ 0 |q| ≤ r. (70)

Si |p∗ | < r on peut prendre dans (70) q = p + td avec |d| = 1 et t petit. Cela
donne ∇ϕ(p∗ ) = 0, ce qui est (67) avec µ = 0. La condition nécessaire d’ordre
deux donne ∇2 ϕ(p∗ ) ≥ 0, ce qui donne (69).
Si maintenant |p∗ | = r, on ∇ϕ(p∗ ) ⊥ Tp∗ (B) = (p∗ )⊥ . Il existe donc µ ∈ R
tel que ∇ϕ(p∗ ) = −µp∗ . La condition (70) implique avec q = tp∗ (t < 1) que
∇ϕ(p∗ ) · p∗ ≤ 0, cela implique µ ≥ 0.

17
Avant de démontrer (69), on constate d’abord que si p∗ vérifie (67), on a
1
ϕ(p) − ϕ(p∗ ) = ∇ϕ(p∗ ) · (p − p∗ ) + (p − p∗ )T B(p − p∗ )
2
1 µ
= −µp∗ · (p − p∗ ) + (p − p∗ )T (B + µ)(p − p∗ ) − |p − p∗ |2
2 2
1 µ
= (p − p∗ )T (B + µ)(p − p∗ ) + |p∗ |2 − |p|2 .


2 2
(71)

Si l’on fait parcourir p la sphère (p = p∗ + td, |p| = r), on trouve

1
t2 dT (B + µ)d = ϕ(p) − ϕ(p∗ ) ≥ 0
2
comme l’expression quadratique ne dépend pas du signe et par continuité on trouve
(69).

⇐=
Inversement, on suppose que |p∗ | vérifie (67-69). On utilise (71). Dans le cas µ = 0
on a immédiatement ϕ(p) − ϕ(p∗ ) ≥ 0. Dans le cas µ > 0 on a avec la condition de
complémentarité |p∗ | = r et avec |p| ≤ r, (71) implique également ϕ(p) − ϕ(p∗ ) ≥
0.
On remarque que (71) donne avec p = 0
1 µ
ϕ(p∗ ) = − p∗ T (B + µ)p∗ − |p∗ |2 (72)
2 2
L’idée est maintenant d’adapter le rayon de confiance par rapport au succès de
l’itération précédente. Ayant résolu (65) le changement réel de la fonction est

redr := f (x) − f (x + p∗ ),

tandis que la réduction prévisionnelle est

redp := f (x) − f˜(p∗ ) = −ϕ(p∗ ).

Pour cela on suppose que ϕ(p∗ ) (ce qui revient à g ̸= 0 et B ̸= 0) et on définit la

fiabilité du modèle quadratique par
redr
ρk := . (73)
redp

Théorème 13. (Schulz, Schnabel, Byrd) On suppose que {xk } ⊂ B avec B ⊂

Rn borné, sup ∥∇2 f (x)∥ ≤ M , Bk = ∇2 f (xk ) et f coercive. Alors tout point
x∈B
d’accumulation x∗ de la suite (xk ) vérifie

∇f (x∗ ) = 0, ∇2 f (x∗ ) ≥ 0.

De plus, si ∇2 f (x∗ ) > 0, toute la suite (xk ) converge, rk → 1 et la convergence

est quadratique.

18
 Algorithme 7 : Region de Confiance
1. (Initialisaton) Choisir c0 > 0. r0 > 0 et x0 . k = 0
2. (Résoudre) Trouver pk comme solution de
1
inf gk · p + pT Bk p (74)
p∈Brk 2

3. (Mise à jour) Calculer

reda f (xk ) − f (xk + pk )

ρk := = .
redp −ϕ(pk )

Si ρk ≥ c0
xk+1 = xk + pk ,
sinon xk+1 = xk . (
1
r
2 k
si ρk ≤ 14 ,
rk+1 := (75)
2rk sinon.

Démonstration. On distingue deux cas. Soit d’abord inf rk = 0. Dans ce cas, il

k
existe une sous-suite k ′ telle que ρk′ ≤ 0.25, c’est-à-dire
1 1
f (xk′ ) − f (xk′ + pk′ ) = redak′ ≤ redpk′ = − ϕ(pk′ ).
4 4
Le développement de Taylor montre que

f (xk′ ) − f (xk′ + pk′ ) = −ϕ(pk′ ) + o(|p′k |2 ).

Donc
1
−ϕ(pk′ ) = f (xk′ ) − f (xk′ + pk′ ) + o(|pk′ |2 ) ≤ − ϕ(pk′ ) + o(|pk′ |2 ),
4
ce qui implique que
ϕ(pk′ ) = o(|pk′ |2 ).
Soit v un vecteur arbitraire avec |v| = 1. On pose εk′ := |pk′ | > 0 (si pk les
conditions d’ordre un et deux sont satisfaites et il n’y a rien à démintrer), donc εk′ v
est admissible et lim
′
εk′ = 0. L’optimalité de pk′ montre que
k

ε2k′ T
ϕ(pk′ ) ≤ ϕ(εk′ v) = εk′ gk′ · v + v Hk′ v + o(ε2k′ )
2
On divise par εk′ et fait tendre k ′ → ∞ pour obtenir 0 ≤ ∇f (x∗ ) · v et donc
0 = ∇f (x∗ ) · v pour tout v.
Ensuite on observe qu’on peut extraire une sous-suite k ′′ telle que

gk′′ · v = 0 ou sign(gk′′ · v) = σ ∈ {±1}

est constant. On obtient donc

ε2k′ T
ϕ(pk′ ) ≤ ϕ(εk′ σv) ≤ v Hk′ v + o(ε2k′ ).
2
19
On divise par ε2k′ et fait tendre k ′ → ∞ pour obtenir 0 ≤ 12 v T ∇f 2 (x∗ )v.

Si maintenant inf rk = r̄ > 0. Il existe donc une sous-suite k ′ telle que −ϕk′ (pk′ ) ≤
k
C(f (xk′ ) − f (xk′ )). Cela implique, comme
X X
f (x1 ) − f (x∗ ) ≥ f (xk′ ) − f (xk′ ) ≥ C −ϕk′ (pk′ )
k′ k′

que ϕk′ (pk′ ) → 0. Soit ϕ∗ (p) := g ∗ · p + 21 pT H ∗ p et p∗ une solution du problème

inf ϕ∗ (p).
|p|≤r̄/2

On va démontrer que 0 est également une solution, ce qui implique que g ∗ = 0 et

H ∗ ≥ 0 d’après le Théoreme 8. Pour k suffisamment grand on a

|x∗ − xk′ + p∗ | ≤ |x∗ − xk | + r̄/2 ≤ rk′ .

Le sous-problème donne alors

x ∗ − xk ′
ϕk′ (pk′ ) ≤ ϕk′ (x∗ − xk′ + p∗ ) = ϕk′ (p∗ ) + ∇ϕk′ ( + p∗ ) · (x∗ − xk′ ).
2
En passant à la limite on a donc

ϕ∗ (0) = 0 ≤ ϕ∗ (p∗ ).

Donc p = 0 est aussi solution du problème limite.

Supposons ∇2 f (x∗ ) > 0. Donc Hk > 0 pour k assez grand.

Example 1. Si f (x) = x3 et x0 = 0 on voit que p0 = 0 est une solution de

(76) et on aura xk = 0 pour tout k. Toutefois on constate que le problème (76)
n’a pas de solution unique. Qu’est-ce qu’il se passe si on prend une solution de
norme maximale ? Il est aussi intéressant de considérer f (x) = x4 dans les mêmes
circonstances.

L’inconvéniant de l’algorithme présenté de la région de confiance est la solution du

sous-problème. Cela dépend bien sûr du problème donné. Une façon de simplifier
l’algorithme est de remplacer la gestion du rayon rk par la gestion du multiplicateur
µk . Cela donne lieu à l’algorithme suivant.

2.8 Moindres carrés

Une classe de problème très importante est définie par des fonctionnelle ayant la
form
1
f (x) := |F (x)|2 , F : Rn → Rm , (78)
2
avec F ∈ C 2 (Rn , Rm ). Il faut distinguer plusieurs cas :
— Cas de solution d’une équation F (x) = 0, n = m. On distingue le cas
DF (x) régulier pour x dans l’ensemble des itérés du cas singulier.
— Cas des moindres carrés n < m. DF (x) n’est pas régulière et on a en
général F (x∗ ) ̸= 0. Si F (x∗ ) = 0 on parle d’un problème à résidu nulle.

20
 Algorithme 8 : Region de Confiance - Levenberg-Marquardt
1. (Initialisaton) Choisir c0 > 0. µ0 > 0 et x0 . k = 0
2. (Résoudre)
(Bk + µk I)pk = −gk . (76)
3. (Mise à jour) Calculer

reda f (xk ) − f (xk + pk )

ρk := = T .
redp gk pk + pTk (µk + Bk )pk

Si ρk ≥ c0
xk+1 = xk + pk ,
sinon xk+1 = xk . (
2µk si ρk ≤ 41 ,
µk+1 := 1 (77)
µ
2 k
sinon.

On calcul immédiatement que

1 1
f (x + p) = ⟨F (x + p), F (x + p)⟩ = ⟨F (x) + F ′ (x)p, F (x) + F ′ (x)p⟩ + o(p)
2 2
1 1
= f (x) + ⟨F (x), F ′ (x)p⟩ + ⟨F ′ (x)p, F (x)⟩ + o(p),
2 2
ce qui implique

g(x) = ∇f (x) = F ′ (x)T F (x),

m
′ ′
X (79)
2 T
H(x) = ∇ f (x) = F (x) F (x) + S(x), S(x) := Fi (x)Fi′′ (x).
i=1

On considère encore l’algorithme abstrait

Bk pk = −gk , xk+1 = xk + tk pk . (80)

La question essentielle est la choix de Bk . Le calcul des héssiennes Fi′′ peut être
très coûteux. On est donc particulièrement intéressé par des méthodes qui évite le
calcul explicite. Il y a plusieurs possibilités :
— Quasi-Newton : mise à jour sur la héssienne ou son inverse. On peut choisir
B0 = F ′ (x0 )T F ′ (x0 ),
— Gauß-Newton : Bk = F ′ (xk )T F ′ (xk ),
— Levenberg-Marquardt : Bk = µk + F ′ (xk )T F ′ (xk ),
— Gauß-Newton amélioré : Bk = F ′ (xk )T F ′ (xk ) + Sk avec une approxima-
tion Sk de type mise à jour,
— Newton : Bk = H(xk ).
L’algorithme de Levenberg-Marquardt est proche de l’algorithme de méthode des
régions de confiance. Le rajout de µk I pour convexifier la fonctionnelle peut se
faire pour les autres algorithmes également. Généralement, on espère d’éviter la
gestion des pas tk par l’introduction de µk (et on espère une meilleure conver-
gence).

21
Il existe de nombreuses variantes de ces algorithmes, ainsi que des résultats théoriques.
On mentionne ici simplement que pour un problème à résidu nulle, la convergence
de Gauß-Newton est super-linéaire sous des hypothèses convenables.
On considère l’algorithme Gauß-Newton amélioré. Comment choisir Sk ? Il nous
faut définir une équation de la sécante. Un choix raisonnable est

Sk+1 (xk+1 − xk ) = DF (xk+1 )T − DF (xk )T F (xk+1 ).

(81)

Comme S(x) est symétrique, on peut choisir la méthode SR1 ou BFGS en commençant
pat S0 = 0.

3 Optimisation avec contraintes

Nous considérons la cas abstrait avec un sous-ensemble fermé K ⊂ Rn , et la cas
plus spécifique
K := {x ∈ Rn : g(x) ≤ 0 et h(x) = 0} , (82)
avec des fonctions régulière g : Rn → Rm et h : Rn → Rp . L’inégalité g(x) ≤ 0
veut dire que pour tout 1 ≤ i ≤ m on a gi (x) ≤ 0.
On s’intéresse alors au problème de minimisation sous contraintes :

inf f (x). (83)

x∈K

La fonction f : K → R est supposée régulière et coercive sur K :

si (xk ) ⊂ K et |xk | → ∞, alors f (xk ) → ∞. (84)

3.1 Conditions d’optimalité

Théorème 14. Si f, g, h sont de classe C 1 et x∗ ∈ K est une solution de (83) avec
K donné par (82), alors il existe λ∗ ∈ Rp et µ∗ Rm+ ainsi que µ0 ∈ R+ tels que

∀1 ≤ i ≤ m µi gi (x∗ ) = 0,
(85)
µ0 ∇f (x∗ ) + Dh(x∗ )T λ∗ + Dg(x∗ )T µ∗ = 0.

Remarque 8. Les relations (85)1 avec µ ≥ 0 et g(x∗ ) ≤ 0 s’appellent complémentarité.

On dit qu’on a complémentarité stricte si gi (x∗ ) = 0 implique µi > 0.

Démonstration. On démontre le résulta par une méthode de pénalisation. Pour tout

entier k on définit le problème sans contraintes :

 infn fk (x)
 x∈R
k k 1 (86)
fk (x) := f (x) + |h(x)|2 + |g + (x)|2 + |x − x∗ |2

2 2 2
Le problème (86) admet une solution xk ∈ Rn , car fk est coercive. On prétend que
(xk )k est bornée. Sinon, on aurait fk (xk ) ≥ f (xk ) → +∞. Et cela contredirait

fk (xk ) ≤ fk (x∗ ) = f (x∗ ) < +∞. (87)

22
On peut donc extraire une sous-suite convergente k ′ telle que xk′ → x̃. De (87) on
obtient que
 
2 + 2 2 ∗ 1 ∗ 2
|h(xk )| + |g (xk )| ≤ f (x ) − f (xk ) − |xk − x | .
k 2
Le terme entre accolades est borné, et on obtient par passage à la limite que x̃ ∈ K.
On a aussi avec (87)
1
f (x̃) + |x̃ − x∗ |2 = lim fk′ (xk′ ) ≤ f (x∗ ) ≤ f (x̃),
2 k′ →∞

ce qui implique x̃ = x∗ .
Pour écrire la condition nécessaire d’ordre un on remarque d’abord que la fonction
ϕ(x) := 12 |g + (x)|2 est différentiable avec ∇ϕ(x) = Dg(x)T g + (x) (elle composi-
tion de deux fonctions différentiables). On a alors

∇f (xk ) + k Dh(xk )T h(xk ) + k Dg(x)T g + (x) + xk − x∗ = 0 (88)

On définit maintenant
p k h(xk ) k k g + (xk ) k
sk := 1 + k 2 |h(xk )|2 + k 2 |g + (xk )|2 , λk := , µ := , µ0 = 1/sk .
sk sk
at on divise (88) par sk pour obtenir

µk0 ∇f (xk ) + Dh(xk )T λk + Dg(x)T µk + µk0 (xk − x∗ ) = 0 (89)

Par construction, le vecteur (λk , µk , µk0 ) est de longuer 1 et on peut donc trouver
une sous-suite qui converge vers (λ∗ , µ∗ , µ∗0 ) ̸= 0.
On passe à la limite dans (89) pour obtenir (85). La positivité de µ∗ est évidente. Si
gi (x∗ ) < 0 on obtient µ∗i = 0. De l’autre côté, si µ∗i > 0 g + (xk ) > 0 à partir d’un
certain rang etcela implique g(x∗ )i = 0.
Dans la suite on charche à s’assurer que µ∗0 ̸= 0. Pour cela on utilise des conditions
de qualification des contraintes.
Définition 8. (Point régulier) Soit x ∈ K. On définit l’ensemble des indices actifs :

A(x) := {1 ≤ i ≤ m : gi (x) = 0} . (90)

On appelle i tel que i ∈ A(x) une contrainte active. Alors on appelle x ∈ K un

point régulier au sens de Mangasarian-Fromowitz s’il existe d ∈ Rn \ {0} tel que
(
Dh(x)d = 0 et ⟨∇gi (x), d⟩ < 0 ∀i ∈ A(x) et
(91)
le rang de Dh(x) est maximal.

On dit que x ∈ K est point fortement régulier si

X X
λi ∇hi (x) + µi ∇gi (x) = 0 =⇒ λi = 0, µi = 0. (92)
i i∈A

Théorème 15. (Karush-Kuhn-Tucker) Mêmes hypothèse que le Théorème 14. On

suppose de plus, que x∗ est un point régulier au sens MF. Alors on a la même
conclusion avec µ∗0 = 1.

23
Démonstration. Il suffit de montrer que µ∗0 est non-nulle.
Supposons µ∗0 = 0. La maximalité du rang de Dh(x∗ ) montre qu’il existe au moins
un indice i ∈ A(x∗ ) tel que µ∗i > 0, car, sinon Dh(x∗ )T λ∗ = 0 impliquerait
λ∗ = 0, ce qui est impossible.
Le vector d de (91) donne alors

0 = ⟨Dh(x∗ )T λ∗ , d⟩ + ⟨Dg(x∗ )T µ∗ , d⟩ = ⟨µ∗ , Dg(x∗ )d⟩ ≤ µ∗i ⟨∇gi (x∗ ), d⟩ < 0,

d’où la contradiction
Pour se chauffer pour la condition d’ordre deux, on considère d’abord le cas sui-
vant.
Lemme 5. Soient ϕ, ψ ∈ C 1 (Rn ). Si x∗ est solution du problème
1
2
infn f (x), f (x) := ϕ(x) + ψ(x)+ , (93)
x∈R 2
alors on a
∇ϕ(x∗ ) + ψ(x∗ )+ ∇ψ(x∗ ) = 0, (94)
et pour tout p ∈ Rn

0 ≤ pT ∇2 ϕ(x∗ )p + ψ + (x∗ )pT ∇2 ψ(x∗ )p + σ p 2(∇ψ(x∗ ) · p)2

ψ + (x∗ + εp) (95)
+σ z lim sup ∇ψ(x∗ ) · p,
ε→0 ε
avec σp,z ∈ {0, 1} tels que σ p = 1 si et seulement si ψ(x∗ ) > 0 et σ z = 1 si et
seulement si ψ(x∗ ) = 0.
Démonstration. Pour la condition d’ordre un (94), on observe la différentiabilité
2
de la fonction (ψ(x)+ ) .
Soit p ∈ Rn arbitraire et ε > 0. Alors on a
Z 1 Z 1
f (x∗ + εp) − f (x∗ ) ∗
0 ≤ = ∇ϕ(x + tεp) · p dt + ψ + (x∗ + εtp)∇ψ(x∗ + tε) · p dt
ε 0 0
Z 1 Z 1
{∇ϕ(x∗ + tε) − ∇ϕ(x∗ )} · p dt +
 + ∗
= ψ (x + εtp)∇ψ(x∗ + tεp) − ψ + (x∗ )∇ψ(x∗ ) ·
0 0
Z 1
ε T 2
= p ∇ ϕ(x∗ )p + o(ε) + ψ + (x∗ + εtp) {∇ψ(x∗ + tεp) − ∇ψ(x∗ )} · p dt
2 0
Z 1
 + ∗
+ ψ (x + εtp) − ψ + (x∗ ) ∇ψ(x∗ ) · p dt
0

Il reste à étudier les deux intégrales. D’abord

Z 1
ε
ψ + (x∗ + εtp) {∇ψ(x∗ + tεp) − ∇ψ(x∗ )} · p dt = ψ + (x∗ )pT ∇2 ψ(x∗ )p + o(ε).
0 2
La deuxième intégrale donne lieu au termes impliquant σ p,z .
Pour exprimer les résultat d’ordre deux, on introduit l’ensemble des indices stric-
tement actif.

A∗ (x) := {1 ≤ i ≤ m : gi (x) = 0 et µi > 0} . (96)

24
Théorème 16. Soit x∗ un minumum fortement régulier et
C ∗ := p ∈ N (Dh(x∗ )) : pT ∇gi (x∗ ) = 0 ∀i ∈ A∗ (x), pT ∇gi (x∗ ) ≤ 0 ∀i ∈ A(x) \ A∗ (x) .


(97)
∗
Alors on a pour tout p ∈ C
( )
X X
0 ≤ pT ∇2 f (x∗ ) + λi ∇2 hi (x∗ ) + µi ∇2 gi (x∗ ) p. (98)
i i
∗
Remarque 9. L’ensemble C est appelé le cône critique (nom justifié !).
Démonstration. On reprend la démonstration de la condition nécessaire d’ordre
un.
Théorème 17. Soit x∗ un point vérifiant les conditions KKT et tel que
( )
X X
0 < pT ∇2 f (x∗ ) + λi ∇2 hi (x∗ ) + µi ∇2 gi (x∗ ) p. (99)
i i

pour tout p ∈ C avec

C := p ∈ N (Dh(x∗ )) : pT ∇gi (x∗ ) = 0 ∀i ∈ A∗ (x) .

(100)
Alors x∗ est un minimum local strict.

3.2 Méthodes avec projection

On considère des méthodes qui sont applicable quand l’ensemble K est relative-
ment simple.
Si K est un ensemble convexe, le projeteur πK : Rn → K est bien défini par
|x − πK x| ≤ |x − y| pour tout y ∈ K. (101)
Il est donc définit par le problème de minimisation inf f (y) avec f (y) = 21 |x − y|2
y∈K
pour x ∈ Rn donné. Soit x∗ = πK x. D’àpres le théorème XX, on a donc
⟨x − x∗ , x∗ − y⟩ = ⟨∇f (x∗ ), y − x∗ ⟩ ≥ 0 pour tout y ∈ K. (102)
Nous avons une autre caractérisation de la solution du problème sous contraintes.
Lemme 6. Soit x∗ une solution de inf f (x). Alors on a pour tout t > 0 :
x∈K

x = πK (x∗ − t∇f (x∗ )).

∗
(103)
Démonstration. On note d’abord que la condition (102) s’écrit de façon équivalente
comme
⟨x − y, x∗ − y⟩ ≥ pour tout y ∈ K. (104)
En effet, on obtient (104) en rajoutant ⟨x∗ − y, x∗ − y⟩ ≥ 0 à (102). Dans l’autre
sens, soit z ∈ K arbitraire. On choisit y = x∗ + t(z − x∗ ) avec 0 < t < 1. En
faisant tendre t → 0, on obtient (102).
En partant de (104), on obtient en rajoutant l’inégalité variationnelle de ∇f (x∗ )
⟨(x − y) − t∇f (x∗ ), x∗ − y⟩ ≥ 0,
ce qui s’écrit comme
⟨(x − t∇f (x∗ )) − y, x∗ − y⟩ ≥ 0,
où on reconnaı̂t la condition (104) avec x − t∇f (x∗ ) à la place de x.

25
On commence avec une variante de la méthode du gradient, qui tient compte des
contraintes.

Algorithme 9 : Méthode du gradient projeté

1. (Initialisaton) t0 > 0 et x0 . k = 0
2. (Recherche du pas) déterminer tk
3. (Itération) xk+1 = πK (xk − tk gk )
4. (Critère d’arrêt) Si |xk+1 − xk | ≤ ε stop. Sinon incrémente k.

Cet algorithme est déconseillé, mais nous donnons un résultat de convergence, car
sa démonstration est instructive.
Théorème 18. Soit f ∈ C 1 (Rn ), coercive et strictement convexe avec

⟨∇f (x) − ∇f (y), x − y⟩ ≥ γ∥x − y∥2 (105)

De plus on suppose que ∇f est lipschitzien avec rapport L. Si les pas vérifie

t ≤ tk ≤ t, 0 < t < t < 2/L, (106)

la méthode du gradient converge vers le minimum de f .

Démonstration. On a existence d’un minumum unique x∗ tel que pour tout t > 0

x∗ = πK (x∗ − t∇f (x∗ )).

Alors on a

∥x∗ − xk+1 ∥2 = ∥πK (x∗ − tk ∇f (x∗ )) − πK (xk − tk ∇f (xk ))∥2

≤ ∥x∗ − tk ∇f (x∗ ) − (xk − tk ∇f (xk ))) ∥2
= ∥x∗ − xk − tk (∇f (x∗ ) − ∇f (xk ))) ∥2
= ∥x∗ − xk ∥2 − 2tk ⟨(∇f (x∗ ) − ∇f (xk )) , x∗ − xk ⟩ + t2k ∥∇f (x∗ ) − ∇f (xk )∥2
1 − 2tk α2 + t2k L2 ∥x∗ − xk ∥2 .


≤

3.3 Le cas sans contraintes sous forme d’inégalités

On considère donc le problème

inf f (x). (107)

h(x)=0

3.3.1 Lagrange-Newton
L’idée est d’appliquer la méthode de Newton à l’équation de la stationnarité du
lagrangien,
L(x, λ) = f (x) + ⟨h(x), λ⟩ (108)
Nous savons que la condition nécessaire d’ordre un s’écrit comme

∇L(x, λ) = 0, (109)

26
et la condition suffisante d’ordre deux s’écrit comme

pT H(x,
e λ)p > 0 ∀p ∈ Ker Dh(x). (110)

avec p
X
e λ) := ∇2 f (x) +
H(x, λj ∇2 hj (x). (111)
j=1

Algorithme 10 : Lagrange-Newton
1. (Initialisaton) t0 > 0, x0 et λ0 . k = 0
2. (Direction) Résoudre
 2    
∇x L(xk , λk ) Dh(xk )T px ∇f x(xk ) + Dh(xk )T λk )
=− (112)
Dh(xk ) 0 rk h(xk )

3. (Recherche du pas) déterminer tk

4. (Mise à jour) xk+1 = xk + tk pk , λk+1 = λk + rk
5. (Critère d’arrêt)

A cause de la linéarité, on peut éviter la mise à jour du multiplicateur et remplacer

(112) par  2    
∇x L(xk , λk ) Dh(xk )T px ∇f x(xk )
=− (113)
Dh(xk ) 0 λk+1 h(xk )
La cause majeure qui se pose est le choix du pas. Il est évident que l’on ne doit
plus demander une descente suffisante de f comme dans le cas sans contrainte.
Généralement, on peut appliquer les critères de Powell-Wolfe à une fonction ϕ
tenant compte des contrainte, cela s’appelle fonction mérite.
Il y a différentes possibilités :
1. (Pénalisation quadratique) ϕ(x) = f (x) + σ2 ∥h(x)∥2 ,
2. (Lagrangien augmenté) ϕ(x) = f (x) + λT h(x) + σ2 ∥h(x)∥2 ,
3. (Pénalisation non-différentiable) ϕ(x) = f (x) + σ∥h(x)∥2p , 1 ≤ p ≤ ∞
(généralement p = 1 ou p = ∞).

Définition 9. On dit qu’une fonction de mérite est exacte si x∗ est un minimum

local du problème, x∗ est aussi i, minimum local de ϕ.

La notion d’exactitude est très importante pour la convergence des algorithmes.

On voit que la pénalisation quadratique est exacte, seulement si ∇f (x∗ ) = 0, ce
qui n’est pas le cas généralement. Le lagrangien augmenté est exact, si λ = λ∗ ,
le multiplicateur correspondant à x∗ . On peut démontrer que la pénalisation non-
différentiable est exacte (sous l’hypothèse de condition d’ordre deux suffisante),
si
σ > sup ∥λ∥q , 1/p + 1/q = 1, (114)
λ∈Λ∗

où Λ∗ est l’ensemble des multiplicateur à la solution x∗ .

27
3.3.2 Elimination de variables
Le cas du contrôle optimal et de l’estimation de paramètres donnent lieu à partager
x en variables d’état u et variables de contrôle (paramètres) q :

x = (u, q) ∈ Rn1 × Rn2 , n = n1 + n2 . (115)

De plus, on a souvent une équation d’état qui permet de déterminer l’état en fonc-
tion du contrôle

A(u) − Bq = 0, S : Rn1 → Rn1 , B : Rn2 → Rn1 . (116)

La fonctionnelle et les contraintes sont données par

f (x) = f1 (u) + f2 (q), h(x) = A(u) − Bq. (117)

Le lagrangien s’écrit, en mettant z à la place de −λ comme

L(u, q, z) = f1 (u) + f2 (q) − ⟨A(u) − Bq, z⟩. (118)

La stationnarité s’écrit alors comme

∇f1 (u) − A′ (u)T z
 
 ∇f2 (q) + B T z  = 0 (119)
A(u) − Bq

La première équation dans (119) s’appelle l’équation adjointe.

3.4 SQP
L’algorithme SQP (sequential quadratic programming) consiste à approcher le la-
grangien par des fonctions quadratiques :

L(x + p, λ + r, µ + s) = L(x, λ, µ) + Φ(p, r, s) + o(|p|2 + |r|2 + |s|2 ),

1 (120)
Φ(p, r, s) := ∇L(x, λ, µ)T (p, r, s) + (p, r, s)T ∇2 L(x, λ, µ)(p, r, s).
2
On cherche à la stationnarité de Φ. De plus, les conditions de complémentarité sont
à vérifier. On trouvera alors le système

∇2x L(x, λ, µ)p + Dh(x)T r + Dg(x)T s = −∇f (x) − Dh(x)T λ − Dg(x)T µ,

Dh(x)p + h(x) = 0,
Dg(x)p + g(x) ≤ 0,
(µ + s) ≥ 0,
(µ + s)T g(x) + sT Dg(x)p = 0.
(121)
Le problème majeur est donc maintenant de résoudre le système d’équations et
d’inéquations (11). Pour cela, on remarque que
Lemme 7. Le système (11) est la condition nécessaire du problème QP (quadrtic
programming) suivant :
1
inf ∇f (xk )T p + pT ∇2x L(xk , λk , µk )p
p∈Kk 2 (123)
n
Kk := {p ∈ R : h(xk ) + Dh(xk )p = 0, g(xk ) + Dg(xk )p ≤ 0} .

28
 Algorithme 11 : SQP
1. (Initialisaton) t0 > 0, x0 , λ0 et µ0 . k = 0
2. (Direction) Résoudre

∇2x L(xk , λk , µk )pk + Dh(x)T λk+1 + Dg(x)T µk+1 = −∇f (x),

Dh(xk )pk + h(xk ) = 0,
Dg(xk )pk + g(xk ) ≤ 0, (122)
µk+1 ≥ 0,
µTk+1 (g(xk ) + Dg(xk )pk ) = 0.

3. (Recherche du pas) déterminer tk

4. (Mise à jour) xk+1 = xk + tk pk .
5. (Critère d’arrêt)

On peut alors utiliser toutes les techniques possible pour résoudre le (QP) : points
intérieurs, stratégie (primale, duale, ou primale-duale) d’ensembles actifs etc.
Un question clé est le choix du pas tk .
Comme avant, en tenant compte des inégalités, les possibilités raisonnables sont :
1. P
(Lagrangien augmenté) ϕ(x) = f (x) + λT h(x) + µT g(x) + σ2 ∥h(x)∥2 +
m  σ 2 µ
j=1 µj βj + 2 βj , βj := max(− σj , gj (x)),
2. (Pénalisation non-différentiable) ϕ(x) = f (x) + σ∥h(x)∥2p + σ∥g(x)+ ∥2p ,
p = 1 ou p = ∞.

29