IRMA, univ. Strasbourgirma.math.unistra.fr/~privat/documents/M1_Optim/seance3.pdf · Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 7 / 16. Étude des fonctions

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

Yannick Privat

IRMA, univ. Strasbourg

Résumé no 3Conditions 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



Conditions d’optimalité à l’ordre 1

Sommaire







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

À quoi ça sert ?

Caractériser lesminima/maxima locaux

Quand sont-ils globaux ?

Cadre agréable : la fonctionobjectif est différentiable oumieux, deux fois différentiable

Exemple : en dimension un, si f : R→ R est dérivable, alors, tout point x∗ réalisantun minimum/maximum local vérifie

f ′(x∗) = 0

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



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],

x + t(y − x) ∈ K et doncf (x + t(y − x))− f (x)

t≥ 0.

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érifiel’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 .



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],

x + t(y − x) ∈ K et doncf (x + t(y − x))− f (x)

t≥ 0.

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érifiel’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 .



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

On s’intéresse au problème infx∈Rn

f (x)

Théorème (Condition nécessaires)

Soit x∗, un minimum local pour le problème1 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) = x4 montre que l’on n’a pas mieux que le caractère semi-défini positifde la hessienne, même si x∗ est un minimum global. L’exemple f (x) = x3 montre que cethéorème donne une condition nécessaire mais pas suffisante.

Preuve. On écrit

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

0.

On divise alors par ε > 0 puis on fait tendre ε vers 0+. Enfin, en choisissant dans ledéveloppement précédent ±h pour tout h ∈ Rn, la conclusion s’ensuit.



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


f (x)

Théorème (Condition nécessaires)

Soit x∗, un minimum local pour le problème1 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) = x4 montre que l’on n’a pas mieux que le caractère semi-défini positifde la hessienne, même si x∗ est un minimum global. L’exemple f (x) = x3 montre que cethéorème donne une condition nécessaire mais pas suffisante.

Preuve. On écrit

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

0.

On divise alors par ε > 0 puis on fait tendre ε vers 0+. Enfin, en choisissant dans ledéveloppement précédent ±h pour tout h ∈ Rn, la conclusion s’ensuit.



Condition suffisante (1er ordre, cas non contraint)


f (x)

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 pointcritique 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∗) + 〈∇f (x∗), x − x∗〉 = f (x∗).

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



Condition suffisante (1er ordre, cas non contraint)


f (x)

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 pointcritique 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∗) + 〈∇f (x∗), x − x∗〉 = f (x∗).

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


Étude des fonctions quadratiques

Sommaire







Cas d’une fonction quadratique

Résolution complète du problèmeinfx∈Rn

f (x), avec

f (x) =12〈Ax , x〉 − 〈b, x〉+ c,

avec A ∈ Sn(R), b ∈ Rn et c ∈ R.

! Rappelons que pour tout x ∈ Rn,

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

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

∃P ∈ On(R) | A = P>DP avec D =

λ1 0. . .

0 λn

avec λ1 ≤ · · · ≤ λn.





f (x), avec

f (x) =12〈Ax , x〉 − 〈b, x〉+ c,


Si λ1 < 0

Soit z ∈ R. On a :

f (ze1) =λ1

2z2−z〈b, e1〉+c −−−−→

z→+∞−∞.

Le problème d’optimisation n’a doncpas de solution dans ce cas (etn 7→ ne1 est une suite minimisante).





f (x), avec

f (x) =12〈Ax , x〉 − 〈b, x〉+ c,


Si λ1 = 0 , 2 cas à envisager

Si b /∈ (Im A), l’équation ∇f (x) = 0n’a pas de solution ⇒ le problème n’apas de solution (inf f = −∞).

Si b ∈ (Im A), l’équation ∇f (x) = 0 aune infinité de solutions ⇒ on montreque min f = − 1

2 〈b, x0〉+ 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




f (x), avec

f (x) =12〈Ax , x〉 − 〈b, x〉+ c,


Si λ1 > 0

A ∈ S++n (R).

L’équation ∇f (x) = 0 a une uniquesolutions ⇒ le problème a une uniquesolution x∗ = A−1b et

minx∈Rn

f (x) = −12〈b,A−1b〉+ c.



Exercice

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

inf(x,y)∈R2

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

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


La méthode des moindres carrés

Sommaire







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 cherchex∗ minimisant

f : Rn −→ Rx 7−→ f (x) = 1

2‖Ax − b‖2,

la notation ‖ · ‖ 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 espacevectoriel ImA.Puisque nous sommes en dimension finie, on sait qu’il existe un unique projeté b sur lesous espace vectoriel ImA, car celui-ci est de dimension finie

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




Méthode de résolution

Réécriture du critère

On peut réexprimer f (x) sous une forme mieux adaptée :

∀x ∈ Rn, f (x) =12〈A>Ax , x〉 − 〈A>b, x〉+ 1

2‖b‖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 positiveEn effet, (A>A)> = A>A et si X ∈ Rn, on a 〈A>AX ,X 〉 = ‖AX‖2. . .

! la question se ramène à l’étude des solutions de l’équation

A>Ax = A>b (équation normale).




Deux cas à envisager :

