Programmation mathématique SMA 5

UNIVERSITE MOULAY ISMAIL

FACULTE DES SCIENCES
MEKNES

SMA 5

Programmation mathématique
—————————

Optimisation convexe différentiable

Chapitre 1
2018-2019

kabbajsaid63@[Link]

1 Pr. Said Kabbadj

Programmation mathématique SMA 5

Table des matières

1. Notions fondamentales
1.1 Introduction
1.1.1 Motivation et vocabulaire
1.1.2 Différents types d’optimisation
1.2 Différentiabilité
1.2.1 Gradient et hessienne
1.2.2 Formules de Taylor
1.3 Convexité
1.3.1 Ensembles convexes
1.3.2 Fonctions convexes
1.3.3 Caractérisation des fonctions convexes
1.4 Projection sur un convexe fermé
1.5 Existence et unicité d’un point de minimum
1.6 Conditions d’optimalité
1.6.1 Conditions d’optimalité du premier ordre
1.6.2 Conditions d’optimalité du second ordre

2. Algorithmes de descente pour des problèmes d’optimisation sans

contraintes
2.1 Introduction
2.2 Vecteurs et facteurs de descente
2.3 Généralités sur les algorithmes de descente
2.4 Algorithmes de descente du gradient
2.4.1 Algorithme du gradient à pas fixe
2.4.2 Algorithme du gradient à pas optimal
2.5 La méthode des gradients conjugués

3. Conditions d’optimalité
3.1 Conditions d’optimalité
3.2 Conditions d’optimalité pour les problèmes avec contraintes d’égalités
3.3 Conditions d’optimalité pour les problèmes avec contraintes d’inégalités
3.4 Conditions d’optimalité pour les problèmes avec contraintes d’égalités et
d’inégalités

4. Problèmes d’optimisation avec contraintes

4.1 Introduction
4.2 Algorithmes du gradient à pas fixe avec projection
4.3 Méthodes de dualité

2 Pr. Said Kabbadj

Programmation mathématique SMA 5

Chapitre 1

Notions fondamentales

1.1 Introduction

1.1.1 Motivation et vocabulaire : L’optimisation est une branche des mathématiques

cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les
problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble .

On appelle problème d’optimisation tout problème de la forme :

(P) : 00
Trouver x∗ ∈ U tel que f (x∗ ) = min f (x)00 .
x∈U

U étant une partie d’un ensemble E , et f : E → R est une fonction donnée. Le but
de l’optimisation est de proposer des algorithmes permettant d’approcher les solutions
x∗ de (P) au sens où partant d’un vecteur initial x0 quelconque, on construit explici-
tement une suite de vecteurs {xk }k∈N convergent vers une solution x∗ . Le problème
d’optimisation est dit sans contraintes si U = E, et sous contraintes sinon .

On dit que :

• f est la fonction objectif ou critère d’optimisation .

• v = f (x∗ ) est la valeur optimale .
• x∗ est une solution optimale .
• U est l’ensemble des solutions réalisables ou admissibles .

Dans ce cours on se placera toujours dans le cas où E = Rp (c’est à dire en dimension
finie ). On note < ·, · > le produit scalaire canonique et k · k la norme euclidienne
associée définie par :

3 Pr. Said Kabbadj

Programmation mathématique SMA 5

√
∀x ∈ Rp , kxk = < x, x > .

Les méthodes développées dans ce cours permettent aussi de trouver les valeurs maxi-
males de f, pour cela il suffit de remplacer f par -f , puisque :

max f (x) = − min(−f (x)).

x∈U x∈U

Exemple 1.1 : Un problème de production

Une usine a besoin de n produits a1 , .., an en quantité x1 , .., xn pour fabriquer un produit
fini b en quantité h(x1 , .., xn ). Soit pi le prix unitaire du produit i et p le prix de vente
du produit fini. On désire calculer la production optimale. Il s’agit donc de maximiser
la fonction
i=n
X
f(x) = ph(x1 , .., xn ) - p i xi
i=1

