Prépa agreg Année 2013-2014

Cours option B [Link]@[Link]

Optimisation
I. Aspects théoriques

Soit V un espace vectoriel normé, A une partie de V , J : V → R. On s’intéresse aux deux types
de problèmes suivants
. problème d’optimisation sans contrainte :
Trouver x∗ ∈ V vérifiant J(x∗ ) = inf J(x).
x∈V

. problème d’optimisation avec contraintes :

Trouver x∗ ∈ A V vérifiant J(x∗ ) = inf J(x).
x∈A

Ces contraintes peuvent être de type

• inégalité
A = {x ∈ V, hi (x) ≤ 0, 1 ≤ i ≤ q} (1)
• égalité
A = {x ∈ V, gi (x) = 0, 1 ≤ i ≤ p} (2)
Dans (1) et (2), les fonctions hi et gi sont au moins continues.
La fonction J est appelée la fonction coût (ou encore fonction objectif, ou critère), et le
sous-ensemble A définissant les contraintes l’ensemble des éléments admissibles.

Questions :
. Existence ? Unicité ?
. Localisation : conditions nécessaires, suffisantes, caractérisation d’un point réalisant le
minimum.
. Calcul, expression du minimum ? Algorithme permettant de l’approcher ?

Exemples de problèmes d’optimisation :

. Déterminer le parallélépipède rectangle de volume maximal parmi ceux dont la surface
extérieure vaut 6.
. Le problème de la reine Didon : trouver la courbe plane de longueur l fixée qui enclot avec
le segment reliant ses deux extrémités la portion plane d’aire maximale.

1 Définitions et notations
Définition 1.1. On appelle suite minimisante de J dans A une suite (un )n∈N d’éléments de A
telle que
lim J(un ) = inf J(x).
n→+∞ x∈A
Définition 1.2. Soit J : V → R, A ⊂ V .
. J admet un minimum global sur A si
∃x∗ ∈ A, ∀x ∈ A, J(x) ≥ J(x∗ )
. J admet un minimum local en x∗ ∈ A si
∃V ∈ V(x∗ ), ∀x ∈ V ∩ A, J(x) ≥ J(x∗ ).

1
2 Existence et unicité
2.1 Un critère d’existence en dimension finie
Théorème 2.1. Soit J : F → R une fonction continue, F un sous ensemble fermé de RN .
On suppose que F est borné ou que F est non borné mais J est coercive, c’est-à-dire

J(x) → +∞ quand kxk → +∞. (3)

Alors J admet un minimum sur F .

Remarque 2.1. Le théorème 2.1 reste vraie si on suppose seulement que f est semi-continue
inférieurement, c’est-à-dire

∀x0 ∈ V, lim inf J(x) ≥ J(x0 ).

x→x0

Corollaire 2.1. Soit G un sous espace vectoriel de dimension finie de V , F ⊂ G un ensemble

fermé, a ∈ V . Alors

d(a, F ) = min {ka − xk, x ∈ F} est atteinte.

Application : Polynôme de meilleure approximation.

Exemple 2.1. Contre exemple en dimension infinie

On considère l’espace de Hilbert l2 (R) des suites de carré sommable dans R, muni du produit
+∞
X
scalaire < x, y >= xi yi , et J définie sur l2 (R) par
i=1

+∞
X x2i
J(x) = (kxk2 − 1)2 + .
i=1
i

Alors l’infimium de J sur l2 (R) n’est pas atteint.

2.2 Utilisation de la convexité

Proposition 2.1. Soit C un convexe de V , J : C → R une fonction convexe. Alors
. Tout minimum local de J sur C est un minimum global.
. L’ensemble des points de minimum est un ensemble convexe.
. Si J est strictement convexe, il y a au plus un minimum.

Théorème 2.2. Existence d’un minimum, cas fortement convexe.

Soit C un convexe fermé non vide d’un espace de Hilbert V , J : C → R une fonction convexe
continue sur C et coercive (c’est-à-dire vérifiant (3)). Alors il existe un minimum de J sur C.

Preuve Soit (un )n∈N une suite minimisante. La condition (3) implique que celle-ci est bornée.
On peut alors en extraire une sous-suite qui converge faiblement, c’est-à-dire

∀x ∈ V, hx, uϕ(n) i → hx∗ , xi

(dans un espace réflexif la boule unité est compacte pour la topologie faible, voir [?]) ; de plus
les convexes fermés forts coincident avec les convexes fermés pour la topologie faible (voir [?]),
et donc x∗ ∈ C. Par ailleurs grâce à la continuité (la semi-continuité inférieure est en fait
sufisante) de J que
J(x∗ ) ≤ inf ϕ(uϕ(n) ),
d’où l’on déduit que J(x∗ ) = inf J(x).
x∈C

