Introduction à l’optimisation, aspects théoriques et numériques

Yannick Privat

IRMA, univ. Strasbourg

Résumé no 3
Conditions d’optimalité pour les problèmes sans contrainte

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 1 / 16

Plan

1 Conditions d’optimalité à l’ordre 1

2 Étude des fonctions quadratiques

3 La méthode des moindres carrés

4 Conditions d’optimalité à l’ordre 2

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 2 / 16

 Conditions d’optimalité à l’ordre 1

Sommaire

1 Conditions d’optimalité à l’ordre 1

2 Étude des fonctions quadratiques

3 La méthode des moindres carrés

4 Conditions d’optimalité à l’ordre 2

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 3 / 16

 Conditions d’optimalité à l’ordre 1

Conditions d’optimalité pour les problèmes non contraints

À quoi ça sert ?
Caractériser les
minima/maxima locaux
Quand sont-ils globaux ?
Cadre agréable : la fonction
objectif est différentiable ou
mieux, deux fois différentiable

Exemple : en dimension un, si f : R → R est dérivable, alors, tout point x ∗ réalisant

un minimum/maximum local vérifie

f 0 (x ∗ ) = 0

Attention à l’existence (penser à la fonction exp. . .)

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 4 / 16

 Conditions d’optimalité à l’ordre 1

Inéquation d’Euler

Soit f : K −→ R, avec
! K convexe inclus dans V , un espace de Hilbert
! f différentiable en x ∈ K .
Soit x, un minimum local de f sur K . Pour y ∈ K et t ∈]0, 1],

f (x + t(y − x)) − f (x)

x + t(y − x) ∈ K et donc ≥ 0.
t
Faisons tendre t vers 0. On a montré :

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 5 / 16

 Conditions d’optimalité à l’ordre 1

Inéquation d’Euler

Soit f : K −→ R, avec
! K convexe inclus dans V , un espace de Hilbert
! f différentiable en x ∈ K .
Soit x, un minimum local de f sur K . Pour y ∈ K et t ∈]0, 1],

f (x + t(y − x)) − f (x)

x + t(y − x) ∈ K et donc ≥ 0.
t
Faisons tendre t vers 0. On a montré :

Théorème (inéquation d’Euler).

Sous les hypothèses ci-dessus, si x est un minimum local de f sur K , alors x vérifie
l’inéquation d’Euler :
dfx (y − x) ≥ 0, ∀y ∈ K .
Si de plus, f est convexe, alors x est un minimum global de f sur K .

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 5 / 16

 Conditions d’optimalité à l’ordre 1

Condition nécessaire (1er ordre, cas non contraint)

On s’intéresse au problème infn f (x)

x∈R

Théorème (Condition nécessaires)

Soit x ∗ , un minimum local pour le problème
1 si f est différentiable en x ∗ , alors ∇f (x ∗ ) = 0. On dit que x ∗ est un point
stationnaire ou critique.
2 si f est deux fois différentiable en x ∗ , alors Hess f (x ∗ ) est semi-définie positive.

Remarque
L’exemple f (x) = x 4 montre que l’on n’a pas mieux que le caractère semi-défini positif
de la hessienne, même si x ∗ est un minimum global. L’exemple f (x) = x 3 montre que ce
théorème donne une condition nécessaire mais pas suffisante.

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 6 / 16

 Conditions d’optimalité à l’ordre 1

Condition nécessaire (1er ordre, cas non contraint)

On s’intéresse au problème infn f (x)

x∈R

Théorème (Condition nécessaires)

Soit x ∗ , un minimum local pour le problème
1 si f est différentiable en x ∗ , alors ∇f (x ∗ ) = 0. On dit que x ∗ est un point
stationnaire ou critique.
2 si f est deux fois différentiable en x ∗ , alors Hess f (x ∗ ) est semi-définie positive.

Remarque
L’exemple f (x) = x 4 montre que l’on n’a pas mieux que le caractère semi-défini positif
de la hessienne, même si x ∗ est un minimum global. L’exemple f (x) = x 3 montre que ce
théorème donne une condition nécessaire mais pas suffisante.

Preuve. On écrit

f (x ∗ ) ≤ f (x ∗ + εh) = f (x ∗ ) + h∇f (x ∗ ), εhi + |εh|ϕ(εh) , avec ϕ(εh) −−−→ 0.

ε→0