1.1.2 Différents types d’optimisation :

1. Optimisation linéaire :
• f est une fonction linéaire f(x) = < c, x >
• U est défini par des fonctions affines.
2. Optimisation quadratique .
• f est une fonction quadratique : f(x) = 21 < Ax, x > + < b, x >
A est une matrice symétrique sdéfinie positive
• U est défini par des fonctions affines.

3. Optimisation convexe :
f est une fonction convexe et U est un domaine convexe .

4. Optimisation différentiable :
f est une fonction différentiable et les fonctions (contraintes) sont différentiables.

5. Optimisation non différentiable :

f n’est pas différentiable sur U .

1.2 Différentiabilité

1.2.1 Gradient et hessienne

Définitions 1.2 Soit U ⊂ Rp un ouvert et f : U → R

4 Pr. Said Kabbadj

Programmation mathématique SMA 5

1. On dit que f est différentiable au point x ∈ U s’il existe un voisinage V de x dans

U , une application linéaire Lx : Rp → R et ε : V → R tels que :
lim ε(y − x) = 0 et ∀y ∈ V , on a :
y ∈V →x

f (y) = f (x) + Lx (y − x) + ky − xkε(y − x).

Lx est la différentielle de f en x et on la note dfx .

2. ∀x ∈ U , ∀h ∈ Rp . On note (s’il existe)

∂f f (x + th) − f (x)
(x) = lim = g0(0) avec g(t) = f (x + th) ,
∂h t→0 t
et on l’appelle la dérivée directionnelle de f en x suivant la direction h.

3. ∀x ∈ U ,∀i ∈ {1, ..., p} . On note (s’il existe)

∂f f (x + tei ) − f (x) ∂f
(x) = lim = (x) ,
∂ei t→0 t ∂xi
et on l’appelle la dérivée partielle de f au point x de direction xi .

∂f ∂f
4. ∀x ∈ U, on note (quand il existe) ∇f (x) = ( (x), ........, (x))T
∂x1 ∂xp
est le vecteur gradient de f en x.

5. f ∈ C m (U) si toutes les dérivées partielles jusque à l’ordre m existent et continues

6. ∀x ∈ U , on note (quand il existe ) ∇2 f (x) la matrice hessienne de f en x telle

que :
∂f
(∇2 f (x))i,j = (x) .
∂xi ∂xj
Remarque 1.3

∂f
(a) (x) = 0, ∀x
∂0
∂f ∂f
(b) (x) = (x), ∀x
∂xi ∂ei
Proposition 1.4
1 Si f est différentiable en x , alors f est continue en x et admet en x une dérivée
directionnelle suivant tout vecteur v ∈ Rp de plus

∂f
dfx (v) = (x).
∂v

5 Pr. Said Kabbadj

Programmation mathématique SMA 5

2 Si f est différentiable en x alors les n dérivées partielles de f en x existent et

p
p
X ∂f
∀h ∈ R , dfx (h) =< ∇f (x), h >= (x)hi
i=1
∂x i

3 Soient U ouvert de Rp et V ouvert de R . Si f : U → R et g : V → R deux

fonctions de classe C 1 avec f (U) ⊂ V alors g ◦ f est de classe C 1 et

∇(g ◦ f )(x) = g 0 (f (x)) · ∇f (x) , ∀x ∈ U

4 Si f ∈ C 2 (U) alors la matrice hessienne est symétrique.

Proposition 1.5 Si f : U → R une fonction deux fois différentiable alors

∀x ∈ U, ∀h ∈ Rp , ∇2 f (x)h = ∇ < ∇f (x), h > .

Preuve. Pour i = 1, ...., , p ;

p p
∂ < ∇f (x), h >= ∂
X ∂f X ∂ 2f
(x)hj = (x)hj = (∇2 f (x)h)i
∂xi ∂xi ∂x j ∂x i ∂x j
j=1 j=1

Exemples 1.6 Soit f : Rp → R

(a) Si f(x) = c ∈ R ( fonction constante) alors :

∇f = 0 et ∇2 f = 0