2
Remarque 2.2. Une fonction convexe définie sur un ouvert convexe Ω de RN est continue (et
lipschitzienne sur tout compact de Ω) (voir [HU2] par exemple).
On s’intéresse maintenant aux fonctions vérifiant une condition de convexité un peu plus
forte, et on montre que dans ce cas on a convergence forte d’une suite minimisante.
Définition 2.1. Soit C un convexe de V , J : C → R. J est dite α-convexe (ou encore fortement
convexe) s’il existe α > 0 tel que
α
∀(x, y) ∈ C × C, J(tx + (1 − t)y) ≤ tJ(x) + (1 − t)J(y) − t(1 − t)kx − yk2
2
Remarque 2.3.

. Une fonction α-convexe est strictement convexe, mais la réciproque est fausse (exemple :
la fonction J(x) = − ln(x) sur C =]0, +∞[).
. Si J est α-convexe, elle vérifie en particulier
x+y J(x) + J(y) α
 
J ≤ − kx − yk2 .
2 2 8
Lemme 2.1. Soit C un convexe fermé de V , J : C → R une fonction α-convexe continue sur
C. Alors il existe deux constantes γ1 et γ2 telles que

∀x ∈ C, J(x) ≥ γ1 kxk2 + γ2 .

Preuve Voir [All12]

Théorème 2.3. Existence d’un minimum, cas fortement convexe.
Soit C un convexe fermé non vide d’un espace de Hilbert V , J : C → R une fonction
α-convexe continue sur C. Alors il existe un unique minimum x∗ de J sur C et on a
4
∀x ∈ C, kx − x∗ k2 ≤ [J(x) − J(x∗ )]. (4)
α

3 Localisation des extremums

3.1 Rappels
On notera dans toute la suite HJ (x) la matrice Hessienne d’une application J en un point
x ∈ RN , définie par HJ (x)i,j = ∂i ∂j J(x).
Proposition 3.1. Soit J une fonction deux fois différentiable en x0 ∈ RN . Alors pour tout
h ∈ RN ,
1
J(x0 + h) − J(x0 ) = h∇J(x0 ), hi + hHJ (x0 )h, hi + o(khk2 )
2

3.2 Cas sans contrainte

Dans cette partie, on considère une fonction J : RN → R au moins différentiable et
x∗ ∈ RN .
◦
Remarque 3.1. Ce qui suit vaut également pour le cas avec contraintes quand x∗ ∈ A.

3.2.1 Conditions nécessaires

Proposition 3.2. On suppose que J admet un minimum local en x∗ .
. Alors ∇J(x∗ ) = 0 (équation d’Euler).
. Si de plus on suppose J de classe C 2 , alors HJ (x∗ ) est symétrique semi-définie positive.

3
3.2.2 Conditions suffisantes
Proposition 3.3. Soit J de classe C 1 sur RN . On suppose que ∇J(x∗ ) = 0 et que de plus
. soit J est deux fois différentiable sur U un voisinage de x∗ et que pour tout x ∈ U HJ (x)
est semi-définie positive,
. soit J est deux fois différentiable en x∗ et HJ (x∗ ) est définie positive.
Alors J admet un minimum local en x∗ .

3.2.3 Cas convexe

Lemme 3.1. Soit J une fonction différentiable convexe sur C une partie convexe de RN . Alors
∀(x, y) ∈ C × C h∇J(x), y − xi ≤ J(y) − J(x).
Proposition 3.4. Soit J de classe C1 sur RN , convexe. Alors J(x∗ ) est un minimum global de
J si et seulement si ∇J(x∗ ) = 0.

3.2.4 Quelques applications

. Minimisation d’une fonctionnelle "quadratique".
Soit A ∈ MN (R) une matrice symétrique, b ∈ RN , c ∈ R. On note λ1 la plus petite valeur
propre de A, et pour x ∈ RN on pose
1
J(x) = hAx, xi − hb, xi + c.
2
Alors J est convexe si et seulement si A est semi-définie positive, et J est λ1 -convexe si et
seulement si A est définie positive. De plus, si λ1 ≥ 0 les solutions du problème
Trouver x∗ ∈ RN / J(x∗ ) = inf J(x) (5)
x∈RN
correspondent à celles du l’équation Ax = b.

. Méthode des moindres carrés. m