On divise alors par ε > 0 puis on fait tendre ε vers 0+ . Enfin, en choisissant dans le
développement précédent ±h pour tout h ∈ Rn , la conclusion s’ensuit.
Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 6 / 16
 Conditions d’optimalité à l’ordre 1

Condition suffisante (1er ordre, cas non contraint)

On s’intéresse au problème infn f (x)

x∈R

Théorème (Condition suffisante)

Soit f convexe et différentiable sur Rn .
Une C.N.S. pour que x ∗ soit un minimum local (donc global) de f est que x ∗ soit un point
critique de f , autrement dit, que
∇f (x ∗ ) = 0.

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 7 / 16

 Conditions d’optimalité à l’ordre 1

Condition suffisante (1er ordre, cas non contraint)

On s’intéresse au problème infn f (x)

x∈R

Théorème (Condition suffisante)

Soit f convexe et différentiable sur Rn .
Une C.N.S. pour que x ∗ soit un minimum local (donc global) de f est que x ∗ soit un point
critique de f , autrement dit, que
∇f (x ∗ ) = 0.

Preuve. La condition nécessaire résulte immédiatement du théorème précédent.

L’équivalence local-global résulte du théorème d’optimisation des fonctions convexes.
Quant à la condition suffisante, elle résulte du fait que pour tout x ∈ Rn ,

f (x) ≥ f (x ∗ ) + h∇f (x ∗ ), x − x ∗ i = f (x ∗ ).

On en déduit que x ∗ est bien un minimum.

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 7 / 16

 Étude des fonctions quadratiques

Sommaire

1 Conditions d’optimalité à l’ordre 1

2 Étude des fonctions quadratiques

3 La méthode des moindres carrés

4 Conditions d’optimalité à l’ordre 2

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 8 / 16

 Étude des fonctions quadratiques

Cas d’une fonction quadratique

Résolution complète du problème

infn f (x), avec
x∈R

1
f (x) = hAx, xi − hb, xi + c,
2
avec A ∈ Sn (R), b ∈ Rn et c ∈ R.

! Rappelons que pour tout x ∈ R , n

∇f (x) = Ax − b et Hess f (x) = A.

! On diagonalise la matrice A (d’après le théorème spectral) :

 
λ1 0
∃P ∈ On (R) | A = P > DP avec D=
 .. 
. 
0 λn

avec λ1 ≤ · · · ≤ λn .
Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 9 / 16
 Étude des fonctions quadratiques

Cas d’une fonction quadratique

Résolution complète du problème

infn f (x), avec
x∈R

1
f (x) = hAx, xi − hb, xi + c,
2
avec A ∈ Sn (R), b ∈ Rn et c ∈ R.

Si λ1 < 0
Soit z ∈ R. On a :
λ1 2
f (ze1 ) = z −zhb, e1 i+c −−−−→ −∞.
2 z→+∞

Le problème d’optimisation n’a donc

pas de solution dans ce cas (et
n 7→ ne1 est une suite minimisante).
Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 9 / 16
 Étude des fonctions quadratiques

Cas d’une fonction quadratique

Résolution complète du problème

infn f (x), avec
x∈R

1
f (x) = hAx, xi − hb, xi + c,
2
avec A ∈ Sn (R), b ∈ Rn et c ∈ R.

Si λ1 = 0 , 2 cas à envisager

Si b ∈
/ (Im A), l’équation ∇f (x) = 0
n’a pas de solution ⇒ le problème n’a
pas de solution (inf f = −∞).
Si b ∈ (Im A), l’équation ∇f (x) = 0 a
une infinité de solutions ⇒ on montre
que min f = − 12 hb, x0 i + c, avec x0
une solution de ∇f (x0 ) = 0.
Remarque : Im A = (ker A> )⊥ = (ker A)⊥ (Exercice)
Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 9 / 16
 Étude des fonctions quadratiques

Cas d’une fonction quadratique

Résolution complète du problème

infn f (x), avec
x∈R

1
f (x) = hAx, xi − hb, xi + c,
2
avec A ∈ Sn (R), b ∈ Rn et c ∈ R.

Si λ1 > 0

A ∈ Sn++ (R).
L’équation ∇f (x) = 0 a une unique
solutions ⇒ le problème a une unique
solution x ∗ = A−1 b et
1
min f (x) = − hb, A−1 bi + c.
x∈Rn 2
Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 9 / 16
 Étude des fonctions quadratiques