(b) Si f(x) = < a, x > ( fonction linéaire ) alors :

∇f = a et ∇2 f = 0.
∂f
( = ai ⇒ ∇f = a ⇒ ∇2 f = 0.)
∂xi
Exercice 1.7 Soit f : Rp → R une fonction quadratique associée à la matrcice A ∈
Mp (R) définie par :

f (x) =< Ax, x >, ∀x ∈ Rp

Montrer que :
1) ∇f (x) = (A + AT )x , ∀x ∈ Rp .
2) ∇2 f (x) = A + AT , ∀x ∈ Rp .

6 Pr. Said Kabbadj

Programmation mathématique SMA 5

1.2.2 Formules de Taylor

Soit U un ouvert de Rp , a ∈ U , h ∈ Rp et f : U → R tels que , [a, a + h] ⊂ U .

Proposition 1.8 : Si f ∈ C 1 (U) alors :

Z 1
f (a + h) = f (a) + < ∇f (a + th), h > dt. (1)
0

(1) est la formule de Taylor à l’ordre 1 avec reste intégral

f (a + h) = f (a)+ < ∇f (a), h > + ◦ (khk) (2)

(2) est la formule de Taylor-Young à l’ordre 1.

f (a + h) = f (a)+ < ∇f (a + θh), h >, avec θ ∈]0, 1[ (3)

(3) est la formule de Taylor-Maclaurin à l’ordre 1 .

Proposition 1.9 : Si f ∈ C 2 (U) alors :

Z 1
f (a + h) = f (a)+ < ∇f (a), h > + (1 − t) < ∇2 f (a + th)h, h > dt. (4)
0

(4) est la formule de Taylor à l’ordre 2 avec reste intégral .

1
f (a + h) = f (a)+ < ∇f (a), h > + < ∇2 f (a)h, h > + ◦ (khk2 ). (5)
2
(5) est la Formule de Taylor-Young à l’ordre 2 :

1
f (a + h) = f (a)+ < ∇f (a), h > + < ∇2 f (a + θh)h, h >, avec θ ∈]0, 1[. (6)
2
(6) est la formule de Taylor-Maclaurin à l’ordre 2.

7 Pr. Said Kabbadj

Programmation mathématique SMA 5

1.3 Convexité :

1.3.1 Ensembles convexes :

Définition 1.10 Soit U un sous ensemble de Rp , U est dit :

• Affine si ∀x, y ∈ U, ∀λ ∈ R, λx + (1 − λ)y ∈ U .

• Convexe si ∀x, y ∈ U, ∀λ ∈ [0, 1] , λx + (1 − λ)y ∈ U .

Exemple
1. Tout ensemble affine est convexe .
2. Un sous espace vectoriel est convexe .

Proposition 1.11 Si U1 et U2 sont des parties convexes de Rp , alors :

1. U1 + U2 est convexe .
2. αU1 est convexe ,∀α ∈ R .
3. U1 ∩ U2 est convexe .
4. Le produit cartésien U1 × U2 est convexe dans Rp × Rp .

1.3.2 Fonctions convexes :

Définitions 1.12 Soit U ⊂ Rp convexe . f : U ⊆ Rp → R est dite :

1. Convexe sur U si :
∀x, y ∈ U , ∀λ ∈ [0, 1] , f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) .

2. Strictement convexe sur U si :

∀x, y ∈ U, x 6= y, ∀λ ∈]0, 1[ , f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) .

3. (Strictement ) concave sur U si son opposée -f est (strictement ) convexe

8 Pr. Said Kabbadj

Programmation mathématique SMA 5

4. α-fortement convexe (ou fortement convexe ) sur U si ∃α ∈ R, ∀x, y ∈ U, ∀λ ∈

[0, 1] :
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − α2 λ(1 − λ)kx − yk2 .

5. Elliptique si f est de classe C 1 (U) et fortement convexe .

6. Coercive si et seulement si :
lim f (x) = +∞ .
kxk→+∞