X
Soient (xi , yi )1≤i≤m m couples de réels donnés ; on cherche pn ∈ Pn tel que |yi −pn (xi )|2
i=1
soit minimal. Le problème s’écrit alors
Trouver a∗ ∈ Rn+1 / J(a∗ ) = inf J(a), avec J(a) = kM a − ck2 . (6)
a∈Rn+1
où
y1
 
 .. 
c =  .  ∈ Rm , M = (xji )1≤i≤m, 1≤j≤n+1 ∈ Mm,n+1 (R).
ym
et où k · k désigne la norme euclidienne de Rm . L’équation d’Euler s’écrit alors
M t M a = M tc
(qui s’appelle ici équation normale).

3.3 Cas avec contrainte

3.3.1 Contraintes convexes
Proposition 3.5. Soit J : U → R fonction convexe de classe C 1 sur U un ouvert de RN . Soit
C ⊂ U un convexe, x∗ ∈ C. Alors J(x∗ ) est un minimum de J sur C si et seulement si
∀y ∈ C, h∇J(x∗ ), y − x∗ i ≥ 0.

Exemple 3.1. Caractérisation du projeté sur un convexe fermé.

4
3.3.2 Contraintes de type égalité
Ici l’ensemble des contraintes est du type

A = {x ∈ RN , gi (x) = 0, 1 ≤ i ≤ p} (7)

Théorème 3.1. Extrema liés

Soient J, g1 , . . . , gp : RN → R de classe C 1 , A définie par (7). On suppose
. qu’il existe x∗ ∈ A tel que J(x∗ ) = inf J(x)
x∈A
. que la famille (∇g1 (x∗ ), . . . , ∇gp (x∗ )) est libre (condition de qualification des contraintes).
Alors il existe des réels λ1 , . . . , λp (appellés multiplicateurs de lagrange) tels que
p
∇J(x∗ ) + λi ∇gi (x∗ ) = 0.
X
(8)
i=1

On peut utiliser pour la preuve du Théorème 3.1 le résultat de géométrie différentielle (cf
[Rou] par exemple) suivant

Théorème 3.2. Soit U un ouvert de RN , g1 , . . . , gp : RN → R de classe C 1 , A définie par

(7), a ∈ A. On suppose que la famille (∇g1 (x∗ ), . . . , ∇gp (x∗ )) est libre. Alors l’espace vectoriel
tangent à A en a est
p
[Vect ∇gi (a)]⊥ .
\

i=1

Exemples d’applications
. Diagonalisation des endomorphismes symétriques en dimension finie
. Inégalité arithmético-géométrique

3.3.3 Contraintes de type inégalité

Ici l’ensemble des contraintes est du type

A = {x ∈ RN , hi (x) ≤ 0, 1 ≤ i ≤ q} (9)

On note ici I = {1, . . . , q} et I0 (x∗ ) l’ensemble des contraintes saturées au point x∗ :

I0 (x∗ ) = {i ∈ {1, . . . , q}/ hi (x∗ ) = 0}.

Définition 3.1. On dit que les contraintes sont qualifiées au point x∗ si

. ou bien les fonctions hi sont affines
. ou bien les vecteurs ∇hi (x∗ ), pour i ∈ I0 (x∗ ), sont linéairement indépendants.

Théorème 3.3. Kuhn Tucker

Soit J et hi , i ∈ I des fonctions de classe C 1 . On suppose les contraintes qualifiés au point x∗ .
Alors une condition nécessaire pour que x∗ soit un minimum de J sur l’ensemble C = {x ∈
RN , hi (x) ≤ 0, i ∈ I} est qu’il existe des réels positifs λ1 , λ2 , . . . , λq (appelés multiplicateurs de
Kuhn-Tucker ou de Lagrange généralisés) tels que
q

∇J(x∗ ) + λi ∇hi (x∗ ) = 0

 X

i=1 (10)

 ∗

avec λi hi (x ) = 0 pour i ∈ {1, . . . , q}.

Remarque 3.2. Dans le cas où J et les hi , i ∈ I sont des fonctions convexes, on peut montrer
que x∗ est un minimum de J sur le convexe A si et seulement si il existe des réels positifs λ1 ,
λ2 , . . . , λq tels que la condition (10) soit réalisée.

5
3.3.4 Contraintes mixtes
Le théorème suivant contient les Théorèmes 3.1 et 3.3.

Théorème 3.4. Kuhn Tucker, Lagrange

Soit J, gi , i ∈ {1, . . . , p}, et hi , i ∈ {1, . . . , q}, des fonctions de classe C 1 . On veut minimiser J
sur l’ensemble