Exercice

Étudier en fonction du paramètre réel α l’existence de solutions pour le problème

inf f (x, y ) avec f (x, y ) = x 2 + y 2 + 2αxy − x − y + 1.

(x,y )∈R2

Lorsqu’il y a existence, déterminer les solutions. Sinon, exhiber une suite minimisante.

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 10 / 16

 La méthode des moindres carrés

Sommaire

1 Conditions d’optimalité à l’ordre 1

2 Étude des fonctions quadratiques

3 La méthode des moindres carrés

4 Conditions d’optimalité à l’ordre 2

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 11 / 16

 La méthode des moindres carrés

Complément : la méthode des moindres carrés

Soit A, une matrice réelle de taille m × n (en pratique, m >> n).

On suppose donc que m > n. On cherche à résoudre Ax = b “au mieux”, i.e. on cherche
x ∗ minimisant
f : Rn −→ R
x 7−→ f (x) = 21 kAx − bk2 ,
la notation k · k désignant bien sûr la norme euclidienne de Rn .

Existence de solutions
La question se ramène à rechercher l’existence d’un projeté de b sur le sous espace
vectoriel Im A.
Puisque nous sommes en dimension finie, on sait qu’il existe un unique projeté b sur le
sous espace vectoriel Im A, car celui-ci est de dimension finie

Présentons à présent la méthode de résolution de ce problème.

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 12 / 16

 La méthode des moindres carrés

Complément : la méthode des moindres carrés

Méthode de résolution

Réécriture du critère
On peut réexprimer f (x) sous une forme mieux adaptée :
1 > 1
∀x ∈ Rn , f (x) = hA Ax, xi − hA> b, xi + kbk2 .
2 2

On va utiliser les résultats sur la minimisation de fonctions quadratiques. Notons que :

! la matrice A A est symétrique et semi-définie positive
>
>
> > n > 2
En effet, (A A) = A A et si X ∈ R , on a hA AX , X i = kAX k . . .
! la question se ramène à l’étude des solutions de l’équation
A> Ax = A> b (équation normale).

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 12 / 16

 La méthode des moindres carrés

Complément : la méthode des moindres carrés

Deux cas à envisager :

Si A est de plein rang n. Alors, d’après le théorème du rang, la matrice A est
injective, puis A> A est également injective donc inversible. L’équation normale

A> Ax = A> b

possède alors une unique solution, solution du problème de minimisation.

Si rgA < n. Alors, la plus petite valeur propre de A> A est nulle, puisque A> A n’est
pas injective. D’après l’étude faite des fonctions quadratiques, le problème de
minimisation a soit une infinité de solutions, soit pas de solution.
Or, on a vu que le problème des moindres carrés possède (au moins) une solution.
On en déduit que le problème des moindres carrés possède dans ce cas une infinité
de solutions (correspondant à l’ensemble des solutions de l’équation normale
A> Ax = A> b).

Remarque
Dans le cas où A> A est inversible, la matrice A† = (A> A)−1 A> s’appelle pseudo-inverse
ou inverse généralisé de A. Cette notion est très utile en analyse numérique

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 12 / 16

 La méthode des moindres carrés

Exemple/Exercice : la régression linéaire

On considère un nuage de m points de R2 : Mi = (ti , xi ), pour i ∈ {1, · · · , m}. Ces données
sont souvent le résultat de mesures et on cherche à décrire le comportement global de ce
nuage. En général, ces points ne sont pas alignés, mais si on a de bonnes raisons de penser
qu’ils devraient l’être (un modèle physique, biologiste, etc. peut guider l’intuition), on peut
se demander quelle est la droite approchant au mieux ces points.
La méthode des moindres carrés consiste alors à rechercher la droite telle que la somme
des carrés des distances des points du nuage à cette droite soit minimale.
Autrement dit, on cherche à résoudre
m
X
inf f (α, β) où f (α, β) = (xi − αti − β)2 ,
(α,β)∈R2
i=1

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 13 / 16

 La méthode des moindres carrés

Exemple/Exercice : la régression linéaire