Remarque 1.13 On peut également restreindre θ à ]0, 1[ pour la définition de la

convexité

Exemples 1.14

1. Toute fonction linéaire est convexe .

2. Sur R , la fonction x → x2 est strictement convexe .

3. Sur R , la fonction x →| x | est convexe mais pas strictement covexe . Soit x 6= 0,

| 12 .x + 21 .0 |= 21 | x |= 12 | x | + 12 | 0 | .

4. Le sup d’une famille quelconque de fonctions convexes est convexe.

5. Toute norme sur Rp est convexe .

Définition 1.15 L’épigraphe d’une fonction f est définie par :

epi(f ) = {(x, λ) ∈ Rp × R , f (x) ≤ λ} .

9 Pr. Said Kabbadj

Programmation mathématique SMA 5

Proposition 1.16 Soit f : Rp → R .

1. f est convexe ⇔ epi(f ) est convexe .
2. Soient f et g deux fonctions convexes alors :
(a) f + g est convexe .
(b) ∀α ≥ 0, αf est convexe .

Preuve : 1. Soient x, y ∈ Rp , λ1 , λ2 ∈ R tel que (x, λ1 ), (y, λ2 ) ∈ epi(f ) et soit

θ ∈ [0, 1] .
Supposons que f est convexe, on a :
θ(x, λ1 ) + (1 − θ)(y, λ2 ) = (θx + (1 − θ)y, θλ1 + (1 − θ)λ2 )
Alors :
f (θx + (1 − θ)y) ≤ θf (x) + (1 − θ)f (y) ≤ θλ1 + (1 − θ)λ2
Et par conséquent : θ(x, λ1 ) + (1 − θ)(y, λ2 ) ∈ epi(f ) , d’où epi(f ) est convexe .

Réciproquement , on suppose que epi(f ) est convexe .

Soient (x, f (x)), (y, f (y)) ∈ epi(f ) et λ ∈ [0, 1] ,on a :
λ(x, f (x)) + (1 − λ)(y, f (y)) ∈ epi(f )
Alors :
(λx + (1 − λ)y, λf (x) + (1 − λ)f (y)) ∈ epi(f )
Et donc :
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) , d’où f est convexe .

1.3.3 Caractérisation des fonctions convexes

Proposition 1.17 Soit U un ouvert de Rp , V ⊂ U est un convexe et f : U → R est

de classe C 1 .

a) Les propositions suivantes sont équivalentes :

1. f est convexe sur V.

2.
f (y) ≥ f (x)+ < ∇f (x), y − x >, ∀x, y ∈ V (7)
3. (Monotonie de ∇f sur V ) .

< ∇f (y) − ∇f (x), y − x >≥ 0, ∀x, y ∈ V (8)

10 Pr. Said Kabbadj

Programmation mathématique SMA 5

b) Si de plus f est de classe C 2 sur U alors f est convexe sur V si et seulement si

< ∇2 f (x)(y − x), y − x >≥ 0, ∀x, y ∈ V. (9)

Preuve. a) Montrons que 1. ⇒ 2. ⇒ 3. ⇒ 1.

1 ⇒ 2e Soient x, y ∈ V et t ∈]0, 1] , f est convexe donc :

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

f (x+t(y−x))−f (x)
(10) ⇒ t
≤ (f (y) − f (x)) , en faisant tendre t vers 0

∂f (x)
⇒ ∂(y−x) ≤ f (y) − f (x)
⇒ < ∇f (x), y − x >≤ f (y) − f (x).

2 ⇒ 3e On a :

f (y) ≥ f (x)+ < ∇f (x), y − x >

et

f (x) ≥ f (y)+ < ∇f (y), x − y >

On faisant la somme et ces deux inégalités on obtient :

< ∇f (y) − ∇f (x), y − x >≥ 0.

3 ⇒ 1e Soient x , y fixés de V et t ∈ [0, 1] . Soit g :[0, 1] → R , avec

g(t) = f (ty + (1 − t)x) = f (x + t(y − x)) ∈ R

g est de classe C 1 avec g0(t)=< ∇f (x + t(y − x)), y − x > .