A = {x ∈ RN , gi (x) = 0, 1 ≤ i ≤ p, hi (x) ≤ 0, 1 ≤ i ≤ q}

On suppose les contraintes qualifiés au point x∗ . Alors une condition nécessaire pour que x∗
soit un minimum de J sur l’ensemble C = {x ∈ RN , gi (x) = 0, 1 ≤ i ≤ p, hi (x) ≤ 0, i ∈
I} est qu’il existe des réels positifs λ1 , λ2 , . . . , λq et des réels µ1 , . . ., µp tels que
q p

∗ ∗
µi ∇gi (x∗ )
 X X
∇J(x ) + λi ∇hi (x ) =


i=1 i=1 (11)

 ∗

avec λi hi (x ) = 0 pour i ∈ {1, . . . , q}.

Annexe : caractérisation des fonctions convexes et α-convexes

Fonctions convexes
Définition 3.2. Soit C un convexe ; J : C → R est convexe si

∀(x, y) ∈ C × C, ∀t ∈ [0, 1], J(tx + (1 − t)y) ≤ tJ(x) + (1 − t)J(y).

Proposition 3.6. Soit U un ouvert convexe de RN et J une fonction différentiable de U

dans R. On a équivalence entre
(i) J est convexe
(ii) Le graphe de J est "au-dessus de ses tangentes"

∀(x, y) ∈ U × U, J(y) ≥ J(x) + h∇J(x), y − xi

(iii) L’application ∇J : U → RN est "monotone"

∀(x, y) ∈ U × U, h∇J(y) − ∇J(x), y − xi ≥ 0

De plus il y a équivalence entre la convexité stricte de J et les inégalités (ii) et (iii) rendues
strictes, pour x 6= y.

Proposition 3.7. Soit U un ouvert convexe de RN et J une fonction deux fois différentiable
de U dans R. On a équivalence entre
(i) J est convexe
(ii) HJ (x) est semi-définie positive pour tout x ∈ RN :

∀(x, h) ∈ RN × RN , hHJ (x)h, hi ≥ 0.

Fonctions α-convexes
Définition 3.3. Soit C un convexe d’un espace vectoriel normé, J : C → R est α-convexe si
α
∀(x, y) ∈ C × C, ∀t ∈ [0, 1], J(tx + (1 − t)y) ≤ tJ(x) + (1 − t)J(y) − t(1 − t)kx − yk2 .
2

6
Proposition 3.8. Soit C un convexe d’un espace vectoriel normé, J : C → R. On a les équiv-
alences suivantes
α
J est α-convexe ⇔ J − k · k2 est convexe
2
x+y J(x) + J(y) α
 
⇔ ∀(x, y) ∈ C × C, J ≤ − kx − yk2
2 2 8

Proposition 3.9. Soit U un ouvert convexe de RN et J une fonction différentiable de U

dans R. On a les équivalences suivantes
α
J est α-convexe ⇔ ∀(x, y) ∈ U × U, J(y) ≥ J(x) + h∇J(x), y − xi + ky − xk2
2
⇔ ∀(x, y) ∈ U × U, h∇J(y) − ∇J(x), y − xi ≥ αkx − yk2

Proposition 3.10. Soit U un ouvert convexe de RN et J une fonction deux fois différentiable
de U dans R. Alors

J est α-convexe ⇔ ∀(x, h) ∈ U × RN , hHJ (x)h, hi ≥ αkhk2 .

Références
[Avez] Avez Calcul différentiel
[Brez] Haïm Brezis, Analyse fonctionnelle, Collection Mathématiques Appliquées pour la
Maîtrise. Masson, Paris, 2002.
[Cia82] Philippe G. Ciarlet. Introduction à l’analyse numérique matricielle et à l’optimisation.
Collection Mathématiques Appliquées pour la Maîtrise. Masson, Paris, 1982.
[All12] Grégoire Allaire. Analyse numérique et optimisation. Collection Editions Ecole Poly-
technique. Ellipses, 2012.
[OA] Beck Vincent, Malik J. Peyré Gabriel Objectif agrégation Editions H&K.
[HU1] Jean-Baptiste Hiriart-Urupty Optimisation et analyse convexe, PUF
[HU2] Jean-Baptiste Hiriart-Urupty Convex Analysis and Minimization Algorithms I,
Springer-Verlag, 1996.
[Rou] François Rouvière Petit guide du calcul différentiel à l’usage de la licence et de l’agré-
gation, Editions Cassini.