On considère un nuage de m points de R2 : Mi = (ti , xi ), pour i ∈ {1, · · · , m}. Ces données
sont souvent le résultat de mesures et on cherche à décrire le comportement global de ce
nuage. En général, ces points ne sont pas alignés, mais si on a de bonnes raisons de penser
qu’ils devraient l’être (un modèle physique, biologiste, etc. peut guider l’intuition), on peut
se demander quelle est la droite approchant au mieux ces points.
La méthode des moindres carrés consiste alors à rechercher la droite telle que la somme
des carrés des distances des points du nuage à cette droite soit minimale.
Autrement dit, on cherche à résoudre
m
X
inf f (α, β) où f (α, β) = (xi − αti − β)2 ,
(α,β)∈R2
i=1

Posons X = (α, β)> . Alors, on peut écrire que

   
t1 1 x1
2  .. ..  .. 
f (α, β) = kAX − bk , avec A =  . . , b = 

. 
tm 1 xm

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 13 / 16

 La méthode des moindres carrés

Exemple/Exercice : la régression linéaire

On a vu que ce problème possède une solution unique si A est de rang plein, i.e. 2. On en
déduit que ce problème possède une solution unique sauf si t1 = · · · = tm .
De plus,  Pm 2 Pm   Pm 
A> A = Pi=1 ti i=1 ti et A >
b = i=1 xi ti .
m P m
i=1 ti m i=1 xi

On en déduit que l’équation normale associée est


St 2 α + St β = Sxt
St α + mβ = Sx

où l’on a posé
m
X m
X m
X m
X
St = ti , Sx = xi , Sxt = xi ti et St 2 = ti2 .
i=1 i=1 i=1 i=1

Sous réserve que l’on ne soit pas dans la situation “t1 = · · · = tm ” (ce qui se retrouve en
calculant le déterminant du système et en retrouvant un cas d’égalité de Cauchy-Schwarz),
ce système a pour solution
Sx St − mSxt Sxt St − Sx St 2
α= et β= .
(St )2 − mSt 2 (St )2 − mSt 2
Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 13 / 16
 La méthode des moindres carrés

Exemple/Exercice : la régression linéaire

On s’intéresse à l’évolution du chiffre d’affaire d’une entreprise sur plusieurs années. Y
a-t-il une corrélation (linéaire) entre l’année et le chiffre d’affaire ?

année (xi ) 1999 2000 2001 2002 2003 2004

chiffre d’affaire (yi , en Me) 15 20 32 26 33 55
Exercice Trouver α (coefficient directeur) et
β (ordonnée à l’origine) minimisant
6
X
(m, p) 7→ (yi − αxi − β)2 ,
i=1

puis tracer le nuage de points et la droite

d’ajustement correspondante.

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 13 / 16

 Conditions d’optimalité à l’ordre 2

Sommaire

1 Conditions d’optimalité à l’ordre 1

2 Étude des fonctions quadratiques

3 La méthode des moindres carrés

4 Conditions d’optimalité à l’ordre 2

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 14 / 16

 Conditions d’optimalité à l’ordre 2

Conditions nécessaires (2ème ordre, cas non contraint)

On s’intéresse au problème infn f (x)

x∈R

Théorème (Conditions nécessaires)

Soit x ∗ , un minimum local pour le problème ci-dessus.
Si f est deux fois différentiable en x ∗ , alors Hess f (x ∗ ) est semi-définie positive.

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 15 / 16

 Conditions d’optimalité à l’ordre 2

Conditions nécessaires (2ème ordre, cas non contraint)

On s’intéresse au problème infn f (x)

x∈R

Théorème (Conditions nécessaires)

Soit x ∗ , un minimum local pour le problème ci-dessus.
Si f est deux fois différentiable en x ∗ , alors Hess f (x ∗ ) est semi-définie positive.

Preuve. On utilise un développement de Taylor-Young à l’ordre 2 et on utilise les mêmes

notations que précédemment. On a :
1
f (x ∗ + h) = f (x ∗ ) + h∇f (x ∗ ), hi + hHess f (x ∗ )h, hi + khk2 ϕ(h)
2
1
= f (x ∗ ) + hHess f (x ∗ )h, hi + khk2 ϕ(h)
2

Comme précédemment, on remplace h par εh, h quelconque, ε petit, puis on divise par ε2
et on fait tendre ε vers 0.

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 15 / 16

 Conditions d’optimalité à l’ordre 2

Conditions suffisantes (2ème ordre, cas non contraint)