Soient t1 , t2 ∈ [0, 1] , avec t1 < t2 . On a :
1
g0(t2 ) − g0(t1 ) = t2 −t1
< ∇f (x + t2 (y − x)) − ∇f (x + t1 (y − x), (t2 − t1 )(y − x) >≥ 0

Donc g0 est croissante, d’où g est convexe sur [0, 1], par conséquent pout t ∈ [0, 1] :

g(t.1 + (1 − t).0) ≤ tg(1) + (1 − t)g(0)

C’est à dire : f (ty + (1 − t)x) ≤ tf (y) + (1 − t)f (x) .

b) f est de classe C 2 . Supposons que f est convexe et montrons (9)

Soit h ∈ Rp fixé et soit g : U → R la fonction définie par g(x) =< ∇f (x), h >, ∀x ∈ U
Par application de la proposition 1.5. :

11 Pr. Said Kabbadj

Programmation mathématique SMA 5

∂g(x) < ∇f (x + th) − ∇f (x), th >

< ∇2 f (x)h, h >=< ∇g(x), h >= = lim ,
∂h t→0 t2
Soit x, y ∈ V, et h = y-x , x + t(y-x) ∈ V donc de la monotonie de ∇f et de l’inégalité
précédente on déduit (9) .

Inversement soient x, y ∈ V fixés

On définit h :U → R tel que :

h(z)=< ∇f (z), x − y >, ∀z ∈ U

On a :

h(x) − h(y) =< ∇f (x) − ∇f (y), x − y >

Et d’après la formule de Taylor on a :

∀θ ∈]0, 1[ , h(x) − h(y) =< ∇h(y + θ(x − y)), x − y >

Or : ∀z ∈ V, ∇h(z) = ∇2 f (z)(x − y). Alors :

< ∇f (x) − ∇f (y), x − y >=< ∇2 f (y + θ(x − y))(x − y), (x − y) > (11)

Puisque y − z = −θ(x − y) ,
1
< ∇2 f (y + θ(x − y))(x − y), (x − y) >= < ∇2 f (z)(y − z), (y − z) > (12)
(θ)2

(11) et (12) permettent de déduire la monotonie de ∇f , donc f est convexe .

Proposition 1.18 Soit U un ouvert de Rp , V ⊂ U est un convexe et f : U → R est

de classe C 1 .

a) Les propositions suivantes sont équivalentes :

1. f est strictement convexe sur V.

2.
f (y) > f (x)+ < ∇f (x), y − x >, ∀ x, y ∈ V avec x 6= y (13)
3. ∇f est strictement monotone sur V , c’est à dire :

< ∇f (y) − ∇f (x), y − x >> 0, ∀x, y ∈ V avec x 6= y (14)

b) Si de plus f est de classe C 2 sur U alors si

< ∇2 f (x)(y − x), y − x >> 0, ∀x, y ∈ V avec x 6= y (15)

12 Pr. Said Kabbadj

Programmation mathématique SMA 5

alors f est strictement convexe sur V.

Remarques 1.19

(i) Dans le cas particulier où V est ouvert pour les deux propositions précédentes les
inégalités (9) et (15) concernant la matrice hessienne ∇2 f s’écrivent respectivement :

< ∇2 f (x)h, h >≥ 0, ∀x ∈ V, ∀h ∈ Rp . (9’)

< ∇2 f (x)h, h >> 0, ∀x ∈ V, ∀h ∈ Rp . (15’)

( Puisque V est ouvert , ∀h ∈ Rp et pour t > 0 assez petit , y = x + th ∈ V.

(ii) Dans b) de la proposition , il n’y a pas équivalence . f : R → R avec f (x) = x4 , est

strictement convexe , mais (15) n’est pas vérifiée si x = 0.

(iii) Dans le cas particulier p = 1 et V un intervalle dans R, on a ∇2 f (x) = f 00 (x),