Si A est de plein rang n. Alors, d’après le théorème du rang, la matrice A estinjective, 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’estpas injective. D’après l’étude faite des fonctions quadratiques, le problème deminimisation 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 normaleA>Ax = A>b).

Remarque

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



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éessont souvent le résultat de mesures et on cherche à décrire le comportement global de cenuage. En général, ces points ne sont pas alignés, mais si on a de bonnes raisons de penserqu’ils devraient l’être (un modèle physique, biologiste, etc. peut guider l’intuition), on peutse 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 sommedes carrés des distances des points du nuage à cette droite soit minimale.Autrement dit, on cherche à résoudre

inf(α,β)∈R2

f (α, β) où f (α, β) =m∑i=1

(xi − αti − β)2,




On considère un nuage de m points de R2 : Mi = (ti , xi ), pour i ∈ {1, · · · ,m}. Ces donnéessont souvent le résultat de mesures et on cherche à décrire le comportement global de cenuage. En général, ces points ne sont pas alignés, mais si on a de bonnes raisons de penserqu’ils devraient l’être (un modèle physique, biologiste, etc. peut guider l’intuition), on peutse 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 sommedes carrés des distances des points du nuage à cette droite soit minimale.Autrement dit, on cherche à résoudre

inf(α,β)∈R2

f (α, β) où f (α, β) =m∑i=1

(xi − αti − β)2,

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

f (α, β) = ‖AX − b‖2, avec A =

t1 1...

...tm 1

, b =

x1...xm




On a vu que ce problème possède une solution unique si A est de rang plein, i.e. 2. On endéduit que ce problème possède une solution unique sauf si t1 = · · · = tm.De plus,

A>A =

( ∑mi=1 t

2i

∑mi=1 ti∑m

i=1 ti m

)et A>b =

( ∑mi=1 xi ti∑mi=1 xi

).

On en déduit que l’équation normale associée est{St2α+ Stβ = Sxt

Stα+mβ = Sx

où l’on a posé

St =m∑i=1

ti , Sx =m∑i=1

xi , Sxt =m∑i=1

xi ti et St2 =m∑i=1

t2i .

Sous réserve que l’on ne soit pas dans la situation “t1 = · · · = tm” (ce qui se retrouve encalculant le déterminant du système et en retrouvant un cas d’égalité de Cauchy-Schwarz),ce système a pour solution

α =SxSt −mSxt

(St)2 −mSt2et β =

SxtSt − SxSt2

(St)2 −mSt2.




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

année (xi ) 1999 2000 2001 2002 2003 2004chiffre d’affaire (yi , en Me) 15 20 32 26 33 55

Exercice Trouver α (coefficient directeur) etβ (ordonnée à l’origine) minimisant

(m, p) 7→6∑

i=1

(yi − αxi − β)2,

puis tracer le nuage de points et la droited’ajustement correspondante.



Sommaire







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


f (x)

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êmesnotations que précédemment. On a :

f (x∗ + h) = f (x∗) + 〈∇f (x∗), h〉+ 12〈Hess f (x∗)h, h〉+ ‖h‖2ϕ(h)

= f (x∗) +12〈Hess f (x∗)h, h〉+ ‖h‖2ϕ(h)

Comme précédemment, on remplace h par εh, h quelconque, ε petit, puis on divise par ε2

et on fait tendre ε vers 0.



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


f (x)

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êmesnotations que précédemment. On a :

f (x∗ + h) = f (x∗) + 〈∇f (x∗), h〉+ 12〈Hess f (x∗)h, h〉+ ‖h‖2ϕ(h)

= f (x∗) +12〈Hess f (x∗)h, h〉+ ‖h‖2ϕ(h)

Comme précédemment, on remplace h par εh, h quelconque, ε petit, puis on divise par ε2

et on fait tendre ε vers 0.



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) estsemi-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) = x3. En revanche, le caractère “défini-positif” de lahessienne n’est pas nécessaire, comme en témoigne l’exemple f (x) = x4.On rappelle qu’un point critique qui n’est pas un extremum local porte le nom de pointselle.









Preuve (premier point). Hess f (x∗) est définie positive, par conséquent,

∃α > 0 | 〈Hess f (x∗)h, h〉 ≥ α‖h‖2, ∀h ∈ Rn.

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

f (x∗ + h) = f (x∗) +12〈Hess f (x∗)h, h〉+ ‖h‖2ϕ(h)

≥ f (x∗) +[α2+ ϕ(h)

]‖h‖2 > f (x∗),

pourvu que h soit choisi assez petit, puisque ϕ(h) −−−→h→0

0.









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

f (β) = f (α) +N∑

k=1

(β − α)k

k!f (k)(α) +

(β − α)N+1

(N + 1)!f (N+1)(γ).

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




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

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

Notons que ϕ′(t) = 〈∇f (x∗ + th), h〉 et ϕ′′(t) = 〈Hess f (x∗ + th)h, h〉.Ainsi, il existe t ∈ [0, 1] tel que

f (x∗ + h) = f (x∗) +12〈Hess f (xt)h, h〉 ≥ f (x∗),

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→ x3 + 3xy2 − 15x − 12y .


Documents

IRMA, univ. Strasbourgirma.math.unistra.fr/~privat/documents/M1_Optim/seance3.pdf · Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 3 7 / 16. Étude des fonctions