Théorème (Conditions suffisantes)
Soit f , deux fois différentiable en x ∗ ∈ Rn , tel que ∇f (x ∗ ) = 0 et de plus :
soit Hess f (x ∗ ) est définie positive,
soit f est deux fois différentiable dans un voisinage de x ∗ et Hess f (x) est
semi-définie positive dans ce voisinage.
Alors, x ∗ est un minimum local pour f .

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 16 / 16

 Conditions d’optimalité à l’ordre 2

Conditions suffisantes (2ème ordre, cas non contraint)

Théorème (Conditions suffisantes)
Soit f , deux fois différentiable en x ∗ ∈ Rn , tel que ∇f (x ∗ ) = 0 et de plus :
soit Hess f (x ∗ ) est définie positive,
soit f est deux fois différentiable dans un voisinage de x ∗ et Hess f (x) est
semi-définie positive dans ce voisinage.
Alors, x ∗ est un minimum local pour f .

Remarque
Le caractère “semi-défini positif” de la hessienne en x ∗ ne suffit pas pour conclure,
comme en atteste l’exemple f (x) = x 3 . En revanche, le caractère “défini-positif” de la
hessienne n’est pas nécessaire, comme en témoigne l’exemple f (x) = x 4 .
On rappelle qu’un point critique qui n’est pas un extremum local porte le nom de point
selle.

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 16 / 16

 Conditions d’optimalité à l’ordre 2

Conditions suffisantes (2ème ordre, cas non contraint)

Théorème (Conditions suffisantes)
Soit f , deux fois différentiable en x ∗ ∈ Rn , tel que ∇f (x ∗ ) = 0 et de plus :
soit Hess f (x ∗ ) est définie positive,
soit f est deux fois différentiable dans un voisinage de x ∗ et Hess f (x) est
semi-définie positive dans ce voisinage.
Alors, x ∗ est un minimum local pour f .
Preuve (premier point). Hess f (x ∗ ) est définie positive, par conséquent,

∃α > 0 | hHess f (x ∗ )h, hi ≥ αkhk2 , ∀h ∈ Rn .

On écrit alors la formule de Taylor-Young à l’ordre deux en x ∗ :

1
f (x ∗ + h) = f (x ∗ ) + hHess f (x ∗ )h, hi + khk2 ϕ(h)
2
hα i
≥ f (x ∗ ) + + ϕ(h) khk2 > f (x ∗ ),
2
pourvu que h soit choisi assez petit, puisque ϕ(h) −−−→ 0.
h→0

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 16 / 16

 Conditions d’optimalité à l’ordre 2

Conditions suffisantes (2ème ordre, cas non contraint)

Théorème (Conditions suffisantes)
Soit f , deux fois différentiable en x ∗ ∈ Rn , tel que ∇f (x ∗ ) = 0 et de plus :
soit Hess f (x ∗ ) est définie positive,
soit f est deux fois différentiable dans un voisinage de x ∗ et Hess f (x) est
semi-définie positive dans ce voisinage.
Alors, x ∗ est un minimum local pour f .
Pour le deuxième point, on aura besoin du résultat suivant.

Formule de Taylor Mac-Laurin

Soit f : [α, β] −→ R une fonction N + 1 fois dérivable. Alors, il existe γ ∈]α, β[ tel que
N
X (β − α)k (k) (β − α)N+1 (N+1)
f (β) = f (α) + f (α) + f (γ).
k! (N + 1)!
k=1

Lorsque N = 1, la formule de Taylor Mac-Laurin coïncide avec la formule des accroissements finis

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 16 / 16

 Conditions d’optimalité à l’ordre 2

Conditions suffisantes (2ème ordre, cas non contraint)

Preuve (deuxième point). f étant supposée deux fois différentiable au voisinage de x ∗ , on
applique la formule de Taylor-Mac Laurin à la fonction

ϕ : t 7→ f (x ∗ + th).

Notons que ϕ0 (t) = h∇f (x ∗ + th), hi et ϕ00 (t) = hHess f (x ∗ + th)h, hi.
Ainsi, il existe t ∈ [0, 1] tel que
1
f (x ∗ + h) = f (x ∗ ) + hHess f (xt )h, hi ≥ f (x ∗ ),
2
où xt = x ∗ + th est proche de x ∗ si h est petit.

Exemple
On peut caractériser les points critiques (min local/max local/point selle) de la fonction

f : (x, y ) 7→ x 3 + 3xy 2 − 15x − 12y .

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 16 / 16