donc < ∇2 f (x)(x − y), (x − y) >= f 00 (x)(y − x)2 . Alors (9) et (15) peuvent s’écrire
respectivement :
f 00 (x) ≥ 0, ∀x ∈ V et f 00 (x) > 0, ∀x ∈ V
On retrouve donc une caractérisation bien connue pour la convexité et la convexité
stricte .

1.4 Projection sur un convexe fermé

Définition 1.20 Soit C un convexe fermé de Rp et x ∈ Rp . On considère le problème

d’optimisation convexe suivant :

min k y − x k
(P0 )
y∈C
Proposition 1.21

a) Pour tout x ∈ Rp , le problème (P0 ) admet une unique solution PC (x) appelée pro-
jection de x sur C, et PC : Rp −→ C est appelé opérateur projection sur C.

b) PC (x) est la projection de x sur C si et seulement si :

< x − PC (x), y − PC (x) >≤ 0, ∀y ∈ C. (16)

13 Pr. Said Kabbadj

Programmation mathématique SMA 5

c) L’opérateur PC est  monotone  : C’est à dire ∀x1 , x2 ∈ Rp

hPC (x1 ) − PC (x2 ), x1 − x2 i ≥ 0.

Preuve. a) Existence : on pose d = d(x, C) = inf k x − z k . Puisque

z∈C
d2 = inf k x − z k2 et par définition de la borne inférieure, on a :
z∈C
1
∀n ∈ N ∗ , ∃yn ∈ C, k x − yn k2 ≤ d2 +
. (17)
n
Montrons que {yn } est de cauchy. Par l’identité de parallélogramme

k z − z 0 k2 = 2 k z k2 +2 k z 0 k2 − k z + z 0 k2 (18)
En remplaçant z par yn − x et z’ par yp − x dans (18) , on a

k yn − yp k2 = 2 k yn − x k2 +2 k yp − x k2 − k yn + yp − 2x k2
yn +yp yn +yp
= 2 k yn − x k2 +2 k yp − x k2 −4 k 2
− x k2 , 2
∈ C donc
≤ (2d2 + n2 ) + (2d2 + p2 ) − 4d2
= n2 + p2
D’autre part n1 → 0, p1 → 0, donc ∀ε > 0, ∃Nε ∈ N, ∀n, p ≥ N : n1 + p1 ≤ 2ε , donc {yn }
est de cauchy, Rp est complet d’où yn → y ∈ C . D’ après (17), on a k x − y k≤ d d’où
k x − y k= d .

Unicité : Supposons qu’ils existe y, y 0 ∈ C tels que : y 6= y 0 , d =, k x − y k=k x − y 0 k

D’après (18),
y+y 0
k 2
− x k2 =k 12 (y − x) + 21 (y 0 − x) k2

= 12 k y − x k2 + 12 k y 0 − x k2 − 14 k y − y 0 k2
= d2 − 14 k y − y 0 k2 < d2 ,
y+y 0 y+y 0
2
∈ C et k 2
− x k2 < d2 est absurde .

b) Soit :

(i) : ∀y ∈ C, kx − PC (x)k ≤ kx − yk,

(ii) : ∀y ∈ C, < x − PC (x), y − PC (x) >≤ 0.

Montrons que (i) et (ii) sont équivalentes

(i) implique (ii) : Soient y un élément de C et λ un réel compris entre 0 et 1, alors

λy + (1–λ)PC (x) ∈ C , d’après la propriété (1), donc :

14 Pr. Said Kabbadj

Programmation mathématique SMA 5

kx − PC (x)k2 ≤ kx − PC (x) − λ(y − PC (x))k2

On en déduit la majoration :

2λ hx − PC (x) , y − PC (x)i ≤ λ2 ky − PC (x)k2

Il suffit alors de diviser par λ puis de passer à la limite quand λ tend vers 0 (par valeurs
strictement positives) pour obtenir le résultat.

(ii) implique (i) :

kx − yk2 = kx − PC (x)k2 − 2hx − PC (x) , y − PC (x)i + ky − PC (x)k2 ≥ kx − PC (x)k2 .

Remarquons qu’ici, la convexité de C n’est pas utile.

c) L’application PC est  monotone  : C’est une conséquence directe du fait que

< PC (x1 )–x1 , PC (x1 )–PC (x2 ) > et < PC (x2 )–x2 , PC (x2 )–PC (x1 ) > sont tous deux
négatifs ou nuls. En sommant ces deux inégalités on obtient que

hPC (x1 ) − PC (x2 ), x1 − x2 i ≥ kPC (x1 ) − PC (x2 )k2 ≥ 0.

1.5 Existence et unicité d’un point de minimum

Définitions 1.22 Soit U ⊂ Rp , f : U → R et x∗ ∈ U .

• On dit que x∗ est un point de minimum global ( ou absolu ) de f sur U si :

∀x ∈ U, f (x) ≥ f (x∗ ) .

• On dit que x∗ est un point de maximum global de f sur U si :

∀x ∈ U, f (x) ≤ f (x∗ ) .

• On dit que x∗ est un minimum local ou relatif de f sur U s’il existe un voisinage
V de x∗ dans Rp tel que :

f (x) ≥ f (x∗ ), ∀x ∈ U ∩ V .

• On dit que x∗ est un maximum local de f sur U s’il existe un voisinage V de

x∗ dans Rp tel que :

15 Pr. Said Kabbadj

Programmation mathématique SMA 5

f (x) ≤ f (x∗ ), ∀x ∈ U ∩ V .

• On dit que x∗ est un point d’extremum global (resp local ) de f sur U, si x∗ est
soit un point de maximum global (resp local) , soit un point de minimum global
(resp local) de f sur U.

Remarque 1.23 Un point d’extremum global est un point d’extremum local.

Théorème 1.24 (Existence) Soit U ⊆ Rp non vide et fermé .

f : U → R continue , on suppose soit :
• U est borné.
• U est non borné et f est coercive sur U .
Alors il existe au moins un point de minimum global de de f sur U .

Preuve.
• Si U est borné on applique le théorème de Weierstrass.

• Si U est non borné . Soit a ∈ U , on pose :

E = {x ∈ U, f (x) ≤ f (a)} = f −1 (] − ∞, f (a)])
E est borné car sinon il existe (xk ) une suite de E tel que kxk k 7−→ +∞
Or f (xk ) ≤ f (a) , ce qui est absurde car f est coercive .

E est compacte et f continue donc f admet un minimum x∗ sur E .

∀x ∈ E, f (x∗ ) ≤ f (x)
et
∀x ∈ (U/E), f (x∗ ) ≤ f (a) < f (x)
Conclusion : ∀x ∈ U on a : f (x∗ ) ≤ f (x).

Théorème 1.25 (Unicité)

Soit U ⊆ Rp convexe et f :U → R strictement convexe , alors il existe au plus un point
de minimum de f sur U .

Preuve On suppose qu’ils existent u1 et u2 tels que :

f (u1 ) = f (u2 ) ≤ f (x), ∀x ∈ U,
alors
f ( 12 u1 + 21 u2 ) < 12 f (u1 ) + 12 f (u2 ) (car f est strictement convexe)
D’où : f ( 21 u1 + 21 u2 ) < f (u1 ) , ce qu’est absurde .

16 Pr. Said Kabbadj

Programmation mathématique SMA 5

1.6 Conditions d’optimalité

Dans cette partie , on suppose que U est un ouvert de Rp

1.6.1 Conditions d’optimalité du premier ordre

Théorème 1.26 ( Condition nécessaire du premier ordre : CN1)

Soit f : U → R une fonction à valeurs réelles . Si la fonction f admet un extremum local

en un point x ∈ U et si elle est différentiable en ce point , alors
∇f (x) = 0
On dit qu’un point est critique de f si ∇f (x) = 0.

Preuve f est différentiable au point x ∈ U, donc il existe un voisinage V de x dans U

tel que :
∀y ∈ V, f (y) = f (x)+ < ∇f (x), (y − x) > +ky − xkε(y − x). (19)
On suppose que f admet un minimum local en x . Il existe donc une boule B(x,r) de
centre x et de rayon r dans V telle que :
∀y ∈ B(x, r) ⊂ V : f (x) ≤ f (y).
Soit h ∈ (Rp )∗ fixé , et soit 0 < t < r
khk
= t0 . x + th ∈ B(x, r), donc en remplaçant y
par x +th dans (19), on aura :
f (x + th) − f (x) =< ∇f (x), th > +kthkε(th) ≥ 0.
Donc
< ∇f (x), h > +khkε(th) ≥ 0.
En faisant tendre t vers 0, on aura :
< ∇f (x), h >≥ 0, ∀h ∈ Rp (20)
En remplaçant h par -h dans (20) , on aura ∇f (x) = 0.

Attention

1) Ce resultat est faux si U n’est pas un ouvert.

2) La réciproque est fausse

Proposition 1.27 : Si U est convexe et f : U → R une fonction convexe dre classe

C 1 . Alors un point x ∈ U est un minimum global de f si et seulement si ∇f (x) = 0

Preuve : Reste à vérifier que si ∇f (x) = 0 alors x est un minimum global de f sur U.
f est convexe sur U, donc

17 Pr. Said Kabbadj

Programmation mathématique SMA 5

f (y) ≥ f (x)+ < ∇f (x), y − x >, ∀x, y ∈ U

∇f (x) = 0 =⇒ f (y) ≥ f (x), ∀y ∈ U

1.6.2 Conditions d’optimalité du second ordre

Théorème 1.28 ( condition nécessaire du second ordre : CN2)

Soit f : U → R une fonction à valeurs réelles. Si f ∈ C 2 (U) et f admet un minimum

local (respectivement maximum local ) en x alors :

∀h ∈ Rp , < ∇2 f (x)h, h >≥ 0 (respectivement) < ∇2 f (x)h, h >≤ 0 )

Autrement dit la matrice ∇2 f (x) est positive (respectivement) négative.

Preuve : On suppose que f admet un minimum local en x . Il existe donc une boule
B(x,r) de centre x et de rayon r telle que :

∀y ∈ B(x, r) ⊂ U : f (x) ≤ f (y). (21)

r
Soit h ∈ (Rp ) fixé , il existe une boule B(x, r) ⊂ U et soit t tel que 0 < t < khk = t0 .
x + th ∈ B(x, r), donc en remplaçant y par x +th dans (21), a par x et h par th dans
(5) on aura :
2
f (x + th) − f (x) = t < ∇f (x), h > + t2 < ∇2 f (x)h, h > +t2 khk2 ε(th) ≥ 0.

∇f (x) = 0 , donc
1
2
< ∇2 f (x)h, h > +khk2 ε(th) ≥ 0

en faisant tendre t vers 0, on aura :

< ∇2 f (x)h, h >≥ 0.

Théorème 1.29 ( condition suffisante du second ordre : CN2)

Soit f : U → R une fonction à valeurs réelles. On suppose que f ∈ C 2 (U) .
Si ∇f (x) = 0 et

∀h ∈ (Rp )∗ , < ∇2 f (x)h, h >> 0,

alors f admet un minimum local strict en x .

Preuve Comme ∇2 f (x) est définie positive alors : il existe α > 0 tel que :

18 Pr. Said Kabbadj

Programmation mathématique SMA 5

< ∇2 f (x)h, h >≥ αkhk2

(α = λmin (∇2 f (x)) la plus petite valeur propre de ∇2 f (x) . On a d’après la formule de
Taylor :

f (x + h) = f (x)+ < ∇f (x), h > + 12 < ∇2 f (x)h, h > +khk2 ε(h)

=⇒ f (x + h) − f (x) ≥ ( α 2
2 − | ε(h) |)(khk )
lim ε(h) = 0. Soit r > 0 , ∀h ∈ B(0, r), | ε(h) |< 21 α . Alors , ∀h ∈ B(0, r) , f (x + h) >
f (x), donc x est bien un minimum strict.

19 Pr. Said Kabbadj