PolycopideRadjefSonia PDF

See discussions, stats, and author profiles for this publication at: https://www.researchgate.
net/publication/343474348
Optimisation : Cours et exercices
Preprint · December 2019
CITATIONS READS
0 7,115
1 author:
Sonia Radjef
Université des Sciences et de la Technologie d'Oran Mohamed Boudiaf
26 PUBLICATIONS 46 CITATIONS
SEE PROFILE
Some of the authors of this publication are also working on these related projects:
Méthodes constructives d’optimisation et applications View project
Contribution à la résolution des problèmes difficiles et réels de divers secteurs par la mise en œuvre de nouvelles techniques et d’approches d’optimisation monocritère et
multicritère et d’apprentissage artificiel. View project
All content following this page was uploaded by Sonia Radjef on 06 August 2020.
The user has requested enhancement of the downloaded file.

République Algérienne Démocratique et Populaire.
Ministère de l’Enseignement Supérieur et de la Recherche
Scientifique.
Université des Sciences et de la Technologie d’Oran.
Mohamed Boudiaf.
Faculté des Mathématiques et Informatique
Département des Mathématiques
Optimisation :
Cours et exercices
Présenté par :
Dr RADJEF Epouse DOUAR Sonia

2019
Table des matières
Introduction Générale 1
I Optimisation sans contraintes 4

1 Concepts et Considérations Théoriques 5
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Vecteurs et matrices . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Matrices et vecteurs partitionnés . . . . . . . . . . . . 6
1.3 Discussion générale sur les solutions d’un système linéaire . . . 7
1.4 Propriétés des formes quadratiques . . . . . . . . . . . . . . . 8
1.4.1 Gradient d’une forme quadratique . . . . . . . . . . . . 9
1.4.2 Forme quadratique définie et semi-définie positive . . . 10
1.4.3 Critère de Sylvester pour les formes quadratiques définies
et semi-définies . . . . . . . . . . . . . . . . . . . . . . 11
1.4.4 Propriétés des matrices définies et semi-définies positives 12
1.5 Éléments d’analyse convexe . . . . . . . . . . . . . . . . . . . 13
1.5.1 Ensembles convexes . . . . . . . . . . . . . . . . . . . . 13
1.5.2 Fonctions convexes . . . . . . . . . . . . . . . . . . . . 15
1.6 Semi-continuité inférieure . . . . . . . . . . . . . . . . . . . . 17
1.7 Sur les polyèdres et les polytopes . . . . . . . . . . . . . . . . 18
1.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 Optimisation non linéaire sans contraintes 22

2.1 Formulation mathématique d’un problème d’optimisation . . . 22
2.2 Minima locaux et globaux . . . . . . . . . . . . . . . . . . . . 24
2.3 Théorèmes généraux d’existence . . . . . . . . . . . . . . . . . 26
2.4 Caractérisation des solutions optimales . . . . . . . . . . . . . 28
1
2
2.4.1 Conditions nécessaires d’optimalité . . . . . . . . . . . 28

2.4.2 Conditions sufffisantes d’optimalité . . . . . . . . . . . 30
2.5 Étude de quelques exemples . . . . . . . . . . . . . . . . . . . 31
2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3 Les méthodes numériques pour l’optimisation sans contraintes 37

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 La méthode du gradient . . . . . . . . . . . . . . . . . . . . . 38
3.2.1 Interprétation physique du gradient . . . . . . . . . . . 38
3.2.2 Sélection des directions de descente . . . . . . . . . . . 39
3.2.3 Sélection du pas . . . . . . . . . . . . . . . . . . . . . . 40
3.3 La méthode de Newton . . . . . . . . . . . . . . . . . . . . . . 44
3.4 La méthode du gradient conjugué . . . . . . . . . . . . . . . . 48
3.4.1 Cas linéaire . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4.2 Cas non linéaire . . . . . . . . . . . . . . . . . . . . . . 51
3.5 La méthode de relaxation . . . . . . . . . . . . . . . . . . . . 52
3.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
II Optimisation avec contraintes 56

4 Optimisation non linéaire avec contraintes 57
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2 Théorèmes généraux d’existence . . . . . . . . . . . . . . . . . 59
4.3 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . 61
4.3.1 Conditions nécessaires d’optimalité dans le cas des contraintes
quelconques . . . . . . . . . . . . . . . . . . . . . . . . 61
4.3.2 Conditions d’optimalité pour le cas de contraintes linéaires
de type égalités . . . . . . . . . . . . . . . . . . . . . . 63
4.3.3 Conditions d’optimalité pour le cas de contraintes linéaires
de type inégalités . . . . . . . . . . . . . . . . . . . . . 72
4.3.4 Conditions d’optimalité pour le cas de contraintes égalités
non linéaires . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.5 Conditions d’optimalité pour le cas de contraintes inégalités
non linéaires . . . . . . . . . . . . . . . . . . . . . . . . 84
4.3.6 Optimisation des fonctions non linéaires sous des contraintes
générales non linéaires . . . . . . . . . . . . . . . . . . 88
4.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3
5 Les méthodes numériques pour l’optimisation avec contraintes

99
5.1 Méthode par élimination . . . . . . . . . . . . . . . . . . . . . 99
5.2 Méthodes de pénalisation . . . . . . . . . . . . . . . . . . . . . 102
5.2.1 Principe de la méthode . . . . . . . . . . . . . . . . . . 102
5.2.2 La méthode de pénalisation dans le cas de contraintes
égalités . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
mixtes . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.2.4 Algorithme de la méthode de pénalisation quadratique 104
5.2.5 Quelques exemples corrigés . . . . . . . . . . . . . . . . 107
5.3 Méthode du gradient projeté . . . . . . . . . . . . . . . . . . . 108
5.4 Méthode Lagrange-Newton pour des contraintes égalité . . . . 110
5.4.1 Cas d’un problème quadratique avec des contraintes
affines égalités . . . . . . . . . . . . . . . . . . . . . . . 110
5.4.2 Cas d’un problème non quadratique . . . . . . . . . . . 111
5.5 Méthode de Newton projetée . . . . . . . . . . . . . . . . . . . 111
5.5.1 Cas de contraintes de type x ≥ 0 . . . . . . . . . . . . 111
5.5.2 Cas de contraintes de bornes . . . . . . . . . . . . . . . 112
5.6 Méthode d’Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Bibliographie 118
Introduction Générale
Euler :”Rien ne se passe dans le monde qui ne soit la signification d’un

certain maximum ou d’un certain minimum.”
L’optimisation (ou programmation mathématique) apparaı̂t comme l’une des
branches des mathématiques les plus adaptées au développement d’outils
pour l’ingénieur. L’optimisation c’est au moins trois choses :
– l’art de formuler des problèmes de décision grâce à des concepts et
outils mathématiques précis ;
– une théorie mathématique ;
– une ”cuisine” algorithmique. Une fois que le mathématicien a sû ca-
ractériser une solution, et d’abord se prononcer sur son existence voire
son unicité, l’ingénieur voudrait pouvoir calculer cette solution.
En 1949, Dantzig a proposé le terme ”programmation linéaire” pour l’étude
des problèmes théoriques et algorithmiques liés à l’optimisation de fonctions
linéaires sous des contraintes linéaires.
Kuhn et Tucker proposent, en 1951, le terme de ”programmation non linéaire”
pour l’étude des problèmes d’optimisation non linéaire avec ou sans contraintes.
La programmation dynamique est employée par R. Bellman en 1957 pour une
méthode générale d’optimisation des systèmes dynamiques, c-à-d, évoluant
au cours du temps.
La programmation en nombres entiers est suggérée par Gomory en 1958 pour
les problèmes d’optimisation où les variables sont astreintes à ne prendre que
des valeurs entières.
Cependant, malgré l’apparente diversité des thèmes abordés en les années
1945 et 1960, la prise de conscience progressive d’une affinité profonde, tant
du point des structures que des méthodes, entre les différentes classes de
problèmes amène rapidement à les intégrer au sein d’une nouvelle discipline
plus vaste, la programmation mathématique, dont le terme apparaı̂t officiel-
lement en 1959 dans un symposium.
1
La programmation mathématique est aujourd’hui une branche particulièrement
active des mathématiques appliquées et il y-a, à cela, de nombreuses raisons.
La première est peut-être le nombre, la variété et l’importance de ses appli-
cations que ce soit dans les sciences de l’ingénieur ou dans d’autres domaines
des mathématiques appliquées. Sans prétendre être exhaustif, on peut citer :
– En recherche opérationnelle : optimisation des systèmes technico-économiques,
planifications, problèmes de transport, d’ordonnancement, de gestion
des stocks, etc . . .
– En analyse numérique : approximation, régression, résolution des systèmes
linéaires et non linéaires, méthodes numériques liées à la mise en oeuvre
des méthodes d’éléments finis, etc . . .
– En automatique : identification des systèmes, commande optimale des
systèmes, filtrage, ordonnancement d’atelier, commande de robots, etc
...
– En ingénierie : dimensionnement et optimisation des structures, concep-
tion optimale des systèmes techniques complexes tels que les systèmes
informatiques, réseaux d’ordinateurs, réseaux de transport,
de télécommunication, etc. . .
– En économie mathématique : résolution de grandes modèles macro-
économiques, modèles d’entreprise, théorie de la décision et théorie des
jeux.
Mais l’importance de la programmation mathématique vient aussi du fait
qu’elle fournit un cadre conceptuel adéquat pour l’analyse et la résolution de
nombreux problèmes des mathématiques appliquées.
Ce polycopié est destiné particulièrement aux étudiants de licence (L3) et de
master en mathématiques.
Il regroupe les deux volets de l’optimisation, à savoir optimisation sans
contraintes et optimisation avec contraintes. C’est un support de cours riche
d’exercices et d’exemples numériques. Il est composé de 5 chapitres répartis
en deux parties, l’une concerne l’optimisation sans contraintes et la seconde
concerne l’optimisation avec contraintes. Dans le premier chapitre, on rap-
pelle brièvement quelques notions mathématiques utiles pour la suite du
cours. Le chapitre 2 et 3 sont consacrés à l’optimisation sans contraintes ; dans
le premier, on présentera les conditions d’optimalité, les conditions d’exis-
tence et d’unicité, dans le cas d’un problème non linéaire sans contraintes.
Puis, on développera les algorithmes les plus utilisés pour résoudre ce type de
problèmes. Quand aux quatrième et cinquième chapitres, ils sont consacrés
à la théorie et aux algorithmes de résolution d’un problèmes non linéaires
2
soumis à des contraintes.
Chaque chapitre est clotûré par un ensemble d’exercices. Les divers exer-
cices accompagnent le document afin d’assimiler les notions plus théoriques
vues en cours. Les solutions de certains de ces exercices feront l’objet d’un
prochain polycopié.
3
Première partie
Optimisation sans contraintes
4
Chapitre 1
Concepts et Considérations
Théoriques
1.1 Introduction
Dans ce chapitre, on donne quelques rappels sur l’algèbre linéaire et la
programmation mathématique. On rappelle tout d’abord les propriétés essen-
tielles des formes quadratiques, ainsi que la notion des ensembles et fonctions
convexes.
1.2 Vecteurs et matrices

Définition 1.2.1. Soit n, m ∈ N∗ . Une matrice d’ordre m × n à coefficients
dans R est un tableau à deux dimensions, ayant m lignes et n colonnes,
représenté sous la forme suivante :
 
a11 a12 · · · a1n
 a21 a22 · · · a2n 
A = A(I, J) = (aij , i ∈ I, j ∈ J) =  ..
 
.. . . .. 
 . . . . 
am1 am2 · · · amn
où I = {1, 2, . . . , m} et J = {1, 2, . . . , n} représentent respectivement l’en-

semble des indices des lignes et des colonnes de A. Pour des calculs pratiques,
5
1.2 Vecteurs et matrices 6
la matrice A se note aussi

 
A1
 A2 
 .. 
.
 
A = (a1 , a2 , · · · , aj , · · · , an ) =  ,
 
 Ai 
 .. 
 . 
Am
 
a1j
 a2j 
où aj = A(I, j) =  ..  est un vecteur colonne de dimension m ;
 
 . 
amj
Ai = A(i, J) = (ai1 , ai2 , · · · , ain ) est un vecteur ligne de dimension n.
Chaque vecteur, noté x = x(J) = (xj , j ∈ J), sera ainsi considéré comme un
vecteur-colonne tandis que le vecteur-ligne sera noté xT . La matrice trans-
posée de A sera notée
AT = AT (J, I) = (aji , j ∈ J, i ∈ I).
Notons qu’un vecteur-colonne de dimension n peut être considéré comme une
matrice d’ordre (n × 1), tandis qu’un vecteur ligne de dimension n peut être
considéré comme une matrice d’ordre (1 × n).
La matrice A est dite carrée si on a m = n ; de plus, si A = AT , la matrice
est dite symétrique.
La matrice identité d’ordre n sera notée In .
1.2.1 Matrices et vecteurs partitionnés

On peut effectuer le produit d’une matrice A et d’un vecteur x, après les
avoir partitionnés judicieusement. On dit alors qu’on a effectué le produit
par blocs. En effet, si l’on a

x1
A = [A1 |A2 ], x = ,
x2
alors on peut écrire :

x1
Ax = [A1 |A2 ] = A 1 x1 + A 2 x2 .
x2
1.3 Discussion générale sur les solutions d’un système linéaire 7
De même pour

A11 A12 x1 b1
A= ,x = ,b = ,
A21 A22 x2 b2
l’équation Ax = b peut alors s’écrire :

A11 x1 + A12 x2 = b1 ,
A21 x1 + A22 x2 = b2 .
On peut partitionner une matrice d’une manière arbitraire. Par exemple, si

A = A(I, J) est une matrice d’ordre (m × n) et que JB et JN sont deux
sous-ensembles quelconques de J, tels que
|JB | = m, JB ∪ JN = J, JB ∩ JN = ∅,
alors on peut partitionner A de la façon suivante :
A = (a1 , a2 , · · · , aj , · · · , an ) = [AB |AN ],
avec AB = A(I,h JBi), AN = A(I, JN ).

Si x = x(J) = xxNB , xB = x(JB ), xN = x(JN ), alors on peut écrire
n
X X X
Ax = aj x j = aj x j + aj x j
j=1 j∈JB j∈JN
= A(I, JB )x(JB ) + A(I, JN )x(JN )
= A B xB + A N xN .
1.3 Discussion générale sur les solutions d’un

système linéaire
Soient m et n deux nombres entiers. Un système de m équations linéaires
à n inconnues x1 , x2 , · · · , xn s’écrit comme suit :

 a11 x1 + a12 x2 + · · · + a1n xn = b1 ,

 a21 x1 + a22 x2 + · · · + a2n xn = b2 ,

.. .. . .. . (1.1)


 . + . + .. + . = ..
 a x + a x + ··· + a x = b .
m1 1 m2 2 mn n m
1.4 Propriétés des formes quadratiques 8
où les coefficients aij sont des réels. Les nombres b1 , b2 , · · · , bm sont appelés
les membres libres du système (1.1) ou les seconds membres. En posant
   
x1 b1
 x2   b2 
A = (aij , 1 ≤ i ≤ m, 1 ≤ j ≤ n), x =  ..  , b =  ..  ,
   
 .   . 
xn bm
Le système (1.1) peut s’écrire sous la forme matricielle suivante :
Ax = b. (1.2)
Tout vecteur x vérifiant les équations (1.1) s’appelle solution du système. Le

système (1.1) est dit compatible s’il possède une ou plusieurs solutions. Dans
le cas contraire, il est dit incompatible ou impossible. Lorsque le vecteur b
est nul, le système (1.2) est dit homogène. Tout système homogène possède
la solution triviale x = 0.
Définition 1.3.1. Le système linéaire (1.2) est dit de rang complet en lignes
si rang(A) = m, m ≤ n, et de rang complet en colonnes si rang(A) =
n, m ≥ n.
Lemme 1.3.1. Soit m ≤ n et rang(A) = m. Alors le système Ax = b admet

toujours des solutions, quelque soit le second membre b :
a) une et une seule solution si m = n,
b) une infinité de solutions si m < n.
1.4 Propriétés des formes quadratiques

Définition 1.4.1. Une fonction F : Rn −→ R, est dite forme quadratique
de n variables x1 , x2 , · · · , xn si elle s’écrit sous la forme suivante :
n X
X n
F (x) = aij xi xj = xT Ax (1.3)
i=1 j=1
où xT = (x1 , x2 , · · · , xn ) est un n-vecteur ligne et A = (aij , 1 ≤ i, j ≤ n) est

une matrice carrée d’ordre n.
Pour i 6= j, le coefficient du terme xi xj s’écrit aij + aji . En vertu de

cela, la matrice A peut être supposée symétrique. En effet, en définissant de
nouveaux coefficients
dij = dji , 1 ≤ i, j ≤ n.
On obtient une nouvelle matrice D symétrique telle que
aij + aji
D = (dij , 1 ≤ i, j ≤ n), avec dij = dji = .
2
Il est clair qu’après une redéfinition des coefficients, la valeur de la forme
quadratique F (x) reste inchangée pour tout point x ∈ Rn :
F (x) = xT Ax = xT Dx.
Pour cela, il est naturel de considérer que la matrice d’une forme quadratique
est toujours symétrique.
1.4.1 Gradient d’une forme quadratique

Définition 1.4.2. Soit F : Rn −→ R une fonction réelle continûment
différentiable. Son gradient au point x est défini par :
 ∂F 
∂x1
(x)
 ∂F (x) 
 ∂x2
∇F (x) =  (1.4)

.. 
 . 
∂F
∂xn
(x)
Soit F une forme quadratique et D sa matrice symétrique associée :
F (x) = xT Dx. (1.5)
En écrivant la matrice D sous forme de vecteurs colonnes
D = (d1 , d2 , · · · , dn ),
l’expression (1.5) peut se mettre sous la forme suivante :
 T 
d1 x
 dT2 x 
 .  n
 .  X
 . 
F (x) = (x1 , x2 , · · · , xj , · · · , xn )  T  = xj dTj x.
d
 j  x
 .  j=1
 .. 
dTn x
La dérivée partielle de F par rapport à chaque variable xj est donnée par :

∂F
(x) = x1 d1j + · · · + xj−1 d(j−1)(j) + dTj x + xj djj + · · · + xn dnj
∂xj
= x1 d1j + · · · + xj−1 d(j−1)(j) + xj djj + · · · + xn dnj + dTj x
= 2dTj x
Par conséquent, le gradient de F (x) est :
∇F (x) = 2Dx. (1.6)
Définition 1.4.3. Soit une fonction réelle de classe C 2 , F : Rn −→ R. Le

Hessien de la fonction F est défini par :

2 ∂F ∂F ∂F ∂F
∇ F (x) = ∇ ∂x1 (x), ∇ ∂x2 (x), · · · , ∇ ∂xj (x), · · · , ∇ ∂xn (x)
 ∂2F ∂2F ∂2F 

∂ 2 x1
(x) ∂x1 ∂x2
(x) ··· ∂x1 ∂xn
(x)
∂2F ∂2F ∂2F . (1.7)

∂x2 ∂x1
(x) ∂ 2 x2
(x) ··· ∂x2 ∂xn
(x) 
=
 
 .. .. .. .. 
 . . . . 
∂2F ∂2F ∂2F
∂xn ∂x1
(x) ∂xn ∂x2
(x) ··· ∂ 2 xn
(x)
Définition 1.4.4. Soit F : Rn −→ R une fonction de classe C 1 . La dérivée

directionnelle de F dans la direction d au point x est :
0 F (x + td) − F (x)
F (x; d) = lim+
t→0 t
∂F ∂F
= (x + td)|t=0 d1 + · · · + (x + td)|t=0 dn
∂x1 ∂xn
= (∇F (x))T d.
1.4.2 Forme quadratique définie et semi-définie posi-

tive
Soit F (x) = xT Dx une forme quadratique avec D symétrique.
Définition 1.4.5. F est dite définie positive si xT Dx > 0, ∀x ∈ Rn et x 6= 0.
elle est dite semi-définie positive ou définie non négative si xT Dx ≥ 0, ∀x ∈
Rn .
Définition 1.4.6. F est dite définie négative si xT Dx < 0, ∀x ∈ Rn et x 6= 0.

Elle est dite semi-définie négative ou définie non positive si xT Dx ≤ 0, ∀x ∈
Rn .
Définition 1.4.7. Une matrice symétrique D est dite matrice définie positive
(respectivement non négative) et on note D 0 (respectivement D 0)
si elle est associée à une forme quadratique définie positive (respectivement
non négative).
1.4.3 Critère de Sylvester pour les formes quadratiques

définies et semi-définies
L’intérêt du critère du Sylvester est de caractériser une forme quadra-
tique définie ou semi-définie. Pour cela, considérons la matrice symétrique
suivante :  
d11 d12 · · · d1n
 d21 d22 · · · d2n 
D =  ..
 
.. .. 
 . . . 
dn1 dn2 · · · dnn
Le mineur de la matrice D, formé des lignes i1 , i2 , · · · , ip et les colonnes
j1 , j2 , · · · , jp , sera noté comme suit :

di j di j · · · di j
1 p
1 1 1 2
d d · · · d

i1 i2 · · · ip i j i j i

2 1 2 2 2 jp
D = .. .. .

j1 j2 · · · jp ..
. . .

dip j1 dip j2 · · · dip jp
Ce mineur est dit principal si : i1 = j1 , i2 = j2 , · · · , ip = jp , c’est-à-dire s’il

est formé des lignes et des colonnes portant les mêmes numéros.
Les mineurs suivants :

d11 d12 · · · d1n

d11 d12 d21 d22 · · · d2n
D1 = d11 , D2 = , · · · , Dn = . .. .. ,

d21 d22 .. . .

dn1 dn2 · · · dnn
sont appelés mineurs principaux sucessifs. Alors, le critère de Sylvester se

formule comme suit :
Théorème 1.4.1 (Critère de sylvester). (i) Pour que la matrice D soit

définie positive (D 0), il est nécessaire et suffisant que tous ses mi-
neurs principaux successifs soient positifs :
D1 > 0, D2 > 0, · · · , Dn > 0; (1.8)
(ii) Pour que la matrice D soit semi-définie positive (D 0), il est

nécessaire et suffisant que tous ses mineurs principaux soient non négatifs :

i1 , i2 , · · · , ip
D ≥ 0, 1 ≤ i1 < i2 < · · · < ip ≤ n, p = 1, 2, · · · , n.
i1 , i2 , · · · , ip
(1.9)
Remarque 1.4.1. Pour qu’une matrice D soit définie négative (D ≺ 0) ou non

positive (D 0), les conditions (1.8) et (1.9) se reformulent ainsi :
(i) D ≺ 0 ⇔ (−1)p Dp > 0, p = 1, 2, · · · , n.
i ,
1 2 i , · · · , ip
(ii) D 0 ⇔ (−1)p D ≥ 0, 1 ≤ i1 < i2 < · · · < ip ≤
i1 , i2 , · · · , ip
n, p = 1, 2, · · · , n.
Remarque 1.4.2. Le critère de Sylvester n’est valable que pour les matrices
symétriques.
1.4.4 Propriétés des matrices définies et semi-définies

positives
Les matrices symétriques définies ont des propriétés très intéressantes. En
voici quelques unes :
Propriété 1.4.1. Soit la matrice D partitionnée de la manière suivante :
m k
D= D11 D21 m , m + k = n.
D21 D22 k
Si D > 0 (D ≥ 0), alors les sous-matrices principales D11 et D22 sont définies
positives (non négatives). D’une manière générale, toute sous-matrice prin-
cipale d’une matrice définie positive (non négative) est aussi définie positive
(non négative).
1.5 Éléments d’analyse convexe 13
Propriété 1.4.2. Un élément de la diagonale d’une matrice symétrique D

définie non négative ne peut s’annuler que si les autres éléments de la même
ligne et colonne s’annulent aussi.
Propriété 1.4.3. Soit D une matrice symétrique définie non-négative. Si
x ∈ Rn est un point quelconque fixe tel que xT Dx = 0, alors on aura Dx = 0.
1.5 Éléments d’analyse convexe

Dans les problèmes d’optimisation, avec ou sans contraintes, une notion va
jouer un rôle très important : celle de convexité. En effet, pour la plupart des
algorithmes, la convergence vers un optimum global ne pourra être démontrée
qu’avec des hypothèses de convexité.
1.5.1 Ensembles convexes

Définition 1.5.1. Un ensemble S ⊂ Rn est dit convexe si et seulement si :
∀x, y ∈ S, ∀λ ∈ [0, 1], on a λx + (1 − λ)y ∈ S. (1.10)
Cette définition peut s’interpréter en disant que S est convexe si et seule-
ment si pour deux points quelconques x et y pris dans S, le segment [x, y]
tout entier est contenu dans S.
Définition 1.5.2. Soit S = {p1 , p2 , . . . , pk } un ensemble de k points de Rn .
• Un point p ∈ Rn peut être obtenu par :
– Combinaison linéaire des points de S si
k
X
p= λi pi , λi ∈ R, i = 1, k.
i=1
– Combinaison affine des points de S si

k
X k
X
p= λi pi , λi = 0.
i=1 i=1
– Combinaison conique des points de S si

k
X
p= λi pi , λi ≥ 0 pour i = 1, k.
i=1
– Combinaison convexe des points de S si

k
X k
X
p= λi pi , λi = 1, λi ≥ 0, i = 1, k.
i=1 i=1
• On définit l’enveloppe conique (respectivement convexe) des points de

S comme l’ensemble des points de Rn pouvant être obtenus par com-
binaison conique (respectivement convexe) des points de S.
• L’espace affine (respectivement espace vectoriel) engendré par les points
de S est l’ensemble des points de Rn pouvant être obtenus par combi-
naison affine (respectivement linéaire) des points de S.
• Les points de S sont dits affinement indépendants (respectivement
linéairement indépendants) si aucun des points de S ne peut être ob-
tenu par une combinaison affine (respectivement linéaire) des autres
points de S.
Propriété 1.5.1. Un ensemble S de points de Rn est convexe si et seulement
si toute combinaison convexe de points de S est encore un point de S.
Exemple 1.5.1. L’ensemble S = {x ∈ Rn , x = x0 + αd, α ≥ 0} est convexe,
où d ∈ Rn est un vecteur non nul, et x0 ∈ Rn est un point fixe.
En effet, pour tout x1 , x2 ∈ S et pour tout λ ∈ [0, 1], on a
x1 = x0 + α1 d, x2 = x0 + α2 d,
où α1 , α2 ∈ R+ . Donc
λx1 + (1 − λ)x2 = λ(x0 + α1 d) + (1 − λ)(x0 + α2 d)

= x0 + [λα1 + (1 − λ)α2 ]d.
Comme λα1 + (1 − λ)α2 ≥ 0, alors λx1 + (1 − λ)x2 ∈ S.

Théorème 1.5.1. Soient S1 et S2 deux ensembles convexes de Rn . Alors
1. S1 ∩ S2 est convexe ;
2. S1 ± S2 = {x1 ± x2 | x1 ∈ S1 , x2 ∈ S2 } est convexe.
Théorème 1.5.2. Soit S ⊂ Rn un ensemble convexe. Alors
1. l’intérieur de S, noté IntS, est un ensemble convexe ;
2. la clôture S de S est un ensemble convexe.
1.5.2 Fonctions convexes

Définition 1.5.3. On dit qu’une fonction f : S ⊂ Rn −→ R, définie sur un
ensemble convexe S, est convexe, si elle vérifie :
∀x ∈ S, ∀y ∈ S, ∀λ ∈ [0, 1] , on a : f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y).
Une fonction f est dite strictement convexe si l’inégalité ci-dessus est stricte
pour x 6= y et λ ∈ ]0, 1[.
Une fonction f est dite concave si (−f ) est convexe.
L’interprétation géométrique de cette définition est que le graphe d’une
fonction convexe est toujours en dessous du segment reliant les points (x, f (x))
et (y, f (y)).
Exemple 1.5.2. Un des exemples basiques de fonctions convexes est la fonction
indicatrice. Soit S ⊂ Rn un sous-ensemble non vide ; la fonction indicatrice
IS : Rn → R ∪ {+∞} est définie par

0, si x ∈ S,
IS (x) =
+∞, ailleurs.
La fonction indicatrice IS est convexe si et seulement si S est convexe.
Exemple 1.5.3. On définit la fonction distance :
dS (x) = inf {ky − xk | y ∈ S},
où S ⊂ Rn est un ensemble convexe non vide et k.k est une norme quelconque
dans Rn . Alors dS est une fonction convexe.
Une fonction convexe peut aussi être décrite par son épigraphe.
Définition 1.5.4. Soit S ⊂ Rn un ensemble non vide et f : S → R. L’en-

semble
{(x, f (x)) : x ∈ S} ⊂ Rn+1
décrivant la fonction f est appelé le graphe de la fonction f .
Définition 1.5.5. Soit S ⊂ Rn un ensemble non vide. Soit f : S ⊂ Rn → R.
L’épigraphe de f , noté epif , est un sous-ensemble de Rn+1 défini par
epif = {(x, α)|f (x) ≤ α, x ∈ S, α ∈ R}.
L’hypographe de f , noté hypf , est un sous-ensemble de Rn+1 défini par
hypf = {(x, α)|f (x) ≥ α, x ∈ S, α ∈ R}.
Les théorèmes suivants indiquent la relation entre une fonction convexe

et la convexité de epif .
Théorème 1.5.3. Soient S ⊂ Rn un ensemble convexe non vide et f : S ⊂

Rn → R. Alors, f est convexe si et seulement si epif est un ensemble convexe.
Démonstration. Supposons que f est convexe. Soient x1 , x2 ∈ S et (x1 , α1 ), (x2 , α2 ) ∈

epif . D’après les définitions de la fonction convexe et de l’épiraphe, il s’ensuit
f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ) ≤ λα1 + (1 − λ)α2
pour tout λ ∈ [0, 1]. Comme S est un ensemble convexe, λx1 + (1 − λ)x2 ∈ S.
D’où
(λx1 + (1 − λ)x2 , λα1 + (1 − λ)α2 ) ∈ epif,
ce qui implique que epif est convexe.
Supposons, maintenant, que epif est convexe, et soient x1 , x2 ∈ S. On a
(x1 , f (x1 )), (x2 , f (x2 )) ∈ epif . D’après la convexité de epif , on a
(λx1 + (1 − λ)x2 , λf (x1 ) + (1 − λ)f (x2 )) ∈ epif, pour λ ∈ [0, 1].
Donc
f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 )
pour tout λ ∈ [0, 1]. D’où f est convexe.
Théorème 1.5.4. 1. Soient f une fonction convexe sur un ensemble convexe

n
S ⊂ R et un nombre réel α ≥ 0. Alors αf est aussi une fonction
convexe sur S.
2. Soient f1 , f2 deux fonctions convexes sur un ensemble convexe S. Alors
f1 + f2 est aussi une fonction convexe sur S.
3. Soient f1 , f2 , . . . , fm des fonctions convexes sur P
un ensemble convexe S
et α1 , α2 , . . . , αm ≥ 0, des nombres réels. Alors m i=1 αi fi est aussi une
fonction convexe sur S.
Dans le cas où f : S ⊂ R → R, on a le résultat suivant :
Propriété 1.5.2. Si f : S → R est deux fois continûment dérivable sur S

convexe, alors f est convexe si et seulement si f 00 (x) ≥ 0, ∀x ∈ S. Elle est
strictement convexe si f 00 (x) > 0, ∀x ∈ S.
1.6 Semi-continuité inférieure 17
Théorème 1.5.5. Soit f : Rn → R. Si f est continûment différentiable, les

conditions a) et b) ci-dessous sont équivalentes ;
Si f est deux fois continûment différentiable, les conditions a), b) et c) ci-
dessous sont équivalentes :
a) f est convexe ;
b) ∀x, ∀y : f (y) ≥ f (x) + ∇f T (x)(y − x) ;
c) ∀x, le hessien ∇2 f (x) est une matrice semi-définie positive (y T ∇2 f (x)y ≥
0, ∀y ∈ Rn ).
Corollaire 1.5.1. Soit f une forme quadratique définie par

1
f (x) = xT Ax − bT x.
2
Alors f est convexe si et seulement si A 0, et strictement convexe si et
seulement si A 0.
Cela provient du fait que ∇2 f (x) = A.
Définition 1.5.6. On dit qu’un problème de programmation mathématique

est convexe s’il consiste à minimiser une fonction convexe (respectivement
maximiser une fonction concave) sur un domaine convexe.
1.6 Semi-continuité inférieure

De façon générale, une fonction convexe peut être très compliquée sur le
bord de son domaine. Par exemple, la fonction

0 si x2 + y 2 < 1,
f (x, y) = (1.11)
φ(x, y) si x2 + y 2 = 1, avec φ(x, y) ≥ 0
est convexe. Cependant, son comportement sur le bord peut être arbitraire-
ment complexe. Minimiser de telles fonctions est en général impossible. Cette
remarque nous mène à nous restreindre à la classe de fonctions semi-continues
inférieurement.
Définition 1.6.1. Un ensemble S ⊂ Rn est compact si et seulement s’il est

fermé et borné.
1.7 Sur les polyèdres et les polytopes 18
Définition 1.6.2 (Fonction semi-continue inférieurement). Une fonction f :

Rn → R ∪ {+∞} est dite fermée ou semi-continue inférieurement si :
∀x ∈ Rn , ∀xn −→ x, lim inf f (xn ) ≥ f (x).

n→+∞
Proposition 1.6.1. Soit f : Rn → R ∪ {+∞}. Les propositions suivantes

sont équivalentes :
i) f est semi-continue inférieurement.
ii) Quel que soit α ∈ R, l’ensemble de niveau {x ∈ Rn |f (x) ≤ α} est
fermé.
iii) epi(f ) est un ensemble fermé.
Définition 1.6.3. La fonction f : Rn → R est coercive si et seulement si
lim f (x) = +∞.

kxk→+∞
1.7 Sur les polyèdres et les polytopes

On note par S l’ensemble suivant :
S = {x ∈ Rn |Ax ≤ b} ,
où b est un vecteur de Rm et A une matrice à m lignes et n colonnes, m et

n étant des nombres finis.
On a


 a11 x1 + a12 x2 + · · · + a1n xn ≤ b1 ,
 a21 x1 + a22 x2 + · · · + a2n xn ≤ b2 ,

Ax ≤ b ⇔ .. .. . .. .


 . + . + .. + . ≤ ..
 a x + a x + ··· + a x ≤ b .
m1 1 m2 2 mn n m
Définition 1.7.1. L’ensemble S obtenu par l’intersection d’un nombre fini

de demi-espaces de Rn (chacun de ces demi-espaces correspondant à une
des lignes du système matriciel Ax ≤ b), constitue ce que l’on nomme un
polyèdre.
Définition 1.7.2. Un polyèdre borné, i.e. un polyèdre pour lequel il existe
un nombre B tel que chaque point du polyèdre a des coordonnées comprises
entre −B et B, est un polytope.
1.7 Sur les polyèdres et les polytopes 19
Théorème 1.7.1. Un polyèdre est un ensemble convexe.

Définition 1.7.3. Le polyèdre S est de dimension k, noté dim(S) = k, si le
nombre de points de S affinement indépendants est (k + 1). Le polyèdre S a
pleine dimension si dim(S) = n.
Définition 1.7.4. Un point x d’un polyèdre S est un point extrême de S si,
dans toute expression de x comme combinaison convexe de deux points x1
et x2 de S, on a forcément x1 = x2 = x.
Définition 1.7.5. Soit S = {x ∈ Rn |Ax ≤ b} un polyèdre dans Rn .
• Une inéquation aT x ≤ a0 est une inéquation valide pour S si elle est
vérifiée par chacun des points de S.
Si aT x ≤ a0 est une inéquation valide pour
S, elle définit une face F
de S, avec F := x ∈ Rn |x ∈ S, aT x = a0 .
• Une face F de S est une face propre de S si F 6= ∅ et F 6= S.
• Une face F d’un polyèdre S est une facette de S si dim(F ) = dim(S)−1.
Théorème 1.7.2. Un point x est un point extrême d’un polyèdre S si et
seulement si x est une face de dimension 0 de S.
Une autre manière d’énoncer le théorème 1.7.2 est :
Un point x0 est un point extrême d’un polyèdre S si et seulement s’il existe
un vecteur c tel que x0 est l’unique solution optimale du problème suivant :
cT x −→ max, x ∈ S.
Théorème 1.7.3. Un polyèdre a un nombre fini de faces.

Définition 1.7.6. Un ensemble convexe C de points de Rn est un cône si
x ∈ C implique (λx) ∈ C pour tout λ ≥ 0.
Un cône est pointé s’il possède un point extrême.
Définition 1.7.7. Le cône de récession du polyèdre S est le polyèdre S0 =
{x ∈ Rn |Ax ≤ 0}.
Propriété 1.7.1. Si S est un polytope, alors S0 ne contient que le point 0,
i.e. rang(A) = n.
Définition 1.7.8. Si S n’est pas vide, alors r ∈ S0 \ {0} est un rayon de S.
Un rayon r de S est un rayon extrême de S s’il n’existe pas deux rayons de
S, r1 et r2 , tels que r1 6= λr2 pour tout λ ≥ 0, avec r = 21 r1 + 12 r2 .
1.8 Exercices 20
Une autre manière de caractériser les rayons extrêmes d’un polyèdre est
donnée par le théorème suivant :
Théorème 1.7.4. Soit S = {x ∈ Rn |Ax ≤ b} un polyèdre dans Rn . Si S

n’est pas vide, le vecteur r est un rayon extrême de S si et seulement si
{λr|λ ∈ R, λ ≥ 0} est une face de dimension 1 de S0 .
Corollaire 1.7.1. L’ensemble (polytope ou polyèdre) convexe :
S = {x ∈ Rn |Ax ≤ b}
a un nombre fini τ (S) de points extrêmes et τ (S) ≤ Cnm .
Corollaire 1.7.2. Tout point d’un polytope S ⊂ Rn est combinaison convexe

des points extrêmes de S.
Corollaire 1.7.3. Tout point d’un polyèdre S ⊂ Rn est combinaison convexe

des points extrêmes de S, à laquelle s’ajoute éventuellement une combinaison
linéaire, à coefficients positifs, de rayons extrêmaux.
1.8 Exercices
Exercice 1.8.1. Soit A ∈ Mn (R) telle que AT A = AAT . On suppose qu’il
existe p ∈ N tel que Ap = 0.
a) Montrer que AT A = 0.
b) En déduire que A = 0.
Exercice 1.8.2. Soit A ∈ Mn (R). Montrer que la matrice AT A est diagonali-
sable à valeurs propres positives.
Exercice 1.8.3. – Soit A une matrice carrée réelle d’ordre n et S = AT A.
Montrer que S est symétrique semi-définie positive.
– Réciproquement, montrer que pour toute matrice S symétrique posi-
tive, il existe une matrice A carrée réelle de format n telle que S = AT A.
A t-on l’unicité de A ?
– Montrer que S est définie positive si et seulement si A est inversible.
– Montrer que rang(A) = rang(S).
Exercice 1.8.4. 1. Soit A ∈ Rm×n et b ∈ Rm . Utiliser la définition de la
convexité pour montrer que l’ensemble S = {x ∈ Rn : Ax ≥ b} est un
ensemble convexe.
1.8 Exercices 21
2. Pour chacune des propositions suivantes, dire si elle est juste ou fausse :
– L’ensemble S ⊂ Rn est dit fermé quand tout point de S est un point
frontière.
– Si S ⊂ Rn est ouvert alors S est convexe.
Exercice 1.8.5. Etudier la convexité des fonctions suivantes :
1. f1 (X1 , X2 ) = 10X1 + 10X2 + 100 − X12 − 2X1 X2 − X22
2. f2 (X1 , X2 ) = X12 + 2X1 X2 + 100X1 + 100X2
3. f3 (X1 , X2 ) = X1 eX1 +X2 , X1 , X2 ≥ 0.
4. f (X1 , X2 , X3 ) = 3X12 + 2X22 + X32 − 2X1 X2 − 2X1 X3 + 2X2 X3 − 6X1 −
4X2 − 2X3
Exercice 1.8.6. Etudier la nature des formes quadratiques suivantes :
1. z = X12 + X22 ;
2. z = (X1 + X2 )2 ;
3. z = X12 − X22 .
Exercice 1.8.7. Calculer la jacobienne de la fonction f définie de R2 dans R3
et pour tout (x, y) de R2 , on a :
f (x, y) = (ex + y 3 , y, 3 cosh x + sinh y)T .
Exercice 1.8.8. Montrer que la fonction suivante est convexe :
f (x) = 3x21 + 2x22 + x23 − 2x1 x2 − 2x1 x3 + 2x2 x3 − 6x1 − 4x2 − 2x3 .
Exercice 1.8.9. Calculer le gradient et le hessien de la fonction de Rosen-

brock :
f (x) = 100(x2 − x21 )2 + (1 − x1 )2 .
Chapitre 2
Optimisation non linéaire sans

contraintes
2.1 Formulation mathématique d’un problème

d’optimisation
Il existe différents problèmes d’optimisation. Certaines caractéristiques
permettent de les distinguer : comportent-ils des contraintes ? les fonctions
objectifs sont-elles linéaires ? sont-elles quadratiques ? sont-elles convexes ? les
domaines de définition des fonctions sont-ils continus ou discrets ? le problème
contient-il une seule ou plusieurs fonctions objectifs ? Tous ces problèmes
possèdent des structures différentes et ne peuvent être traités de la même
façon.
Un problème d’optimisation continue se présente habituellement sous la forme
suivante :
f (x) −→ min,
(2.1)
x ∈ S.
Définition 2.1.1. Le vecteur x = (x1 , . . . , xn ) est appelé vecteur des va-

riables de décision du problème ; la fonction f : Rn → R est la fonction ob-
jectif ; S est généralement défini par une collection de contraintes exprimées
sous forme d’égalités et d’inégalités, du genre S = {x ∈ Rn , g(x) ≤ 0}, où
g = (g1 , · · · , gm )T est une fonction de Rn dans Rm .
Définition 2.1.2. Un vecteur x0 est dit solution optimale du problème (2.1)

si pour tous les vecteurs x ∈ S, on a f (x) ≥ f (x0 ).
22
2.1 Formulation mathématique d’un problème d’optimisation 23
Définition 2.1.3. Le problème d’optimisation (2.1) est dit programme linéaire

si les fonctions f, g1 , . . . , gm sont linéaires, i.e., elles vérifient
f (αx + βy) = αf (x) + βf (y),
gi (αx + βy) = αgi (x) + βgi (y), i = 1, m,
pour tous x, y ∈ Rn et tous α, β ∈ R.
Ici, on a
S = {x ∈ Rn , gi (x) ≤ 0, i = 1, . . . , m}.
Si l’une au moins de ces fonctions n’est pas linéaire, le problème est dit
programme non-linéaire.
Définition 2.1.4. Le problème d’optimisation (2.1) est dit convexe si la fonc-
tion objectif f et les contraintes g1 . . . , gm sont convexes, i.e., elles vérifient
f (αx + βy) ≤ αf (x) + βf (y),
gi (αx + βy) ≤ αgi (x) + βgi (y), i = 1, m,
pour tous x, y ∈ Rn et tous α, β ∈ R, avec α + β = 1, α ≥ 0, β ≥ 0.
Conséquence 2.1.1. Un programme linéaire est alors un programme d’op-
timisation convexe.
On peut considérer l’optimisation convexe comme une généralisation de la
programmation linéaire.
Dans ce chapitre, nous allons étudier le problème de minimisation d’une
fonction non linéaire f : Rn → R, qu’on notera
min f (x). (2.2)
x∈Rn
Exemple 2.1.1. On voudrait installer une antenne pour connecter 4 clients

importants. Cette antenne doit se trouver au plus proche de chaque client,
en donnant priorité aux meilleurs clients.
Pour chaque client, on connait :
– sa localisation : les coordonnées (x, y) ;
– le nombre d’heures de communication par mois.
Le problème consiste à trouver (x, y) tel que
p p
min 200 (xp − 5)2 + (y − 10)2 + 150 2
p (x − 10) + (y − 5)
2
+200 x2 + (y − 10)2 + 300 (x − 12)2 + y 2

2.2 Minima locaux et globaux 24
Figure 2.1 – Exemple
2.2 Minima locaux et globaux

Les minima locaux et globaux de f sur Rn sont définis de la manière
suivante :
Définition 2.2.1. Un vecteur x0 ∈ Rn est un minimum local de f sur Rn si
∃ > 0 tel que f (x0 ) ≤ f (x), ∀x ∈ Rn , avec kx − x0 k < .
Définition 2.2.2. Un vecteur x0 ∈ Rn est un minimum global de f sur Rn

si
f (x0 ) ≤ f (x), ∀x ∈ Rn .
Remarque 2.2.1. Les maxima locaux et globaux sont définis de manière si-
milaire. Notons que x0 est un maximum local (respectivement global) de la
fonction f sur l’ensemble Rn si x0 est un minimum local (respectivement
global) de la fonction (−f ) sur Rn .
2.2 Minima locaux et globaux 25
Il découle de cette observation que tout problème de maximisation peut

être réduit immédiatement à un problème de minimisation (et inversement)
en multipliant la fonction objectif par -1.
Remarque 2.2.2. Le problème (2.2) peut ne pas admettre de solutions opti-
males, comme dans la figure suivante :
Remarque 2.2.3. Le problème (2.2) peut aussi admettre une infinité de solu-
tions optimales, comme dans la figure suivante :
2.3 Théorèmes généraux d’existence 26
Remarque 2.2.4. Dans le cas d’une fonction objectif convexe, il n’y a pas de
distinction entre minimum local et global : tout minimum local est également
global, comme l’établit le théorème suivant :
Théorème 2.2.1. Soit f : S ⊆ Rn → R une fonction convexe définie sur un
ensemble convexe S. Alors, tout minimum local est également un minimum
global. Si f est strictement convexe, alors il existe au plus un minimum global
de f .
2.3 Théorèmes généraux d’existence

Théorème 2.3.1 (Weierstrass). Soit S ⊂ Rn un ensemble non vide. Si
f : S ⊂ Rn → R une fonction semi-continue inférieurement sur S compact
(fermé et borné), alors il existe x0 ∈ S tel que
minf (x) = f (x0 ).
x∈S
Théorème 2.3.2. Si f : S ⊂ Rn → R une fonction continue sur Rn . Si f

est coercive, i.e.,
lim f (x) = +∞,
kxk→∞
alors le problème (2.2) admet une solution optimale x0 ∈ Rn .

L’unicité résulte en général des propriétés de convexité de f .
Avant de prouver les théorèmes 2.3.1 et 2.3.2, considérons les résultats sui-
vants sur les fonctions coercives.
Proposition 2.3.1. Soit S un sous ensemble fermé de Rn . Si f : S ⊂ Rn →
R est semi-continue inférieurement sur S alors ∀c ∈ R, l’ensemble
S(c) = {x ∈ S/f (x) ≤ c}
est fermé.

Démonstration. Soit c ∈ R et supposons que S(c) 6= ∅. Soit xk ⊂ S(c) une
suite de S(c) convergeant vers x.
Comme S est fermé, alors x ∈ S.
D’autre part, comme f est semi-continue inférieurement, alors de f (xk ) ≤ c,
on déduit
f (x) ≤ lim inf f (xk ) ≤ c.
k→+∞
D’où x ∈ S(c) et S(c) est fermé.

Proposition 2.3.2. Soit S un sous ensemble fermé de Rn . Si f : S ⊂ Rn →

R est semi-continue inférieurement et coercive, alors ∀c ∈ R, l’ensemble
S(c) = {x ∈ S/f (x) ≤ c}
est fermé et borné (compact).
Démonstration. L’ensemble S(c) est fermé d’après la proposition 2.3.1. Démontrons

que S(c) est borné. Supposons le contraire : il existe alors une suite {xk } ⊂
S(c) de S(c) telle que
lim kxk k = +∞.
k→∞
Comme f est coercive, alors
lim f (xk ) = +∞.

k→∞
Or
xk ∈ S(c) ⇒ f (xk ) ≤ c, ∀k.
D’où
+∞ = lim f (xk ) ≤ c < +∞.
k→∞
Ce qui nous amène à une contradiction.

Démonstration du théorème 2.3.1. On suppose que S 6= ∅. Soit {xk } ⊂ S
une suite minimisante telle que
lim f (xk ) = inf f (x).

k→∞ x∈S
0
Comme S est borné, on peut extraire une sous-suite xk convergeant vers
x∗ .
Comme S est fermé, alors x∗ ∈ S. Par ailleurs, f est semi-continue inférieurement,
alors
f (x∗ ) ≤ lim
0
f (xk0 ) = lim f (xk ) = inf f (x).
k →∞ k→∞ x∈S
D’où
f (x∗ ) = inf f (x).
x∈S
2.4 Caractérisation des solutions optimales 28
Démonstration du théorème 2.3.2. Soit c ∈ R et considérons l’ensemble
S(c) = {x ∈ S/f (x) ≤ c} .
f étant coercive et semi-continue inférieurement, alors d’après la proposition

2.3.2, l’ensemble S(c) est compact.
D’après le théorème 2.3.1, il existe x∗ ∈ S(c) tel que
f (x∗ ) = inf f (x) = inf f (x).

x∈S(c) x∈S
Corollaire 2.3.1. Soit f : Rn → R une fonction semi-continue inférieurement

sur Rn et coercive. Alors le problème
min f (x)
x∈Rn
a une solution optimale x∗ .

Démonstration. Soit x0 ∈ Rn quelconque. En supposant que la fonction f
est coercive, il existe une constante M > 0 telle que
∀x ∈ Rn : kxk ≥ M ⇒ f (x) ≥ f (x0 ).
Le problème se ramène donc à un problème d’optimisation sur la boule com-

pacte S = {x ∈ Rn : kxk ≤ M } qui est non vide et le théorème 2.3.1 s’ap-
plique.
Pour beaucoup de problèmes d’optimisation sans contraintes, les princi-
pales méthodes de résolution connues ne permettent pas la détermination
d’un minimum global, on se contente d’optimums locaux.
2.4 Caractérisation des solutions optimales

2.4.1 Conditions nécessaires d’optimalité
Étant donné un vecteur x0 , nous souhaiterions être capables de déterminer
si ce vecteur est un minimum local ou global de la fonction f . La propriété
de différentiabilité de f fournit une première manière de caractériser une
solution optimale.
Théorème 2.4.1 (Condition nécessaire du premier ordre). Si x0 est un mi-

nimum local du problème (2.1) et supposons que f : Rn → R est continûment
∂f
différentiable (f est continue et ses dérivées partielles ∂xi
sont continues) sur
n 0
un ensemble ouvert S ⊂ R contenant x .
Alors
∇f (x0 ) = 0.
Démonstration. Soit d ∈ Rn un vecteur quelconque. On a
g(α) = f (x0 + αd) ≥ f (x0 ), ∀α ∈ R/(x0 + αd) ∈ S.
En utilisant l’hypothèse que f est différentiable, on obtient
f (x0 + αd) − f (x0 ) dg(0) f (x0 + αd) − f (x0 )

0 ≤ lim = = lim ≤ 0.
>
α→0 α dα <
α→0 α
D’où
dg(0)
= dT ∇f (x0 ) = 0.
dα
Comme d est choisi arbitrairement, alors
∇f (x0 ) = 0.
Définition 2.4.1. Les points x0 tels que ∇f (x0 ) = 0 sont appelés points
critiques (ou stationnaires) de f .
Remarque 2.4.1. Si f est convexe, la condition nécessaire du premier ordre

est également suffisante pour que x0 soit un minimum global.
Théorème 2.4.2 (Condition nécessaire du second ordre). Soient f : Rn →

R, deux fois continûment différentiable et x0 ∈ Rn . Si x0 est un minimum
local (ou global) de f , alors ∇f (x0 ) = 0 et ∇2 f (x0 ) est semi-définie positive.
Démonstration. Supposons que f est deux fois continûment différentiable et

d ∈ Rn un vecteur quelconque.
Pour tout ∀α ∈ R, le développement de Taylor d’ordre 2 s’écrit :
α2 T 2
f (x0 + αd) − f (x0 ) = α[∇f (x0 )]T d + d ∇ f (x0 )d + o(α2 ).
2
En utilisant la condition ∇f (x0 ) = 0 et le fait que x0 est un minimum local,

on déduit l’existence d’un > 0 (suffisamment petit) tel que
f (x0 + αd) − f (x0 ) 1 T 2 0 o(α2 )

∀α ∈ (0, ) : 0 ≤ = d ∇ f (x )d + .
α2 2 α2
Le passage à la limite quand α → 0 et l’utilisation de la relation
o(α2 )
lim =0
α→0 α2
entrainent
dT ∇2 f (x0 )d ≥ 0
ce qui démontre que ∇2 f (x0 ) est une matrice semi-définie positive.
2.4.2 Conditions sufffisantes d’optimalité

Les conditions données précédemment sont nécessaires, c’est-à-dire qu’elles
doivent être satisfaites pour tout minimum local (ou global) ; cependant, tout
vecteur vérifiant ces conditions n’est pas nécessairement un minimum.
Exemple 2.4.1. Soit la fonction
f (x) = −x4 , x ∈ R.
Le point x0 = 0 satisfait les conditions nécessaires du premier et du second

ordre :
0 00
f (x0 ) = −4x3 |x=0 = 0, f (x0 ) = −12x2 |x=0 = 0 ≥ 0.
Néanmoins, le point x0 = 0 ne constitue pas un minimum de la fonction f .

Il est au contraire un maximum global :
∀x ∈ R, f (x) = −x4 ≤ 0 = f (0).
Le théorème qui suit établit une condition suffisante pour qu’un vecteur
soit un minimum local, si f est deux fois continûment différentiable.
Théorème 2.4.3 (Condition suffisante du second ordre). Soient f : Rn → R,

deux fois continûment différentiable et x0 ∈ Rn . Si ∇f (x0 ) = 0 et ∇2 f (x0 )
est définie positive, alors x0 est un minimum local de f .
2.5 Étude de quelques exemples 31
Démonstration. Le développement de Taylor de la fonction f à l’ordre 2, au

voisinage de x0 s’écrit :
1
f (x0 + l) − f (x0 ) = lT ∇2 f (x0 )l + o(k l k2 ).
2
Toute direction l ∈ Rn , tendant vers 0, peut être écrite sous la forme
l = θd, où k d k= 1 et θ > 0 (assez petit).
On aura alors
o(θ2 )

0 0 0 0 2 1 T 2 0
f (x + l) − f (x ) = f (x + θd) − f (x ) = θ d ∇ f (x )d + 2 .
2 θ
Comme
dT ∇2 f (x0 )d > 0
et
o(θ2 )
lim= 0,
θ→0 θ 2
alors pour tout nombre positif θ > 0 assez petit, on aura
f (x) = f (x0 + θd) > f (x0 ),
ce qui prouve que x0 est un minimum local de f .
2.5 Étude de quelques exemples

2
Exemple 2.5.1. Soit f (x) = 1 − e−x .
On a à résoudre le problème suivant :
minf (x).
x∈R
On a
0 2
f (x) = 0 ⇔ 2xe−x = 0 ⇔ x = 0,
et
00 2 2
f (x)|x=0 = 2e−x − 4x2 e−x |x=0 = 2 > 0.
Le point x0 = 0 est un minimum local de f .
On peut remarquer que le point x0 = 0 est un minimum global de f .
2.5 Étude de quelques exemples 32
Exemple 2.5.2. Soit
f (x1 , x2 ) = x21 + x22 − 2x1 x2 + x1 → min
sur R2 .
On a  ∂f
 ∂x1
= 2x1 − 2x2 + 1 = 0
∇f (x) = 0 ⇔
∂f
= 2x2 − 2x1 = 0

∂x2
Les équations n’étant pas compatibles, il s’ensuit alors que le problème posé
n’a pas de solution. Le maximum de f n’existe pas non plus, puisque la
condition nécessaire du premier ordre est la même que pour le minimum.
Exemple 2.5.3. Soit
f (x1 , x2 ) = x21 − x22 − 2x1 x2 + x1 → min
sur R2 .
Cherchons les points stationnaires
 ∂f
 ∂x1 = 2x1 − 2x2 + 1 = 0 −1 1
∇f (x) = 0 ⇔ ⇒ x1 = , x2 = .
 ∂f 4 4
∂x2
= −2x2 − 2x1 = 0
2.6 Exercices 33
−1 1
Calculons le hessien de f au point x0 = ( 4 4
)
∂ 2f ∂ 2f ∂ 2f ∂ 2f
= 2, = = −2, = −2.
∂x21 ∂x1 ∂x2 ∂x2 ∂x1 ∂x22
Donc
2 0 2 −2
∇ f (x ) = = M,
−2 −2
où
M1 = 2 > 0; M2 = det M = −8 < 0
Le hessien n’est pas semi-définie positif. Il s’ensuit alors que le point x0 =
( −1
4
1
4
) ne constitue pas un minimum de f .
−1 1 1
f( , ) = − > −1 = f (0, 1).
4 4 8
2 2
Exemple 2.5.4. Soit f (x) = f (x1 , x2 ) = e−x1 −x2 à minimiser sur R2 .
On a
−x2 −x2
 ∂f
 ∂x1 = −2x1 e 1 2 = 0
⇒ x1 = x2 = 0.
 ∂f −x21 −x22
∂x2
= −2x2 e =0
D’autre part, au point x0 = (0, 0), on a
∇2 f (x0 ) < 0.
Le point x0 = (0, 0) ne constitue pas donc un minimum pour la fonction f .

La fonction f admet le point x0 = (0, 0) comme maximum.
2.6 Exercices
Exercice 2.6.1. Soit f : Rn → R.
a) Démontrer que si f est convexe, alors tout minimum local est global.
b) Supposons que f est une forme quadratique. Démontrer une condition
nécessaire et suffisante pour que f soit strictement convexe.
c) Déterminer les valeurs de a, b et c telles que la fonction
f (x, y, z) = x2 + 2axy + by 2 + cz 2 ,
soit convexe sur R3 .

2.6 Exercices 34
d) Déterminer, si possible, les valeurs de a et b telles que
f (x) = x3 + ax2 + bx
admette :
1. un point maximum local au point x = −1 et un point minimum
local au point x = +1.
2. un point maximum local au point x = +1 et un point minimum
local au point x = 0.
Exercice 2.6.2. Soit ϕ la fonction définie sur R par
ϕ(x) = x exp(−x2 /2), pour x ∈ R
et f la fonction définie sur R2 par
f (x, y) = xy exp((−x2 − y 2 )/2), pour (x, y) ∈ R2 .
1. Déterminer les extrema de ϕ sur R et préciser leurs natures.

2. Déterminer les extrema de f sur R2 et préciser leurs natures.
Exercice 2.6.3. Supposons que f : R → R est convexe, et a et b du domaine
de définition de f avec a < b.
(a) Montrer que
b−x x−a
f (x) ≤ f (a) + f (b), ∀x ∈ [a, b].
a−x x−b
(b) Montrer que
f (x) − f (a) f (b) − f (a) f (b) − f (x)

≤ ≤ , ∀x ∈]a, b[.
x−a b−a b−x
(c) Supposons que f est différentiable. Utiliser le résultat de (b) (ou la
définition de f convexe) pour démontrer que
f (b) − f (a)
f 0 (a) ≤ ≤ f 0 (b).
b−a
(d) Supposons que f est deux fois différentiable. Utiliser le résultat de
(c) pour montrer que f 00 (a) ≥ 0 et f 00 (b) ≥ 0
2.6 Exercices 35
Exercice 2.6.4. – Montrer que la fonction f définie sur R2 par

√
f (x, y) = 2x2 + y 2 − 3xy + 2x + 1, (x, y) ∈ R2 ,
admet un unique point de minimum global sur R2 que l’on déterminera.

– Minimiser la fonction suivante sur son domaine de définition :
n
Y
g(x1 , x2 , · · · , xn ) = xxi i .
i=1
Exercice 2.6.5. Soit f : R2 −→ R la fonction définie par
f (x1 , x2 ) = x31 − 3x1 1 + x22 .

a) f admet-elle des points critiques ? des extrêma locaux ? justifier.

b) Soit g : [0, 2π] −→ R la fonction définie par
g(t) = f (cos t, sin t)
1. Montrer que g 0 (t) = −6 sin t cos(2t)

2. Trouver les points critiques de g.
3. Etudier la variation de g.
4. Déduire les extrêma de g.
Exercice 2.6.6. Considérons la fonction suivante :

4θ − 7
h(θ) =
θ2 +θ−2
– Identifier tous les points stationnaires de h ;
– Parmi ceux-ci, identifier tous les minima locaux de h ;
– Identifier des points où la fonction n’est pas bornée.
Exercice 2.6.7. Considérons la fonction suivante :
h(θ) = 1 − 12θ + 7.5θ2 − θ3 .
– Identifier tous les points stationnaires de h ;

– Parmi ceux-ci, identifier tous les minima locaux de h.
Exercice 2.6.8. a) Montrer que si f : Rn → R est strictement convexe et
possède un minimum, alors celui-ci est unique.
2.6 Exercices 36
b) L’affirmation suivante, spécifier si elle est vraie ou fausse. Justifier la

réponse.
Soient f : Rn → R et x∗ tel que ∇f (x∗ ) = 0 et ∇2 f (x∗ ) est semi définie
positive. Alors x∗ est un minimum local de f .
Exercice 2.6.9. – Soit f : Rn → R définie par
1 (x−µ)2
∀x ∈ R, f (x) = √ e− 2 .
2π
On fixe x1 , . . . , xn ∈ R. Résoudre le problème suivant :
" n #
Y
max f (xi ) .
µ∈R
i=1
– Déterminer les extrema, s’ils existent, de la fonction suivante :
f (x, y) = x2 y 2 + x2 + y 2 + 2axy (a ≥ 0).
Exercice 2.6.10. Soient n ≥ 2 et f : Rn → R la fonction définie par

n−1
X
3
f (x) = (1 + xn ) x2i + x2n .
i=1
Montrer que 0 est le seul point critique de f , que f y atteint un minimum

local strict, mais pas global.
Chapitre 3
Les méthodes numériques pour

l’optimisation sans contraintes
3.1 Introduction
Comme la stationnarité de f est une condition nécessaire d’optimalité,
pratiquement toutes les méthodes de minimisation sans contrantes dans Rn
consistent à rechercher un point x∗ stationnaire (∇f (x∗ ) = 0).
Ce problème est équivalent à la résolution d’un système d’équations non
linéaires :
∂f
gi (x) = (x) = 0, i = 1, · · · , n.
∂xi
On peut chercher à résoudre directement ce système, ce qui conduit à la
méthode de Newton. Cependant, il faut se rappeler que cette méthode présente
quelques inconvénients :
i) la divergence de la méthode, si le point de départ est trop éloigné de
x∗ ,
ii) elle exige que la fonction f soit deux fois continûment différentiable
et exige le calcul des dérivées secondes.
C’est pourquoi, les méthodes les plus couramment utilisées sont basées sur un
principe général assez simple, mais dont l’analyse des conditions de conver-
gence sont complexes : on les appelle méthodes de descente. Il s’agit de
procédures itératives de construction d’une suite de points {xk } telle que la
fonction f décroı̂t d’une itération à une autre, i.e.,
f (xk+1 ) < f (xk ), k = 0, 1, · · · .
37
3.2 La méthode du gradient 38
Le processus itératif général de construction de la suite {xk } a la forme

suivante :
xk+1 = xk + θk dk , k = 0, 1, · · · (3.1)
où dk est une direction d’amélioration ou de descente et θk le pas le long de
cette direction.
Le problème restant posé et qui différencie les différentes méthodes numériques
est le choix du pas θk et de la direction dk à chaque itération.
3.2 La méthode du gradient

3.2.1 Interprétation physique du gradient
Pour une fonction différentiable f : Rn → R, le gradient ∇f (x0 ) de f au
point x0 se définit comme suit :
f (x0 + 4x) − f (x0 ) = (∇f (x0 ))T 4x + o(k4xk), (3.2)
où
o(k4xk)
lim = 0.
k4xk→0 k4xk
Une autre interprétation du gradient peut se faire de la manière suivante :

soit x0 ∈ Rn . De x0 , on choisit une direction de déplacement d ∈ Rn , kdk = 1,
et on pose :
x(θ) = x0 + θd, θ ≥ 0.
Le point x(θ) est le point atteint après un déplacement le long de la direction
d avec un pas θ. Estimons la variation de la valeur de la fonction f en passant
du point x0 au point x0 + θd. La relation (3.2) prend la forme suivante :

0 0 0 T o(θ)
f (x + θd) − f (x ) = θ (∇f (x )) d + .
θ
Pour des valeurs de θ ≥ 0 voisines de zéro, le signe de l’expression f (x0 +

θd) − f (x0 ) dépendra du signe de (∇f (x0 ))T d.
Pour avoir la relation f (x0 + θd) < f (x0 ), ie., une diminution de la valeur de
f (x) lors du passage du point x0 au point x0 + θd, on devrait choisir θ ≥ 0
assez petit et la direction d ∈ Rn de façon à avoir (∇f (x0 ))T d < 0.
Définition 3.2.1. La direction d ∈ Rn est appelée direction de descente, si
(∇f (x0 ))T d < 0 (3.3)
Le processus itératif (3.1) de construction de la suite {xk } prend la forme
xk+1 = xk + θk dk , k = 0, 1, · · · (3.4)
avec, si ∇f (xk ) 6= 0, la direction dk est choisie de façon que

T
∇f (xk ) dk < 0,

(3.5)
et le pas θk est positif. Si ∇f (xk ) = 0, alors le processus itératif est arrêté et

xk+1 = xk (ce qui est équivalent à choisir dk = 0).
En vertu de la relation (3.5) de dk et du gradient ∇f (xk ), on appelle les
algorithmes de ce type ”méthodes du gradient”. Certains auteurs réservent
le terme ”méthode du gradient” pour le cas particulier où dk = −∇f (xk ).
Il existe une large variété de possibilités pour choisir la direction dk et le pas
θk dans les méthodes du gradient.
3.2.2 Sélection des directions de descente

Plusieurs méthodes du gradient s’écrivent sous la forme :
xk+1 = xk − θk Dk ∇f (xk ), (3.6)
où Dk est une matrice symétrique définie positive. Dans ce cas, la direction
dk s’écrit
dk = −Dk ∇f (xk )
et la condition de descente
T
∇f (xk ) dk < 0

peut s’écrire
T
− ∇f (xk ) Dk ∇f (xk ) < 0

et qui est vérifiée puisque Dk > 0.

On donne quelques exemples de choix de la matrice Dk .
Méthode de la descente la plus rapide (méthode de la plus forte

pente, steepest descent)
On pose Dk = I, k = 0, 1, 2, · · · où I est la matrice identité n × n.
Dans ce cas, le processus itératif (3.6) prend la forme
xk+1 = xk − θk ∇f (xk ), k = 0, 1, 2, · · · (3.7)
Nous allons justifier ci-après l’appelation de méthode de la plus forte pente.

En partant du point xk et en se mouvant le long de la direction d, la fonction
f (x) va varier avec une vitesse donnée par la dérivée directionnelle de f au
point xk dans la direction d, soit :
f (xk + θd) − f (xk ) T

f 0 (xk ; d) = lim = ∇f (xk ) d.
≥
θ→0
θ
Pour des directions d telles que kdk = 1, la vitesse de variation de la fonction

f sera maximale pour
∇f (xk )
dk = (3.8)
k∇f (xk )k
En effet, on a d’après l’inégalité de Cauchy-Schwartz
T
∇f (xk ) d ≤ k∇f (xk )kkdk = k∇f (xk )k

et pour dk vérifiant (3.8), on a

T
k T
∇f (xk ) ∇f (xk )
∇f (x ) dk = .
k∇f (xk )k
Ainsi, le gradient ∇f (xk ) constitue la meilleure direction de croissance à

partir du point xk . La direction opposée à celle du gradient (−∇f (xk ) ) est
la meilleure direction de descente à partir de xk .
L’inconvénient de la méthode de descente rapide est sa lente convergence.
3.2.3 Sélection du pas

Il existe un certain nombre de règles de choix du pas θk dans la méthode
du gradient. Nous allons présenter les plus couramment utilisées.
a) Règle du minimum
Elle consiste à choisir, à l’itération k, le pas θk minimisant la fonction f
dans la direction dk , c-à-d
f (xk + θk dk ) = min f (xk + θdk ). (3.9)

θ≥0
b) Règle du minimum réduit

C’est une version de la règle du minimum qui est la plus utilisée. On fixe
un scalaire s > 0 et θk est défini par
f (xk + θk dk ) = min f (xk + θdk ). (3.10)

θ∈[0,s]
Remarque 3.2.1. La résolution des problèmes d’optimisation (3.9) et (3.10)

se fait par des méthodes d’optimisation unidimentionnelle.
c) Règle du pas constant

Ici, on fixe pour toutes les itérations
θk = s, k = 0, 1, · · · (3.11)
La règle du pas constant est la plus simple. Toutefois, si le pas est grand, il
y-a risque de divergence et quand le pas est trop petit, la vitesse de conver-
gence serait très lente. Ainsi la règle du pas constant n’est utile que pour les
problèmes où la valeur appropriée du pas est connue ou peut être facilement
calculée.
Exemple 3.2.1. On considère la fonctionnelle quadratique suivante :
f (x1 , x2 ) = 8x21 + 4x1 x2 + 5x22 .
On applique la méthode du gradient à pas optimal, en partant du point initial

!
(0)
(0) x1 10
x = (0) = ,
x2 10
pour trouver le minimum de f .

– On calcule le gradient de f :

16x1 + 4x2
∇f (x) = .
4x1 + 10x2
– On calcule la valeur du gradient au point x(0) :

(0) 200
∇f (x ) = .
140
– On calcule le point x(1) :

(1) (0) (0) (0) 10 (0) 200 10 − 200α(0)
x = x −α ∇f (x ) = −α = .
10 140 10 − 140α(0)
– On cherche la valeur optimale de α(0) . Pour ce, on calcule f (x(1) ) puis
on détermine α(0) permettant de minimiser f (x(1) ). On a
f (x(1) ) = 8(10 − 200α(0) )2 + 4(10 − 200α(0) )(10 − 140α(0) ) + 5(10 − 140α(0) )2
= −59600 + 1060000α(0)
= ϕ(α(0) ).
On calcule α(0) tel que ϕ0 (α(0) ) = 0, d’où α(0) = 0.056.
– On trouve ainsi
(1) −1.20
x = .
2.16
– On cherche de la même façon tous les points x(k) jusqu’à ce que le
critère d’arrêt soit satisfait.
Exemple 3.2.2. Utiliser la méthode de la plus forte pente puis de la plus forte
pente accélérée (p=2) pour trouver le minimum de la fonction f définie de
R2 dans R comme suit :
1
f (x1 , x2 ) = x41 − 2x31 + x22 − 3x1 − x1 x2 .
6
On a 3
4x1 − 6x21 − 3 − x2
∇f (x1 , x2 ) = 1 .
x − x1
3 2

0 0
Soit x = . On trouve la direction de la plus forte pente
0

0 3
−∇f (x ) = .
0
On minimise donc
g0 (λ) = f (x0 − λ∇f (x0 )) = 81λ4 − 54λ3 − 6λ.
On trouve
λ0 ≈ 0.582.
Notre premier pas nous conduit donc au point

1 0 0 1.746
x = x − λ0 ∇f (x ) = .
0
On réitère pour obtenir les valeurs suivantes :

i i i
i x −∇f
(x) gi (λ) λi x
0 3 1.746
0 81λ4 − 54λ3 − 6λ 0.582
0 0 0
1.746 0 1.746
1 0.508λ2 − 3.049λ − 6.590 3
0 1.746 5.238
1.746 5.238 2.01
2 752λ4 + 716λ3 + 214λ2 − 27λ − 11 0.05
5.238 0 5.238
2.01 0 2.01
3 0.012λ2 − 0.07λ − 11.904 3
5.238 0.264 6.03
Pour la plus forte pente accélérée, après avoir fait 2 pas de la plus forte
pente standard, nous devons faire un pas accéléré, en utilisant la direction
x2 − x0 . On minimise donc la fonction
g2 (λ) = f (x0 + λ(x2 − x0 )) = 9.29λ4 − 10.65λ3 − 4.57λ2 − 5.238λ.
On trouve
λ2 = 1.172
et on atteint le point

3 0 2 0 2.05
x = x + λ2 (x − x ) = ,
6.137
qui est prés du minimum global.

3.3 La méthode de Newton 44
3.3 La méthode de Newton

La méthode de Newton est obtenue en posant dans (3.6)
−1
Dk = ∇2 f (xk ) , k = 0, 1, · · · (3.12)
ce qui donne
−1
xk+1 = xk − θk ∇2 f (xk ) ∇f (xk ), k = 0, 1, · · ·
en supposant que ∇2 f (xk ) est une matrice définie positive. Dans le cas où
∇2 f (xk ) n’est pas définie positive, une certaine modification est nécessaire.
L’idée de la méthode de Newton peut s’expliquer de deux manières :
– Lors de la minimisation d’une fonction sur Rn , le problème consistait
à chercher un point x∗ ∈ Rn tel que
∇f (x∗ ) = 0.
La méthode numérique de Newton appliquée à l’équation
g(x∗ ) = ∇f (x∗ ) = 0
construit les approximations successives de la manière suivante :

−1
∂g(xk )

k+1 k
x =x − g(xk ), k = 0, 1, · · · (3.13)
∂x
où 
g1
 ..  ∂g(xk ) ∂gi (xk )

g =  . , = .
∂x ∂xj 1≤i,j≤n
gn
En tenant compte du fait que
∂g(xk )
= ∇2 f (xk ) = H(xk ),
∂x
la formule itérative (3.13) s’écrit alors
−1
xk+1 = xk − ∇2 f (xk ) ∇f (xk ), k = 0, 1, · · ·

(3.14)
Le point xk+1 peut être interprété comme la racine de l’approximation

linéaire de la fonction
g(x) = ∇f (x)
au voisinage de xk . On a
∂g(xk )
g(x) ' g(xk ) + (x − xk ) = 0,
∂x
d’où −1
∂g(xk )

k
x−x =− g(xk )
∂x
et −1
∂g(xk )

k+1 k
x=x =x − g(xk )
∂x
ou −1
xk+1 = xk − ∇2 f (xk ) ∇f (xk ).

– Une autre interprétation de la méthode de Newton est la suivante :

elle consiste à minimiser l’approximation quadratique q(x) de f (x) au
voisinage de xk .
T 1
f (x) ' q(x) = f (xk )+ ∇f (xk ) (x−xk )+ (x−xk )T ∇2 f (xk )(x−xk ).

2
Si le hessien H(xk ) = ∇2 f (xk ) est définie positif, le point xk+1 de
la méthode de Newton est alors pris comme étant le minimum de la
fonction q(x) :
0 = ∇q(xk+1 ) = ∇f (xk ) + ∇2 f (xk )(xk+1 − xk ) = 0.
D’où la formule itérative
−1
xk+1 = xk − ∇2 f (xk ) ∇f (xk ).

Cette formule itérative est une itération de la méthode de Newton. Elle

correspond à l’itération plus générale
xk+1 = xk − θk Dk ∇f (xk ), k = 0, 1, · · · (3.15)
−1
où θk = 1, Dk = ∇2 f (xk ) , ou encore
xk+1 = xk + θk dk
−1
avec θk = 1, dk = − ∇2 f (xk ) ∇f (xk ).
Remarque 3.3.1. Lorsque le hessien ∇2 f (xk ) n’est pas défini positif, la di-
rection de déplacement dk dans la méthode de Newton peut ne pas être une
direction de descente. En effet, l’expression
T T 2 −1
∇f (xk ) dk = − ∇f (xk ) ∇ f (xk ) ∇f (xk ) = −dTk ∇2 f (xk )dk

peut être éventuellement positive et dans ce cas, la direction dk ne serait plus

une direction de descente.
Exemple 3.3.1. On cherche à obtenir le zéro de la fonction
 2 
x + y2 + z2 − 3
F : (x, y, z) 7→  x2 + y 2 − z − 1  .
x+y+z−3
La méthode de Newton s’écrit comme suit :

(0)
x est donné
x(k+1) = x(k) − (∇F (x(k) ))−1 F (x(k) ).
Dans notre cas, on a

 
2x 2y 2z
∇F (x) =  2x 2y −1  .
1 1 1
 
1
(0)
Premier cas : On choisit x =  0 .
1
Itération 1 : On a  
−1
F (x(0) ) =  −1 
−1
et  
2 0 2
∇F (x(0) ) =  2 0 −1 
1 1 1
d’où
3
 
2
x(1) =  1
2
.
1
Itération 2 : On a
−1
 
2
F (x(1) ) =  3
2

−1
et  
3 1 2
∇F (x(1) ) =  3 1 −1 
1 1 1
d’où
5
 
4
x(2) =  3
4
.
1
Itération 3 : On a
1
 
8
F (x(2) ) =  1
8

0
et  
5/2 3/2 2
∇F (x(2) ) =  5/2 3/2 −1 
1 1 1
d’où
9
 
8
x(3) =  7
8
.
1
On a ainsi
1
 
32
F (x(3) ) =  1
32
.
0

Deuxième cas : On choisit x(0) = 0 0 0 .
Itération 1 : On a  
3
F (x(0) ) =  −1 
−3
et  
0 0 0
∇F (x(0) ) =  0 0 −1  .
1 1 1
3.4 La méthode du gradient conjugué 48
On tombe ainsi sur l’un des cas pathologiques de la méthode de

Newton, lorsque la matrice ∇F est singulière.
3.4 La méthode du gradient conjugué

Dans cette méthode, on utilise un modèle quadratique de f , nous al-
lons donc d’abord présenter l’algorithme appliqué à une fonction fortement
convexe quadratique.
3.4.1 Cas linéaire

Soit f (x) = 12 xT Ax − bx, avec A symétrique définie positive.
On sait alors qu’il existe un minimum unique sur Rn donné par x∗ = A−1 b.
Dans la suite, on note r(x) = Ax − b = ∇f (x) le résidu.
Définition 3.4.1. Les vecteurs non nuls {d1 , · · · , dp } sont dits conjugués par
rapport à la matrice A si
pour tout i 6= j ∈ {1, · · · , p} : dTi Adj = 0.
Lemme 3.4.1. Un ensemble de vecteurs conjugués par rapport à A est un
ensemble de vecteurs linéairement indépendants.
Posons φ(ρ) = f (x + ρd), alors
0
φ (ρ) = ρdT Ad + Axd − bd
et
1
f (x + ρd) = (x + ρd)T A(x + ρd) − b(x + ρd).
2
D’où
0 r(x)d
φ (ρ) = 0 ⇒ ρ = − , (d 6= 0). (3.16)
dT Ad
Théorème 3.4.1. Soit x(0) ∈ Rm et {d0 , · · · , dm−1 } un ensemble de vecteurs
conjugués par rapport à A. On considère la suite définie par
r(x(k) )dk
x(k+1) = x(k) + ρk dk , où ρk = − .
dTk Adk
Alors r(x(k) )di = 0 pour i = 0, · · · , k − 1 et x(k) minimise f et la suite (x(k) )
converge en au plus n itérations.
Pour pouvoir utiliser la méthode itérative du théorème précédent, il faut

construire un ensemble de vecteurs conjugués par rapport à A. Or, afin de
réduire le nombre d’opérations, on se propose de déduire d(k) à partir de
d(k−1) uniquement.
Dans l’algorithme du gradient conjugué linéaire, on prend
d(k) = −∇f (x(k) ) + βk d(k−1)
T
avec βk tel que d(k) Ad(k−1) = 0, on en déduit
T
d(k) Ad(k−1) = (−∇f (x(k) ) + βk d(k−1) )T Ad(k−1)
T T
= −r(x(k) )Ad(k−1) + βk d(k−1) Ad(k−1)
d’où T
r(x(k) )Ad(k−1)
βk = (k−1)T (k−1) . (3.17)
d Ad
Comme d(k) ∇f (x(k) ) = −kr(x(k) )k22 , on déduit bien une direction de descente.
Remarque 3.4.1. On rappelle que s’il existe un vecteur d tel que dT ∇f (x∗ ) <
0, alors d est une direction de descente de f en x∗ .
Algorithme : Gradient conjugué linéaire

1. Initialisation Choisir x(0) et poser k = 0, r(0) = Ax(0) − b, d(0) = −r(0) .
2. Itération k Tant que kr(x(k) )k > , faire

(k)T (k)
ρk = dr(k)T Ad
r
(k)
x(k+1) = x(k) + ρk d(k)

r(k+1) = r(k) + ρk Ad(k)
(k+1)T (k+1)
βk+1 = r r(k)T rr(k)
d(k+1) = −r(k+1) + βk+1 d(k)
k =k+1
Fin tant que
Notons que les formules pour r(k) et βk+1 ont changé, ceci est possible grâce
au théorème suivant qui affirme en particulier que les d(k) sont conjugués.
Théorème 3.4.2. Soit x(k) 6= x∗ , obtenu après la k ème itération de l’algo-
rithme du gradient conjugué linéaire avec r(k) et βk+1 définis par les équations
(3.16) et (3.17) respectivement. Alors, on a
(i) r(k) r(i) = 0, pour i = 0, · · · , k − 1 ;

(ii) V ect{r(0) , · · · , r(k) } = V ect{r(0) , Ar(0) · · · , Ak r(k) } ;
(iii) V ect{d(0) , · · · , d(k) } = V ect{d(0) , Ad(0) · · · , Ak d(k) } ;
T
(iv) d(k) Ad(i) = 0 pour i = 0, · · · , k − 1 ;
Commentaires. • On a T
r(k) d(k)
ρk = − (k)T (k) , (3.18)
d Ad
et dans l’algorithme, on a
T
r(k) r(k)
ρk = (k)T (k) (3.19)
d Ad
Montrons l’équivalence de (3.18) et (3.19). On a d(k) = −r(k) +βk d(k−1) ,
donc (3.18) s’écrit comme suit :
(k)T
ρk = − d(k)rT Ad(k) −r(k) + βk d(k−1)

T (k)T
r(k) r(k) (k−1)
= T
d(k) Ad(k)
− βk rd(k)TdAd(k)
T
r(k) r(k)
= T
d(k) Ad(k)
T
car r(k) d(k−1) = 0.
• On a x(k+1) = x(k) + ρk d(k) et r(k) = Ax(k) − b d’où
r(k+1) − r(k) = (Ax(k+1) − b) − (Ax(k) − b)

= (Ax(k+1) − x(k) )
= ρk Ad(k)
d’où
r(k+1) = r(k) + ρk Ad(k) .
• Montrons que
T
r(k) Ad(k−1)
βk = (k−1)T (k−1)
d Ad
et T
r(k) r(k)
βk =
r(k−1)T r(k−1)
sont équivalentes.
On a
r(k) − r(k−1) = ρk−1 Ad(k−1)
donc
T T r(k) − r(k−1)
r(k) Ad(k−1) = r(k)
ρk−1
d’où
T r(k) − r(k−1)
βk = r(k)
ρk−1 d(k−1)T Ad(k−1)
or T
r(k) r(k) T T
ρk = (k)T (k) ⇒ ρk−1 d(k−1) Ad(k−1) = r(k−1) r(k−1)
d Ad
d’où T
T r(k) − r(k−1) r(k) r(k)
βk = r(k) =
r(k−1)T r(k−1) r(k−1)T r(k−1)
car
T
r(k) r(k−1) = 0, r(k) = d(k) − βk−1 d(k−1)
et r(k) est orthogonal à toutes les directions d(0) , d(1) , · · · , d(k) .
Remarque 3.4.2. 1. Dans la démonstration du théorème, il est essentiel de

choisir d = −∇f (x(0) ). C’est à partir de d(0) que l’on construit des
(0)
gradients orthogonaux et des directions conjuguées.

2. L’algorithme du gradient conjugué linéaire est surtout utile pour résoudre
des grands systèmes creux.
3. La convergence peut être assez rapide, si A admet seulement p valeurs
propres distinctes, la convergence a lieu en au plus p itérations.
3.4.2 Cas non linéaire

Pour pouvoir appliquer l’algorithme du gradient conjugué linéaire au cas
d’une fonction f quelconque, il faut :
– remplacer r(x(k) ) par ∇f (x(k) ) ;
– déterminer ρk par une minimisation unidimentionnelle.
Algorithme du Gradient conjugué non linéaire (Fletcher-Reeves)

1. Initialisation Choisir x(0) , poser k = 0 et calculer f (0) = f (x(0) ) et
∇f (0) = ∇f (x(0) ), d(0) = −∇f (0) .
3.5 La méthode de relaxation 52
2. Itération k Tant que k∇f (k) k > , faire

– Déterminer ρk
– Calculer x(k+1) = x(k) + ρk d(k)
– Calculer ∇f (k+1) = ∇f (x(k+1) )
T
∇f (k+1) ∇f (k+1)
– Calculer βk+1 = T
∇f (k) ∇f (k)
– Calculer d(k+1) = −∇f (k+1)
+ βk+1 d(k)
– Poser k = k + 1.
Fin tant que
3.5 La méthode de relaxation

La dernière méthode que nous présentons permet de ramener un problème
de minimisation dans Rn à la résolution successive de n problèmes de mini-
misation dans R, à chaque itération.
On cherche à minimiser f : Rn → R. On pose X = (x1 , · · · , xn ).
Le principe de la méthode est le suivant : étant donné un itéré X k de coor-
données (xk1 , · · · , xkn ), on fixe toutes les composantes sauf la première et on
minimise sur la première :
min f (x, xk2 , · · · , xkn ), x ∈ R.
On obtient ainsi la première coordonnée de l’itéré suivant X k+1 que l’on note
xk1 ; on peut, pour effectuer cette minimisation dans R, utiliser par exemple
la méthode de Newton dans R. On recommence ensuite en fixant la première
coordonnée à xk+1
1 et les n − 2 dernières comme précédemment. On minimise
sur la deuxième et ainsi de suite.
L’algorithme obtenu est :
Algorithme de relaxation
1. Initialisation Poser k = 0 et choisir X 0 ∈ Rn .
2. Itération k Pour i variant de 1 à n, on calcule la solution xk+1

i de
k+1
min f (xk+1 k+1
1 , x2 , · · · , xi , x, xk+1 k+1
i+1 , · · · , xn ), x ∈ R.
3. Critère d’arrêt – Si kxk+1 − xk k < , stop.

– Sinon, poser k = k + 1 et aller à 2.
3.6 Exercices 53
3.6 Exercices
Exercice 3.6.1. Considérons un problème de minimisation d’une fonction
donnée sous la forme suivante :
m
1X
f (x) = fi (x)2 ;
2 i=1
où fi est deux fois différentiable.

a) Calculer le gradient et le Hessien de f en un point x.
b) Donner l’algorithme de Newton ou autre appliqué pour cette fonction
f.
c) Donner l’algorithme en prenant
1
fi (x) = xT Ai x + bTi x + 1.
2
Exercice 3.6.2. Soit le problème d’optimisation sans contraintes suivant où
la fonction f : R2 → R :
min f (x, y) = 3x2 + 3y 2 .
Pour chacun de ces algorithmes, appliquer deux itérations de la méthode

en prenant comme point de départ (x0 , y 0 ) = (1, 1).
– La méthode du gradient à pas variable ;
– La méthode de Newton ;
– La méthode des gradients conjugués.
Exercice 3.6.3. Dans cet exercice, on étudie une méthode de minimisation
sans contraintes d’une fonction quadratique de la forme :
1
f (x) = xT Ax + xT b + c.
2
Définition 3.6.1. On dit que les vecteurs di , i = 0, . . . , n − 1 sont conjugués
par rapport à une matrice symétrique définie positive A si :
∀i, j ∈ {i = 0, . . . , n − 1}, i 6= j ⇒ dTi Adj = 0.
• On note {di , i = 0, . . . , n − 1} une famille quelconque de vecteurs

conjugués par rapport à une matrice symétrique définie positive A de Rn×n .
On se donne par ailleurs un vecteur b ∈ Rn .
3.6 Exercices 54
Soit un vecteur initial x0 ∈ Rn arbitraire.

A l’étape (k +1), supposant construits les vecteurs x1 , x2 , . . . , xk , ce qui sous-
entend que les vecteurs (Axl + b), l = 0, . . . , k − 1 sont tous différents de zéro,
deux cas peuvent se présenter :
– ou bien Axk + b = 0 et l’algorithme est terminé,
– ou bien Axk + b 6= 0, auquel cas, on définit le nombre
dTk .(Axk + b)
ρk = ,
dTk Adk
puis le vecteur
xk+1 = xk − ρk .dk .
1. Justifier le choix de ρk .
2. En supposant que Axk + b 6= 0, ∀k = 1, . . . , n − 1, exprimer xl , pour l =
1, . . . , n en fonction de x0 , (ρi , i = 0, . . . , n − 1) et (di , i = 0, . . . , n − 1).
3. Montrer que dTk Axk = dTk Ax0 , ∀k = 0, . . . , n − 1.
4. – Calculer dTk (Axn + b).
– Déduire que xn est la solution du système Ax = −b.
– Que peut-on dire sur la convergence de la méthode.
5. Appliquer l’algorithme du gradient conjugué pour résoudre le problème
d’optimisation sans contraintes suivant :
min f (x1 , x2 ) = 10x1 + 10x2 + 100 − x21 − x22 − 2x1 x2 .

(x1 ,x2 )∈R2
Exercice 3.6.4. Soit f : R2 −→ R la fonction définie par
f (x1 , x2 ) = x31 − 3x1 1 + x22 .

a) f admet-elle des points critiques ? des extrêma locaux ? justifier.

b) Soit g : [0, 2π] −→ R la fonction définie par
g(t) = f (cos t, sin t)
1. Montrer que g 0 (t) = −6 sin t cos(2t)

2. Trouver les points critiques de g.
3. Etudier la variation de g.
3.6 Exercices 55
4. Déduire les extrêma de g.
Exercice 3.6.5. Pour chacune des affirmations suivantes, spécifier si elles sont
vraies ou fausses. Justifier la réponse.
1. Soit f : Rn → R une fonction deux fois continûment différentiable et
soit xk tel que ∇2 f (xk ) est définie positive. Alors la direction de Newton
dN est une direction de descente pour f en xk .
2. Soit q : Rn → R telle que
1
q(x) = xT Qx + g T x + c,
2
n×n
avec Q ∈ R symétrique définie positive, g ∈ Rn et c ∈∈ R.
On suppose d1 , . . . , dn Q−conjuguées. Si Q = αI avec α > 0, alors
d1 , . . . , dn sont orthogonales.
3. Soient f : Rn → R et x∗ tel que ∇f (x∗ ) = 0 et ∇2 f (x∗ ) est semi définie
positive. Alors x∗ est un minimum local de f .
Exercice 3.6.6. Soit le problème d’optimisation sans contraintes suivant :
min f (x, y) = 3x2 + 3y 2 .
(x,y)∈R2
1. Appliquer deux itérations de la méthode du gradient à pas fixe en

prenant comme point de départ (x0 , y0 ) = (1, 1).
2. Appliquer deux itérations de la méthode du gradient à pas optimal en
prenant comme point de départ (x0 , y0 ) = (1, 1).
Exercice 3.6.7. Appliquer un algorithme pour résoudre le problème d’opti-
misation sans contraintes suivant :
min f (x1 , x2 ) = 10x1 + 10x2 + 100 − x21 − x22 − 2x1 x2 .
(x1 ,x2 )∈R2
Exercice 3.6.8. Soit A ∈ Mn (R) et J la fonction definie de Rn dans R par

2
J(x) = ekAxk , où k.k designe la norme euclidienne sur Rn .
1. Montrer que J admet un minimum.
2. On suppose que la matrice A est inversible, montrer que ce minimum
est unique.
3. Ecrire l’algorithme du gradient à pas optimal pour la recherche de ce
minimum.
4. A quelle condition suffisante cet algorithme converge-t-il ?
Deuxième partie
Optimisation avec contraintes
56
Chapitre 4
Optimisation non linéaire avec

contraintes
4.1 Introduction
Un problème de minimisation d’une fonction non-linéaire f sous contraintes
x ∈ S ⊂ Rn , où S est défini par une collection de m inégalités et r égalités,
se présente sous la forme suivante :

 f (x) → min,
gi (x) ≤ 0, i = 1, m, (4.1)
hj (x) = 0, j = 1, r.

Les fonctions gi , i = 1, · · · , m et hj , j = 1, · · · , r sont des fonctions réelles de

classe C 1 .
Remarque 4.1.1. Si les fonctions f, gi , i = 1, · · · , m et hj , j = 1, · · · , r sont
linéaires, alors le problème (4.1) est appelé problème de programmation linéaire.
Remarque 4.1.2. Dans un problème de programmation linéaire, l’optimum
est toujours atteint en un point extrême du polyhèdre S.
En programmation non linéaire (ou optimimisation non linéaire), même si le
domaine admissible S est un polyhèdre, le minimum peut être atteint en un
point quelconque de S (en un point extrême, point frontière ou encore point
intérieur).
57
4.1 Introduction 58
Exemple 4.1.1. Soit le problème suivant :



 f (x) = (x1 − 4)2 + (x2 − 6)2 → min,
x1 + x2 ≥ 1,


 2x1 + 3x2 ≤ 12,
x1 ≥ 0, x2 ≥ 0,

L’ensemble S est un polytope et il est représenté sur la figure suivante :
L’équation f (x) = α √= constante > 0 représente un cercle de centre

M (4, 6) et de rayon R = α.
En faisant diminuer (ou augmenter) le nombre α, la valeur de f (x) diminue
(ou augmente). Il s’ensuit alors que le point x∗ , qui est l’intersection des
droites perpendiculaires BC et M x∗ , réalise le minimum de la fonction f sur
l’ensemble S. De plus, le point x∗ se trouve sur l’arête du polyèdre S.
Ici, on trouve
196
x∗ = 24 36
, f (x∗ ) =

13 13
.
13
Exemple 4.1.2. Considérons la fonction :
f (x) = (x1 − 4)2 + (x2 − 1)2 ,
et cherchons son minimum sur le même polyèdre précédent S. Cette fois-ci,

le minimum sera atteint au point intérieur
x∗ = 4 1 , f (x∗ ) = 0.

Exemple 4.1.3. Soit la fonction
f (x) = (x1 − 8)2 + x22 ,
et cherchons son minimum sur le même polyèdre précédent S. Cette fois-ci,

le minimum sera atteint au point extrême
x∗ = 6 0 , f (x∗ ) = 4.

Les minima locaux et globaux de f sur Rn sont définis de la manière

suivante :
Définition 4.1.1. Un vecteur x0 ∈ S est un minimum local de f sur S si
∃ > 0 tel que f (x0 ) ≤ f (x), ∀x ∈ S, avec kx − x0 k < .
Définition 4.1.2. Un vecteur x0 ∈ S est un minimum global de f sur S si
f (x0 ) ≤ f (x), ∀x ∈ S.
4.2 Théorèmes généraux d’existence

Considérons le problème d’optimisation suivant :
min f (x). (4.2)

x∈S⊂Rn
Nous allons donner deux résultats très généraux d’existence d’une solution
optimale au problème (4.2).
Théorème 4.2.1. (Existence) Soit S ⊂ Rn (S non vide) et f : S → R semi

continue inférieurement.
– Si S est un ensemble non vide fermé et borné de Rn , alors il existe une
solution optimale x0 ∈ S, qui vérifie donc
f (x0 ) ≤ f (x), ∀x ∈ S.
– Si S est un ensemble non vide fermé de Rn et si f est coercive alors il

existe une solution x0 ∈ S qui vérifie
f (x0 ) ≤ f (x), ∀x ∈ S.
Démonstration. – Si S 6=6= ∅ est un sous-ensemble fermé borné de Rn ,

comme f est continue, elle atteint ses bornes sur S, d’où l’existence de
x0 .
– Si f est croissante à l’infini, alors il existe R > 0 tel que si kxk > R
alors f (x) > f (0) ; donc
min f = min f,
S S∩BR
où BR désigne la boule fermée de centre 0 et de rayon R. L’ensemble

S ∩BR est compact, car c’est l’intersection d’un fermé et d’un compact.
Donc, par ce qui précède, il existe x0 ∈ S tel que
f (x0 ) = min f = min f.

S∩BR BR
Théorème 4.2.2. (Unicité) Soit f : S ⊂ Rn → R. On suppose que f est

strictement convexe et que S est convexe. Alors il existe au plus un élément
x0 de S tel que f (x0 ) = minf.
S
Démonstration. Supposons que x0 et x∗ soient deux solutions du problème

(4.2), avec x0 6= x∗ . Alors,
1 1 1 1
min f ≤ f ( x0 + x∗ ) < f (x0 ) + f (x∗ ) = min f.
S 2 2 2 2 S
On aboutit donc à une contradiction.
Théorème 4.2.3. (Existence et Unicité) Soit f : S ⊂ Rn → R une fonction

continue. On suppose que f est strictement convexe et que S est non vide et
convexe fermé sur Rn .
Si S est borné ou f est croissante à l’infini, c’est-à-dire que f (x) → +∞
quand kxk → +∞, alors il existe un unique élément x0 de S solution du
problème de minimisation (4.2), i-e, tel que f (x0 ) = minS f.
4.3 Conditions d’optimalité 61
4.3 Conditions d’optimalité

Afin d’analyser ou de résoudre de manière efficace un problème d’optimi-
sation, il est fondamental de pouvoir disposer de conditions d’optimalité. En
effet, celles-ci nous servent non seulement à vérifier la validité des solutions
obtenues, mais souvent l’étude de ces conditions aboutit au développement
des algorithmes de résolution eux-mêmes.
Des conditions équivalentes peuvent être obtenues de diverses manières, en
procédant à des analyses suivant différentes ”lignes directrices”. L’approche
considérée ici pour l’obtention de ces conditions est basée sur les notions de
descente et de direction admissible.
4.3.1 Conditions nécessaires d’optimalité dans le cas

des contraintes quelconques
Soit f une fonction non linéaire définie de Rn dans R et de classe C 1 . Soit
S un sous-ensemble non vide de Rn et considérons le problème de minimisatin
suivant :
min f (x),
(4.3)
x ∈ S.
Définition 4.3.1. – Un vecteur x de Rn est dit solution réalisable ou
plan du problème (4.3), si x appartient à l’ensemble des contraintes S.
– Un plan x∗ est appelé solution optimale du problème (4.3), si
f (x∗ ) = min f (x).

x∈S
On dit aussi que x∗ constitue un point de minimum relatif global.

– Un vecteur x0 ∈ S est appelé point de minimum relatif local de la
fontion f , si pour un certain > 0, il satisfait les relations :
f (x0 ) = min f (x),

x∈B(x0 ,)
B(x0 , ) = x ∈ S, kx − x0 k ≤ .

Définition 4.3.2 (Direction admissible). Soient un ensemble S ⊂ Rn et

x0 ∈ S. Une direction admissible de S en x0 est un vecteur d tel que
d 6= 0 et x0 + αd ∈ S, ∀α ∈ [0, α] pour un certain α > 0.

En vertu de cette définition, on peut remarquer que tous les vecteurs d de

n
R sont des directions admissibles, si le point x est un point intérieur de S.
Le problème se posera donc pour les points de la frontière de S. Pour cette
raison, au lieu d’avoir ∇f (x0 ) = 0 comme dans le cas sans contraintes, ici la
condition nécessaire tiendra compte aussi de la nature de l’ensemble S.
La condition telle que nous venons de l’énoncer ne présente malheureuse-
ment que peu d’intérêt en vue d’un usage en pratique,
car si l’ensemble
des
directions de descente de f en x0 , disons A = d| (∇f (x0 ))T d < 0 , peut
être exprimé en fonction du gradient de la fonction objectif, ce n’est pas
nécessairement le cas de l’ensemble de toutes les directions admissibles de S
en x0 , A = {d | d 6= 0 et x0 + αd ∈ S, ∀α ∈ [0, αmax ] pour un certain αmax > 0}.
Il serait avantageux de trouver un moyen de la convertir en une condition
plus pratiquement utilisable mettant en jeu des équations ou des inéquations.
Théorème 4.3.1 (Condition nécessaire d’optimalité). Soit f une fonction

non linéaire, définie de Rn dans R et de classe C 1 . Si x0 est un minimum
local (ou global) du problème (4.3), alors pour toute direction admissible d en
x0 , on a
∇T f (x0 )d ≥ 0. (4.4)
Démonstration. Soit d une direction admissible en x0 . Il existe alors α > 0

tel que x0 + αd ∈ S pour tout α ∈ [0, α].
Considérons la fonction ϕ(α) = f (x0 + αd).
Comme x0 est un minimum local, il existe > 0 tel que
f (x0 ) ≤ f (x), ∀x ∈ B(x0 , ) ∩ S.
Considérons
Sα = x0 + αd, α ∈ [0, α] .

∀x ∈ Sα ∩ B(x0 , ) ∩ S, on aura
f (x0 ) ≤ f (x).
Soit
e] = α ∈ [0, α] /x0 + αd ∈ Sα ∩ B(x0 , ) ∩ S ,

[0, α
et
ϕ(α) ≥ ϕ(0), ∀α ∈ [0, α
e] .
D’où α0 = 0 est un minimum local de ϕ(α) sur [0, α

e].
On a
0
ϕ(α) = ϕ(0) + αϕ+ (0) + o(α)
où
0 ϕ(α) − ϕ(0)
ϕ+ (0) = lim+ .
α→0 α
0
Si ϕ+ (0) était négative, alors pour un nombre α assez petit, on aurait eu
ϕ(α) < ϕ(0).
Ce qui contredirait le fait que ϕ possède un minimum local en α = 0. On a

0
donc bien ϕ+ (0) ≥ 0.
Par conséquent, comme
0
ϕ (α) = [∇f (x0 + αd)]T d,
on obtient
0
ϕ+ (0) = [∇f (x0 )]T d ≥ 0.
La relation (4.4) est alors démontrée.
4.3.2 Conditions d’optimalité pour le cas de contraintes

linéaires de type égalités
a- Condition nécessaire d’optimalité du premier ordre
Considérons dans Rn le problème de programmation non linéaire :

f (x) → min,
(4.5)
g(x) = Ax − b = 0,
où b ∈ Rm , A une matrice d’ordre m × n, formée des vecteurs colonnes et des

vecteurs lignes suivants :
   
AT1 g1 (x)
 AT   g2 (x) 
 2 
A = (a1 , a2 , · · · , an ) =  ..  , g(x) =  ,
 
..
 .   . 
T
Am gm (x)
où gi (x) = ATi x − bi , 1 ≤ i ≤ m.

Pour que l’ensemble des solutions réalisables
S = {x ∈ Rn , g(x) = 0} = x ∈ Rn , ATi x − bi = 0, 1 ≤ i ≤ m

ne soit pas vide ou ne soit pas réduit à un point isolé, on considérera que
rangA = m < n.
Proposition 4.3.1. Soit x une solution réalisable du problème (4.5).
Un vecteur d ∈ Rn est alors une direction admissible en x si et seulement si
Ad = 0. (4.6)
De plus, pour un tel vecteur, on a
x(α) = x + αd ∈ S, ∀α ∈ R.
En effet,
g(x(α)) = Ax(α) − b = Ax + αAd − b = 0, ∀(α 6= 0) ∈ R ⇔ Ad = 0.
Remarque 4.3.1. Pour α = 0, x(α) se réduit à x qui vérifie g(x) = 0.
Si donc x0 est un point minimum pour le problème (4.5), alors la fonction
ϕ(α) = f (x0 + αd) pour Ad = 0 admet aussi un minimum au point α = 0.
On en déduit que
dϕ(0)
= ϕT (0) = ∇f T (x0 )d = 0. (4.7)
dα
L’égalité (4.7) montre que le vecteur d est orthogonal au gradient de f au
point minimum x0 . Il est aussi orthogonal à chacun des vecteurs-lignes de la
matrice A :
 
AT1
 AT 
 2 
Ad = 0 ⇒  ..  d = 0 ⇒ ATi d = 0, 1 ≤ i ≤ m.
 . 
ATm
Ceci n’est possible que s’il existe un vecteur λ0 ∈ Rm tel que

m
X
∇f (x0 ) = − λ0i Ai = −AT λ0 . (4.8)
i=1
En effet, dans le cas contraire, pour tout vecteur λ ∈ Rm , on aura

m
X
0
∇f (x ) 6= λi Ai .
i=1
Donc le vecteur ∇f (x0 ) n’appartient pas au sous-espace vectoriel engendré

par les vecteurs-lignes de la matrice A.
Il existe alors un vecteur d0 6= 0 tel que
ATi d0 = 0, 1 ≤ i ≤ m, ∇f T (x0 )d0 6= 0.
Ce qui contredit le critère d’optimalité (4.7).

Pour le problème (4.5), introduisons la fonction L(x, λ), appelée fonction de
Lagrange.
Xm
T
L(x, λ) = f (x) + λ g(x) = f (x) + λi gi (x), (4.9)
i=1
où
 
g1 (x)
x = (x1 , x2 , · · · , xn ) ∈ Rn , λ = (λ1 , λ2 , · · · , λm ) ∈ Rm , g(x) =  ..
.
 
.
gm (x)
En termes de fonction de Lagrange, l’égalité (4.8) exprime donc simplement

la condition de stationnarité du point x0 .
∇x L(x0 , λ0 ) = 0.
En effet, on a
m
X m
X
0 0 0
∇x L(x , λ ) = ∇f (x ) + λ0i ∇gi (x0 ) 0
= ∇f (x ) + λ0i Ai = 0. (4.10)
i=1 i=1
D’autre part, la condition g(x0 ) = 0 réalisée pour une solution optimale est
équivalente à la condition de stationnarité du vecteur λ0 de la fonction de
Lagrange :  
g1 (x0 )
∇λ L(x0 , λ0 ) =  ... 0
 = g(x ) = 0. (4.11)
 
0
gm (x )
Si l’on note  
∇x L(x, λ)
∇L(x, λ) =  ,
∇λ L(x, λ)
alors la règle des multiplicateurs de Lagrange s’établit ainsi :
Théorème 4.3.2 (Multiplicateurs de Lagrange). Si x0 est un point de mini-

mum relatif local (ou global) pour le problème (4.5), alors il existe un vecteur
unique λ0 ∈ Rm , appelé vecteur des multiplicateurs de Lagrange, tel que
∇L(x0 , λ0 ) = 0 ⇔ ∇x L(x0 , λ0 ) = 0 et ∇λ L(x0 , λ0 ) = 0. (4.12)
Donc si x0 est un point de minimum relatif du problème (4.5), alors le

couple (x0 , λ0 ) est un point stationnaire de la fonction de Lagrange (4.9).
Remarque 4.3.2. Le point x0 n’est pas nécessairement un point de minimum
de la fonction de lagrange L(x, λ) pour λ = λ0 .
Soit x0 un point de minimum relatif du problème (4.5). Il lui correspond
donc un vecteur λ0 = (λ01 , · · · , λ0m ) vérifiant la relation (4.10). Les nombres
λ0i , 1 ≤ i ≤ m, sont dits alors multiplicateurs de Lagrange et ils sont uniques
si et seulement si rangA = m, comme le montre le théorème suivant :
Théorème 4.3.3. Le vecteur des multiplicateurs de Lagrange λ0 est unique

si et seulement si rangA = m.
Démonstration. Soit rangA = m et supposons que pour le point de minimum

x0 , il correspond deux vecteurs λ0 et λ∗ tels que :
m
X m
X
∇f (x0 ) + λ∗i Ai = 0, ∇f (x0 ) + λ0i Ai = 0.
i=1 i=1
On en déduit que
m
X
(λ∗i − λ0i )Ai = 0.
i=1
Comme rangA = m, alors les vecteurs Ai , 1 ≤ i ≤ m sont linéairement

indépendants. Donc, λ∗i = λ0i , 1 ≤ i ≤ m, d’où
λ∗ = λ0 .
Inversement, soit λ0 un vecteur unique correspondant au point de minimum

x0 et considérons la combinaison linéaire nulle suivante :
m
X
αi Ai = 0.
i=1
De la relation (4.10), on en déduit :

m
X m
X m
X
0
∇f (x ) + λ0i Ai − αi Ai = ∇f (x ) + 0
(λ0i − αi )Ai = 0.
i=1 i=1 i=1
Donc si λ0i − αi = λ∗i , on aura

m
X
∇f (x ) + 0
λ∗i Ai = 0.
i=1
Le vecteur λ∗ vérifie aussi, comme λ0 , la relation (4.10). En vertu de l’uni-

cité du vecteur des multiplicateurs de Lagrange, on conclut que les vecteurs
αi , 1 ≤ i ≤ m, sont nuls et que les vecteurs Ai , 1 ≤ i ≤ m sont linéairement
indépendants. Par conséquent, rangA = m.
Exemple 4.3.1. Résoudre le problème de minimisation suivant :

 f (x) = 2x21 + x22 + 5x23 → min,
x1 − x2 + x3 = 1,
2x1 + x2 + 5x3 = 0.

On définit la fonction de Lagrange :
L(x, λ) = 2x21 + x22 + 5x23 + λ1 (x1 − x2 + x3 − 1) + λ2 (2x1 + x2 + 5x3 ).
La condition nécessaire d’optimalité est donnée comme suit :
4x1 + λ1 + 2λ2 = 0 (4.13)

2x2 − λ1 + λ2 = 0 (4.14)
10x3 + λ1 + 5λ2 = 0 (4.15)
x1 − x2 + x3 = 1, (4.16)
2x1 + x2 + 5x3 = 0. (4.17)
En faisant la somme des équations (4.56), (4.57) et (4.58) et en tenant compte

de (4.60), on obtient
λ1 + 8λ2 = 0 ⇒ λ1 = −8λ2 .
On aura alors
3 −9 3
x1 = λ2 , x2 = λ2 , x3 = λ2 .
2 2 10
10
En utilisant (4.59), on déduit la valeur de λ2 = 63 . D’où
80 5 −5 1 40
λ1 = − , x1 = , x2 = , x3 = , f (x) = .
63 21 7 21 63
On trouve donc un seul vecteur x ∈ Rn qui réalise le minimum de f sur
l’ensemble des contraintes. En effet, la condition nécessaire de Lagrange est
aussi suffisante puisque la fonction considérée ici est strictement convexe. Par
conséquent,
1 40
x∗ = 5 −15 1 , f (x∗ ) = .

21 63
b- Condition nécessaire d’optimalité du second ordre

Considérons le problème (4.5) et supposons de plus que la fonction f est
de classe C 2 . On a alors la condition nécessaire suivante de second ordre.
Théorème 4.3.4. Si x0 est un point de minimum relatif du problème (4.5)

et λ0 le vecteur des multiplicateurs de Lagrange correspondant, alors la forme
quadratique
∇2x L(x0 , λ0 ) (ou ∇2 f (x0 ))
est semi-définie positive sur l’ensemble des points de la variété
Ay = 0. (4.18)
Démonstration. Soit y un vecteur de Rn vérifiant (4.18). On sait déjà que le

vecteur
x(α) = x0 + αy
est solution réalisable du problème (4.5) pour tout α ∈ R.
Posons
ϕ(α) = f (x(α)) = f (x0 + αy).
Puisque le point x0 réalise un minimum relatif pour la fonction f , alors la

fonction ϕ(α) admet aussi un minimum en α = 0. D’où
0 dϕ 00 d2 ϕ
ϕ (0) = |α=0 , ϕ (0) = |α=0 ≥ 0.
dα dα2
Donc
dϕ dx(α)
|α=0 = ∇f T (x(α)) |α=0
dα dα
= y T ∇f (x(α)) |α=0
= y T ∇f (x0 )
d2 ϕ dx(α)
2
|α=0 = y T ∇2 f (x(α))
dα dα
T 2
= y ∇ f (x(α))y.
Par conséquent, on obtient
y T ∇2 f (x0 )y ≥ 0 (4.19)
D’autre part, on a
m
T
X
L(x, λ0 ) = f (x) + λ0 g(x) = f (x) + λ0i (ATi x − bi ).
i=1
On en déduit que
m
X
0
∇x L(x, λ ) = ∇f (x) + λ0i Ai
i=1
∇2x L(x, λ0 ) = ∇2 f (x).
En vertu de la dernière égalité et de la relation (4.19), on obtient finalement
y T ∇2x L(x0 , λ0 )y ≥ 0.
c- Condition suffisante d’optimalité du second ordre

Théorème 4.3.5. Soit f une fonction de classe C 2 et (x0 , λ0 ) un couple de
vecteurs vérifiant la condition nécessaire d’optimalité du premier ordre pour
le problème (4.5), i.e.,
∇x L(x0 , λ0 ) = 0.
Pour que x0 soit un point de minimum relatif local du problème (4.5), il est
alors suffisant que la forme quadratique
y T ∇2x L(x0 , λ0 )y
soit définie positive sur l’ensemble des points y de la variété Ay = 0.
Démonstration. Soit y un vecteur de Rn vérifiant Ay = 0. Donc x(α) =
x0 + αy est solution réalisable pour tout α ∈ R. Soit
ϕ(α) = f (x(α)) = f (x0 + αy), α ∈ R.
On a alors
0 T dx(α) 0
∇f (x0 + αy) = ∇f (x0 + αy)y ⇒ ϕ (0) = ∇f (x0 )y.

ϕ (α) =
dα
00 00
ϕ (α) = y ∇ f (x + αy)y ⇒ ϕ (0) = y T ∇2 f (x0 )y.
T 2 0
En outre, de la condition nécessaire du premier ordre (4.8), on déduit que

∇f (x0 ) = −AT λ0 .
D’où
0
ϕ (0) = −AT λ0 y = 0,
00
ϕ (0) = y T ∇2 f (x0 )y > 0.
La fonction ϕ admet donc un minimum local en α = 0.
Soit maintenant un vecteur x, solution réalisable du problème (4.5) telle que
kx − x0 k = > 0.
Il existe donc un vecteur y tel que
k y k= 1, Ay = 0, x = x0 + y.
Il s’ensuit alors que
f (x) = f (x0 + y) = ϕ() > ϕ(0) = f (x0 ).
Le point x0 constitue donc bien un point de minimum pour le problème
(4.5).
d- Cas d’une fonction convexe

Considérons le problème
f (x) → min,
(4.20)
x ∈ S = {x ∈ Rn , g(x) = Ax − b = 0}
où f est une fonction convexe de classe C 1 et A une matrice d’ordre m × n,

avec rangA = m < n.
Soit x0 ∈ S et λ0 un m−vecteur tels que le couple (x0 , λ0 ) vérifie la condition
nécessaire d’optimalité du premier ordre, ie,
∇x L(x0 , λ0 ) = ∇f (x0 ) + AT λ0 = 0. (4.21)
Cette dernière relation est aussi suffisante pour l’optimalité du vecteur x0

dans le problème (4.20).
Puisque S est aussi convexe, on peut écrire
f (x) − f (x0 ) ≥ (∇f (x0 ))T (x − x0 ), ∀x ∈ S.
De l’égalité (4.21), on déduit que

T
f (x) − f (x0 ) ≥ −λ0 A(x − x0 ), ∀x ∈ S.
Comme A(x − x0 ) = 0, on déduit
f (x) ≥ f (x0 ).
Ce qui prouve que x0 réalise un minimum pour la fonction objectif du

problème (4.20).
Exemple 4.3.2. A titre d’illustration, calculons le minimum x0 pour une fonc-
tion quadratique convexe :
1
f (x) = xT Dx + cT x,
2
où D est une matrice symétrique définie positive et x ∈ S = {x ∈ Rn , g(x) = Ax − b = 0} .
La condition (4.21) donne alors
Dx0 + c = −AT λ0 ⇒ x0 = −D−1 (AT λ0 + c).

D’autre part, on a
Ax0 = b ⇒ −AD−1 AT λ0 − AD−1 c = b.
D’où −1
λ0 = − AD−1 AT (AD−1 c + b).

Par conséquent,
−1
x0 = D−1 AT AD−1 AT (AD−1 c + b) − D−1 c.

Exemple 4.3.3. Résolvons le problème suivant :


 f (x) = x21 + 3x22 + 4x23 − x1
x1 + x2 + x3 = 0,
2x1 − x2 + 5x3 = 1.

On a
   
2 0 0 −1
1 1 1 0
D =  0 6 0 ,c =  0 ,A = ,b = .
2 −1 5 1
0 0 8 0
En appliquant les résultats de l’exemple précédent, on trouve

 
7
−1 1  7
x0 = D−1 AT AD−1 AT (AD−1 c + b) − D−1 c = −9  , f (x0 ) = .

33 99
2

linéaires de type inégalités
Avant d’aborder le problème, voyons un lemme, appelé lemme de Farkas,
qui joue un rôle très important en optimisation mathématique.
Lemme 4.3.1 (Lemme de Farkas). Soient (m + 1) vecteurs de Rn , c, Ai , i =
1, m, m < n. Si pour chaque vecteur x vérifiant ATi x ≤ 0, 1 ≤ i ≤ m, on a
cT x ≤ 0, alors il existe des coefficients λi ≥ 0, 1 ≤ i ≤ m, tels que
m
X
c= λi Ai .
i=1
Démonstration. Sans perte de généralité, on peut supposer que les vecteurs

Ai , 1 ≤ i ≤ m, sont linéairement indépendants. Montrons alors que le vecteur
c appartient au sous-espace engendré par les vecteurs Ai , 1 ≤ i ≤ m, ie
m
X
c= λi A i . (4.22)
i=1
Si ce n’était pas le cas, il existerait alors un vecteur x orthogonal à tous les

vecteurs Ai , 1 ≤ i ≤ m et tel que
ATi x = 0, 1 ≤ i ≤ m, cT x = α > 0. (4.23)
Soit x0 un certain vecteur satisfaisant aux conditions du théorème :
ATi x0 ≤ 0, 1 ≤ i ≤ m, cT x0 = β ≤ 0. (4.24)
Considérons ensuite le vecteur x = x + θx0 où

α
0 < θ < |β| si β 6= 0,
0<θ si β = 0.
En vertu des relations (4.23) et (4.24), on aura alors
ATi x = ATi x + θATi x0 ≤ 0, 1 ≤ i ≤ m,

cT x = cT x + θcT x0 = α + θβ > 0.
Cette dernière relation contredit l’hypothèse du lemme, l’égalité (4.22) est

donc vraie.
Supposons maintenant que dans la relation (4.22), les coefficients λi ne sont
pas tous positifs ou nuls, par exemple λk < 0. Il existe alors un vecteur x tel
que
ATi x = 0, i 6= k, 1 ≤ i ≤ m, ATk x = αk < 0.
Soit aussi un certain vecteur x0 , satisfaisant aux inégalités
ATi x0 = βi < 0, 1 ≤ i ≤ m.
On construit le vecteur
αk λk
x = x + θx0 , 0 < θ < Pm .
| i=1 λi βi |
On aura donc
ATi x = ATi x + θATi x0 = θβi < 0, 1 ≤ i ≤ m, i 6= k;
ATk x = ATk x + θATk x0 = αk + θβk < 0;
mais
m
X m
X
T
c x = λi ATi x = λk ATk x + λi ATi x
i=1 i=1,i6=k
m
X
= λk (αk + θβk ) + θλi βi
i=1,i6=k
m
X
= λk αk + θ λi βi .
i=1
Cette dernière relation contredit l’hypothèse du théorème pour un nombre θ
positif assez petit. Notre supposition sur un certain λk < 0 est donc fausse.
Le lemme de Farkas est ainsi démontré.
Remarque 4.3.3. Ici, la démonstration est faite pour m vecteurs linéairement
indépendants, où m < n. Ce lemme reste vrai, même pour m ≥ n. Il suffit
alors de prendre les λi égaux à zéro pour les vecteurs linéairement dépendants.

Soit f une fonction non linéaire définie de Rn dans R et de classe C 1 .
Considérons le problème de minimisation de la fonction f sur l’ensemble S
défini par les inégalités linéaires suivantes :
S = {x ∈ Rn : g(x) = Ax − b ≤ 0} ,
où
       
g1 (x) AT1 x − b1 AT1 b1
g(x) =  .. .. ..  , b =  ..  .
= ,A = 
    
. . .   . 
gm (x) ATm x − bm Am T
bm
On notera ici que le nombre m peut être plus grand que n.
Le problème de minimisation d’une fonction f avec des contraintes linéaires
de type inégalités se résume ainsi :
f (x) → min, (4.25)
gi (x) ≤ 0, i ∈ I = {1, · · · , m} . (4.26)
Définition 4.3.3. Tout vecteur x vérifiant les inégalités (4.26) est appelé
solution admissible ou plan du problème (4.25)-(4.26).
Définition 4.3.4. La contrainte gi (x) ≤ 0 sera dite active au point x, si
gi (x) = 0 et passive si gi (x) < 0.
On notera l’ensemble des indices actifs au point x par
Ia = Ia (x) = {i ∈ I : gi (x) = 0} .
On a alors le lemme suivant :

Lemme 4.3.2. Dans les contraintes (4.26), un vecteur y de Rn est une
direction admissible au point x ∈ S si et seulement si
ATi y ≤ 0, i ∈ Ia (x).
Démonstration. Soit y une direction admissible au point x. Il existe alors un

nombre α > 0 assez petit tel que
x(α) = x + αy ∈ S, ∀α ∈]0, α].
On aura donc
Ax − b + αAy ≤ 0.
Puisque
ATi x − bi + αATi y ≤ 0, i ∈ I,
ATi x − bi = 0, ∀i ∈ Ia (x),
alors, en vertu de α > 0, on obtient
ATi y ≤ 0, ∀i ∈ Ia (x).
Inversement, soit y un vecteur tel que
ATi y ≤ 0, ∀i ∈ Ia (x).
Soit le vecteur x(α) = x + αy, où x est une solution admissible du problème
(4.25)-(4.26). On peut alors écrire
gi (x(α)) = ATi x − bi + αATi y = αATi y ≤ 0, ∀i ∈ Ia (x), ∀α ≥ 0;

gi (x(α)) = ATi x − bi + αATi y = gi (x) + αATi y, ∀i ∈ I \ Ia (x).
Comme gi (x) < 0, ∀i ∈ I \ Ia (x), on peut alors trouver un nombre α > 0

assez petit tel que
gi (x(α)) = gi (x) + αATi y ≤ 0, ∀i ∈ I \ Ia (x), ∀α ∈ [0, α].
Donc
gi (x(α)) ≤ 0, ∀i ∈ I, ∀α ∈ [0, α].
Ce qui revient à dire que
x(α) = x + αy ∈ S.
Le vecteur y considéré est, par conséquent, une direction admissible au point
x.
Théorème 4.3.6 (Théorème de Karush-Kuhn-Tucker). Soit x0 un point de
minimum du problème (4.25)-(4.26). Il existe alors un m−vecteur λ0 ≥ 0 tel
que :
i) pour la fonction de Lagrange L(x, λ) = f (x) + λT g(x), la condition de
stationnarité est satisfaite :
∇x L(x0 , λ0 ) = 0.
ii) la condition de complémentarité est remplie :
λ0i gi (x0 ) = 0, i ∈ I.
Démonstration. Le vecteur x0 étant un minimum, alors pour toute direction
admissible y en x0 , on aura
∇T f (x0 )y ≥ 0,
et ce, en vertu du théorème (4.3.1).
En utilisant le lemme (4.3.2), on peut écrire
ATi y ≤ 0, ∀i ∈ Ia (x0 ) ⇒ −∇T f (x0 )y ≤ 0.
En vertu du lemme de Farkas, il existe alors des coefficients λ0i ≥ 0, i ∈
Ia (x0 ), tels que X
−∇T f (x0 ) = λ0i Ai .
i∈Ia (x0 )
Posons λ0i = 0 pour i ∈ I\Ia (x0 ). On obtient alors

X
−∇T f (x0 ) = λ0i Ai ⇔ ∇x L(x0 , λ0 ) = 0, λ0i gi (x0 ) = 0, i ∈ I.
i∈I
Le théorème de de Karush-Kuhn-Tucker (KKT) est ainsi démontré.


Théorème 4.3.7. Soit f une fonction de classe C 2 . Si x0 un point de mini-
mum du problème (4.25)-(4.26), alors la forme quadratique
y T ∇2 f (x0 )y
est définie non négative sur l’ensemble de la variété :
ATi y = 0, i ∈ Ia (x0 ), (4.27)
où Ia (x0 ) est l’ensemble des indices actifs en x0 .
Démonstration. Supposons qu’il existe un vecteur y vérifiant (4.27) tel que
y T ∇2 f (x0 )y < 0.
Considérons le vecteur x(α) = x0 + αy. Pour α > 0 assez petit, le vecteur

x(α) est une solution réalisable du problème (4.25)-(4.26). On peut alors
écrire
1
f (x(α)) − f (x0 ) = α∇T f (x0 )y + α2 y T ∇2 f (x0 )y + o(α2 ).
2
En vertu du théorème de Karush-Kuhn-Tucker (4.3.6), on a
X
∇f (x0 ) = − λ0i ATi , λ0i ≥ 0, i ∈ Ia (x0 ).
i∈Ia (x0 )
D’où X
(∇f (x0 ))T y = − λ0i ATi y = 0.
i∈Ia (x0 )
Donc
o(α2 )

0 2 1 T 2 0
f (x(α)) − f (x ) = α y ∇ f (x )y + < 0,
2 α2
si α est un nombre positif assez petit.
Cette dernière inégalité contredit le fait que x0 soit un minimum local de f .
Par conséquent, la matrice ∇2 f (x0 ) est définie non négative sur l’ensemble
(4.27).
c- Condition suffisante d’optimalité du second ordre

Théorème 4.3.8. Soit x0 un point admissible du problème (4.25)-(4.26)
vérifiant les conditions nécessaires de Karush-Kuhn-Tucker. Si la matrice
∇2 f (x0 ) est définie positive sur l’ensemble (4.27), alors x0 est un point de
minimum du problème (4.25)-(4.26).
d- Cas de fonction convexe

Considérons le problème suivant :
f (x) → min, x ∈ S = {x ∈ Rn : g(x) = Ax − b ≤ 0} (4.28)
où f est une fonction convexe de classe C 1 .

Soit (x0 , λ0 ) un couple de vecteurs vérifiant le théorème de Karush-Kuhn-
Tucker (4.3.6) :
m
X
0
0 0
∇x L(x , λ ) = 0 ⇔ ∇f (x ) = − λ0i ATi , λ0i ≥ 0, 1 ≤ i ≤ m;
i=1
λ0i gi (x0 ) = 0, 1 ≤ i ≤ m.
Alors le vecteur x0 constitue un point minimum global du problème (4.28).

En effet, on peut écrire, du fait que f est convexe et S convexe,
f (x) − f (x0 ) ≥ ∇T f (x0 )(x − x0 ), ∀x ∈ S.
D’où m
X
0
f (x) − f (x ) ≥ − λ0i ATi (x − x0 ), ∀x ∈ S.
i=1
Puisque λ0i 0
= 0, pour i ∈ I\Ia (x ), alors on aura
X
f (x) − f (x0 ) ≥ − λ0i (ATi x − ATi x0 ),
i∈Ia (x0 )
d’où X
f (x) − f (x0 ) ≥ − λ0i (ATi x − bi ) ∀x ∈ S.
i∈Ia (x0 )
Par conséquent, x0 est un point de minimum global du problème (4.28).

Pour une fonction convexe, les conditions de KKT sont donc à la fois nécessaires
et suffisantes pour l’optimalité du plan x0 .

égalités non linéaires

f (x) → min,
(4.29)
x ∈ S = {x ∈ Rn : g(x) = 0}
où f est une fonction non linéaire définie de Rn dans R et de classe C 1 .
g(x) = (g1 (x), g2 (x), · · · , gm (x)) ,
avec gi (x) : Rn → R, 1 ≤ i ≤ m, sont de classes C 1 .
Considérons la fonction de Lagrange :
L(x, λ) = f (x) + λT g(x). (4.30)
a- Conditions nécessaires de premier ordre

Théorème 4.3.9 (Règle des multiplicateurs de Lagrange). Soit x0 une so-
lution optimale du problème (4.29) et supposons que les vecteurs
∇g1 (x0 ), ∇g2 (x0 ), · · · , ∇gm (x0 ) (4.31)
sont linéairement indépendants.
Alors il existe un vecteur multiplicateur de Lagrange (unique) λ0 tel que la
paire (x0 , λ0 ) vérifie les relations appelées conditions de stationnarité de la
fonction de Lagrange :
∇x L(x0 , λ0 ) = 0, ∇λ L(x0 , λ0 ) = 0. (4.32)
Définition 4.3.5. Un point x∗ est appelé point stationnaire du problème
(4.29), s’il existe un vecteur λ∗ tel que la paire (x∗ , λ∗ ) est un point station-
naire de la fonction de Lagrange (4.30) :
∇x L(x∗ , λ∗ ) = 0, ∇λ L(x∗ , λ∗ ) = 0. (4.33)
La recherche des points stationnaires du problème (4.29) se ramène à la
résolution du système (4.33) de (m + n) équations avec (m + n) inconnus
(x, λ).
Ainsi, d’après la règle des multiplicateurs de Lagrange, la résolution du
problème (4.29) (si la solution existe) se ramène à la recherche de la valeur
minimale de la fonction f (x) sur l’ensemble des points stationnaires.
Remarque 4.3.4. Contrairement aux fonctions convexes, les solutions opti-

males ne sont pas, en général, des points stationnaires de la fonction de
Lagrange avec λ = λ∗ .
Exemple 4.3.4. Considérons le problème de minimisation suivant :

f (x1 , x2 ) = x32 → min,
g(x1 , x2 ) = x2 − x21 = 0.
La solution optimale étant x0 = (0, 0).
∂g ∂g ∂g 0
On a ∂x1
(0, 0) = −2x1 |(0,0) = 0, ∂x2
(0, 0) = 1. Le vecteur ∂x
(0, 0) =
1
est un vecteur linéairement indépendant.
L(x, λ) = x32 + λ(x2 − x21 ).
Les conditions de stationnarité sont ainsi données :
∂L
(x, λ) = −2λx1 = 0,
∂x1
∂L
(x, λ) = 3λx22 + λ = 0,
∂x2
∂L
(x, λ) = x2 − x21 = 0,
∂λ
Ainsi à la solution optimale x0 = (0, 0) correspond un multiplicateur de La-

grange λ0 = 0.
On a alors L(x, λ0 ) = L(x, 0) = x32 ; le point x0 = (0, 0) est un point d’in-
flexion de la fonction de Lagrange L(x, 0) = x32 .

f (x1 , x2 ) = x2 → min,
g(x1 , x2 ) = x2 − x21 = 0.
∂g ∂g ∂g 0
On a ∂x1
(0, 0) = −2x1 |(0,0) = 0, ∂x2
(0, 0) = 1. Le vecteur ∂x
(0, 0) =
1
est un vecteur linéairement indépendant.
L(x, λ) = x2 + λ(x2 − x21 ).
Les conditions de stationnarité sont ainsi données :

∂L
(x, λ) = −2λx1 = 0,
∂x1
∂L
(x, λ) = 1 + λ = 0,
∂x2
Ce qui donne λ = −1.

On a alors L(x, λ0 ) = L(x, −1) = x21 qui atteint son minimum en x0 = (0, 0).

f (x1 , x2 ) = −x22 → min,
g(x1 , x2 ) = x2 = 0.

L(x, λ) = −x22 + λx2 .
On trouve λ = 0. L(x, 0) = −x22 , cette fonction n’atteint pas le minimum

mais le maximum au point x0 = (0, 0).
b- Condition nécessaire du second ordre

Considérons le problème (4.29), où on suppose que f (x) et g(x) sont de
classe C 2 et la solution optimale x0 est telle que les vecteurs (4.31) sont
linéairement indépendants, c-à-d, la solution optimale x0 est régulière.
Théorème 4.3.10. Si x0 est une solution optimale locale régulière du problème

(4.29), λ0 le vecteur multiplicateur de Lagrange correspondant, alors la forme
quadratique suivante est définie non négative :
lT ∇2x L(x0 , λ0 )l ≥ 0 (4.34)
sur l’hyperplan
lT ∇gi (x0 ) = 0, i = 1, · · · , m. (4.35)
c- Condition suffisante d’optimalité locale

Considérons le problème (4.29), où on suppose que f (x) et g(x) sont de
classe C 2 .
Théorème 4.3.11. Pour qu’un point stationnaire x0 soit une solution opti-
male locale du problème (4.29), il est suffisant qu’avec le vecteur multiplica-
teur de Lagrange correspondant λ0 , la forme quadratique suivante soit définie
positive :
lT ∇2x L(x0 , λ0 )l > 0 (4.36)
sur l’hyperplan
lT ∇gi (x0 ) = 0, i = 1, · · · , m (4.37)
avec l 6= 0.
Exemple 4.3.7. Trouver les paramètres d’une citerne tels que pour une surface
extérieure donnée S0 , la citerne aurait un volume maximal.
La surface extérieure de la citerne est égale à :
S0 = 2πx22 + 2πx1 x2 .
Le volume de la citerne est :
V = πx22 x1 .
Soient les fonctions suivantes :
f (x1 , x2 ) = −πx22 x1
g(x1 , x2 ) = 2πx22 + 2πx1 x2 − S0 .
Le problème posé est transformé ainsi :

f (x1 , x2 ) → min,
(4.38)
g(x1 , x2 ) = 0.
Le problème obtenu n’est pas équivalent au problème initial, puisqu’on n’a
pas pris en considération les contraintes supplémentaires
x1 ≥ 0, x2 ≥ 0. (4.39)
Mais nous allons résoudre le problème sous forme (4.38) en excluant, si

nécessaire, les solutions ne vérifiant pas les contraintes (4.39). Si le problème
(4.38) admet une solution alors le problème posé aurait sa solution parmi les
solutions optimales locales du problème (4.38).
L(x, λ) = −πx22 x1 + λ(2πx22 + 2πx1 x2 − S0 ).
Les points stationnaires vérifient les relations suivantes :
∂L
(x, λ) = −πx22 + 2πλx2 = 0
∂x1
∂L
(x, λ) = −2πx2 x1 + 4πλx2 + 2πλx1 = 0
∂x2
∂L
(x, λ) = 2πx22 + 2πx1 x2 − S0 = 0
∂λ
D’où r
S0
x1 = 4λ, x2 = 2λ, λ = ± .
24π
q
0 S0
Choisissons λ = 24π .
Calculons la matrice

2 0 0 −2πx2 + 2πλ0 0 −2πλ0
∇x L(x, λ ) = =
−2πx2 + 2πλ0 −2πx1 + 4πλ0 −2πλ0 −4πλ0
L’équation de l’hyperplan (4.37) est
∂g ∂g
( )y1 + ( )y2 = 4πλ0 y1 + 16πλ0 y2 = 0. (4.40)
∂x1 ∂x2
De (4.40), on obtient y1 = −4y2 .
La forme quadratique avec la matrice ∇2x L(x, λ) a la forme
y T ∇2x L(x, λ0 )y = −4πλ0 y1 y2 − 4πλ0 y22
et sur l’hyperplan (4.40), elle devient
y T ∇2x L(x, λ0 )y = 12πλ0 y22 > 0,
pour tout y = (y1 , y2 ) avec y2 6= 0.
Ainsi les conditions du théorème (4.3.11) sont vérifiées pour :
r r
0 S0 0 S0
x1 = 2 , x2 = .
6π 6π
Le cylindre avec ces paramètres aurait le plus grand volume.

inégalités non linéaires

 f (x) → min,
g(x) ≤ 0, (4.41)
x∈D

où f : Rn → R et gi : Rn → R, 1 ≤ i ≤ m sont des fonctions de classe C 1 ,

I = {1, 2, · · · , m} , D ⊂ Rn ouvert non vide.
Définition 4.3.6. – Tout vecteur x ∈ D vérifiant les contraintes g(x) ≤

0 du problème (4.41) est appelé solution admissible ou plan du problème
(4.41).
– La contrainte gi (x) ≤ 0 est dite active au point x si gi (x) = 0. Elle est
dite passive si gi (x) < 0.
– On notera l’ensemble des indices actifs au point x par
Ia (x) = {i ∈ I, gi (x) = 0} .
a- Conditions nécessaires d’optimalité de premier ordre

Théorème 4.3.12. Supposons que f et gi , i ∈ Ia (x0 ) sont différentiables au
point x0 , et les fonctions gi , i 6∈ Ia (x0 ) sont continues en x0 .
Si x0 est une solution optimale locale du problème (4.41), alors il n’existe pas
de vecteur l ∈ Rn vérifiant le système suivant :
lT ∇f (x0 ) < 0 (4.42)

lT ∇gi (x0 ) < 0, i ∈ Ia (x0 ) (4.43)
Démonstration. Soit x0 un plan optimal du problème (4.41), l ∈ Rn un vec-

teur vérifiant (4.43).
Comme x0 ∈ D et D est ouvert, alors il existe δ1 > 0 tel que
x0 + λl ∈ D, ∀λ ∈ [0, δ1 ]. (4.44)
Comme gi (x0 ) < 0 et les fonctions gi (.) sont continues en x0 pour i 6∈ Ia (x0 ),
alors il existe δ2 > 0 tel que
gi (x0 + λl) < 0, ∀λ ∈ [0, δ2 ], ∀i 6∈ Ia (x0 ). (4.45)
Enfin, comme
lT ∇gi (x0 ) < 0, i ∈ Ia (x0 ),
alors d’après le théorème 4.3.1, il existe δ3 > 0, tel que
gi (x0 + λl) < gi (x0 ) = 0, ∀λ ∈ [0, δ3 ], ∀i ∈ Ia (x0 ). (4.46)
De (4.44), (4.45) et (4.46), on déduit que
x0 + λl ∈ S, ∀λ ∈ [0, δ],
où δ = min(δ1 , δ2 , δ3 ). Donc l est une direction admissible en x0 .

D’après le théorème 4.3.1, on a
(∇f (x0 ))T l ≥ 0,
et donc le système (4.42)-(4.43) n’admet pas de solution l ∈ Rn .

Définition 4.3.7. Un vecteur l est dit direction admissible au point x e par
rapport à la contrainte inégalité gi (x) ≤ 0 (direction intérieure), si
lT ∇gi (e
x) < 0, si gi (e
x) = 0,
et l un vecteur quelconque si gi (e
x) < 0.
Définition 4.3.8. Un vecteur l est appelé direction admissible au point x e par
rapport aux contraintes du problème (4.41), si il est une direction admissible
par rapport à chacune des contraintes gi (x) ≤ 0, 1 ≤ i ≤ m au point x e.
Ainsi, les directions admissibles par rapport aux contraintes du problème
(4.41) au plan xe sont décrites par les équations (4.43) si on change x0 par x
e.
Du théorème 4.3.12, on déduit la proposition suivante :
Proposition 4.3.2. Si x0 est un optimum local du problème (4.41), alors au
point x0 , il n’existe pas de directions admissibles du problème (4.41).
Théorème 4.3.13. Soit x0 un point de minimum relatif local du problème
(4.41) tel que les vecteurs
∇gi (x0 ), i ∈ Ia (x0 ) (4.47)

Il existe alors un unique vecteur multiplicateur de Lagrange λ0 vérifiant les
relations suivantes :
λ0 ≥ 0.
∇x L(x0 , λ0 ) = 0.
(λ0 )T g(x0 ) = 0.
Définition 4.3.9. On dira qu’un plan x0 est régulier si les vecteurs
∇gi (x0 ), i ∈ Ia (x0 )


Considérons de nouveau le problème (4.41) mais en supposant que f, g
sont des fonctions de classe C 2 .
D’après le théorème 4.3.13, à toute solution optimale x0 régulière du problème
(4.41), il correspond un unique vecteur de Lagrange λ0 .
Définition 4.3.10. – Une contrainte gi (x) ≤ 0 active au point x0 est

dite forte si λ0i > 0.
L’ensemble des indices des contraintes fortes au point x0 sera noté :
Ia+ (x0 ) = i : gi (x0 ) = 0, λ0i > 0 .

– Une contrainte gi (x) ≤ 0 active au point x0 est dite faible si λ0i = 0.

L’ensemble des indices des contraintes faibles au point x0 sera noté :
Ia0 (x0 ) = i : gi (x0 ) = 0, λ0i = 0 .

Théorème 4.3.14. Soient x0 un plan optimal régulier du problème (4.41)

et λ0 le vecteur de Lagrange correpondant.
Alors, la forme quadratique est définie non négative :
lT ∇2x L(x0 , λ0 )l ≥ 0,
sur l’ensemble des vecteurs l vérifiant le système suivant :
lT ∇gi (x0 ) = 0, i ∈ Ia+ (x0 ),

(4.48)
T 0
l ∇gi (x ) ≤ 0, i ∈ Ia0 (x0 ).
c- Condition suffisante d’optimalité locale

Supposons que dans le problème (4.41), les fonctions f (x) et g(x) sont de
classe C 2 .
Définition 4.3.11. Un plan x0 du problème est dit pseudo-stationnaire, s’il

existe un m−vecteur λ0 tel que
∇x L(x0 , λ0 ) = 0, λ0i gi (x0 ) = 0, λ0i ≥ 0, 1 ≤ i ≤ m.

Théorème 4.3.15. Pour qu’un plan pseudo-stationnaire x0 soit localement

optimal dans le problème (4.41), il suffit que l’inégalité
lT ∇2x L(x0 , λ0 )l > 0, (4.49)
soit vérifiée pour tout vecteur l 6= 0 vérifiant le système :
lT ∇gi (x0 ) = 0, i ∈ Ia+ (x0 ),

(4.50)
lT ∇gi (x0 ) ≤ 0, i ∈ Ia0 (x0 ).
4.3.6 Optimisation des fonctions non linéaires sous des

contraintes générales non linéaires
Considérons le problème de minimisation d’une fonction non linéaire sous
des contraintes non linéaires :

 f (x) → min,
gi (x) ≤ 0, i ∈ I = {1, 2, · · · , m}, (4.51)
hj (x) = 0, j = 1, r,

où les fonctions f : Rn → R, gi : Rn → R, i = 1, m et hj (x) = 0, j = 1, r

sont de classe C 1 .

Théorème 4.3.16. Si x0 est un point de minimum local du problème (4.51)
et les vecteurs

∇gi (x0 ), i ∈ Ia (x0 ) = {i ∈ I : gi (x0 ) = 0} ,
(4.52)
∇hj (x0 ), j = 1, r,
sont linéairement indépendants, alors il existe un multiplicateur de Lagrange

λ ∈ Rm , λ ≥ 0, µ ∈ Rr tels que :
∇f (x0 ) + m
P 0
Pr 0
i=1 λi ∇gi (x ) + j=1 µj ∇hj (x ) = 0,
(4.53)
λi gi (x0 ) = 0, i = 1, m.
b- Condition suffisante d’optimalité

Théorème 4.3.17. Supposons que dans le problème (4.51), les fonctions
f, gi , hj sont de classe C 2 .
Supposons que pour une solution admissible x0 , il existe λ ∈ Rm , λ ≥ 0,
µ ∈ Rr tels que :
∇f (x0 ) + m
P 0
Pr 0
i=1 λi ∇gi (x ) + j=1 µj ∇hj (x ) = 0,
0
λi gi (x ) = 0, i = 1, m,
et pour tout d 6= 0 tel que

 T

 d ∇gi (x0 ) = 0, λi > 0, gi (x0 ) = 0,



dT ∇gi (x0 ) ≤ 0, i = 1, m, λi = 0, gi (x0 ) = 0,




 T
d ∇hj (x0 ) = 0, j = 1, r,
on a
dT ∇2x L(x0 , λ, µ)d > 0,
alors x0 est un point de minimum local.

 √ 2
 f (x1 , x2 ) = −x21 363 − x162 → min,
g(x1 , x2 ) = x1 + x2 − l = 0, (4.54)
x1 ≥ 0, x2 ≥ 0,

avec l > 0.
Posons
g1 (x1 , x2 ) = g(x1 , x2 );
g2 (x1 , x2 ) = −x1 ;
g3 (x1 , x2 ) = −x2 ;
x = (x1 , x2 ).
Le problème (4.54) devient :


 f (x) → min,
g1 (x) = 0,

(4.55)

 g2 (x) ≤ 0,
g3 (x) ≤ 0.

L’ensemble des plans du problème (4.55) est un ensemble compact et la

fonction objectif est continue. Donc le problème (4.55) admet une solution
optimale.
Calculons les vecteurs :

1 −1 0
∇g1 (x) = , ∇g2 (x) = , ∇g3 (x) = .
1 0 −1
Ces trois vecteurs sont linéairement indépendants deux à deux.
Considérons les contraintes du problème (4.55). On remarque aisément que
deux contraintes seulement peuvent être simultanément actives :
Soit g1 (x) = 0, g2 (x) = 0.
Soit g1 (x) = 0, g3 (x) = 0.
Ainsi, chaque plan du problème (4.55) est régulier.

Construisons la fonction de Lagrange :
√
3 x22
L(x, λ) = −x21 − + λ1 (x1 + x2 − l) − λ2 x1 − λ3 x2 .
36 16
La règle des multiplicateurs de Lagrange conduit aux relations suivantes :
√
∂L 3
(x, λ) = −x1 + λ1 − λ2 = 0, (4.56)
∂x1 18
∂L 1
(x, λ) = −x2 + λ1 − λ3 = 0, (4.57)
∂x2 8
∂L
(x, λ) = x1 + x2 − l = 0, (4.58)
∂λ1
−λ2 x1 = −λ3 x2 = 0, (4.59)
λ2 ≥ 0, λ3 ≥ 0, (4.60)
De (4.59), on déduit
λ2 x1 = 0, (4.61)
λ3 x2 = 0, (4.62)
De (4.56) et (4.57), on a
√
λ2 = −x1 183 + λ1 , (4.63)
λ3 = −x2 18 + λ1 , (4.64)
De (4.63) et (4.61), on déduit

√
3
(−x1 + λ1 )x1 = 0. (4.65)
18
De (4.58), on a
x2 = l − x1 . (4.66)
De (4.64) et (4.66), on déduit
l x1
λ3 = − + + λ1 . (4.67)
8 8
Les équations (4.62), (4.67) et (4.66) nous donnent
l x1
(− + + λ1 )(l − x1 ) = 0. (4.68)
8 8
Ainsi, on a obtenu les deux équations (4.65) et (4.68) :
√
(−x1 183 + λ1 )x1 = 0,
(− 8 + x81 + λ1 )(l − x1 ) = 0,
l
qui donnent trois plans pseudo-stationnaires :

1. x∗1 = 0, x∗2 = l, λ∗1 = 8l , λ∗2 = 8l , λ∗3 = 0.
√ √
2. x∗1 = l, x∗2 = 0, λ∗1 = l 183 , λ∗2 = 0, λ∗3 = l 183 .
√ √
3. x∗1 = 9l√
9+4 3
, x∗2 = 4l √
9+4 3
3
, λ∗1 = l 3√
18+8 3
, λ∗2 = λ∗3 = 0.
La forme quadratique correspondante a la forme suivante
√3 √
− 0 3 1
y T ∇2x L(x, λ)y = y T 8
−1 y = −y12 − y22 . (4.69)
0 8
8 8
Considérons la relation (4.60) pour tout point pseudo-stationnaire :
Le premier plan : La troisième contrainte est passive.

∂g 1
 y T ∂x1 (x∗ ) = y1 y2

= y1 + y2 = 0


1
−1
 y T ∂g 2
(x ∗
) = y y = −y1 = 0

1 2

∂x 0
Ce qui nous donne
y1 = y2 = 0.
4.4 Exercices 92
Le deuxième plan : La deuxième contrainte est passive.


T ∂g1 ∗
1
 y ∂x (x ) = y1 y2 = y1 + y2 = 0


1
0
 y T ∂g (x∗ ) = y1 y2

3
= −y2 = 0


∂x −1
Ce qui nous donne

y1 = y2 = 0.
Le troisième plan : La deuxième et la troisième contrainte sont passives.

T ∂g1 ∗
1
y (x ) = y1 y2 = y1 + y2 = 0
∂x 1
D’où
y1 = −y2 .
Au troisième plan pseudo-stationnaire, la forme quadratique (4.69) est
définie négative. Donc d’après le théorème 4.3.15, ce plan ne peut être
la solution du problème. La solution serait parmi les deux premiers
plans.
Les deux premiers plans vérifient le théorème 4.3.14 mais ne vérifient
pas le théorème 4.3.15.
La solution du problème sera trouvée en comparant les valeurs de la fonction
f. √
l2
Au premier plan, f (x∗ ) = − 16 , au second plan f (x∗ ) = − 363 l2 .
Donc le plan optimal est
x∗1 = 0, x∗2 = l .

4.4 Exercices
Exercice 4.4.1. Considérons le problème de recherche du point de la parabole
y = 15 (x − 1)2 le plus proche du point (x, y) = (1, 2), dans le sens de norme
Euclidienne.
1. Modéliser ce problème en un programme de minimisation avec contraintes ;
2. Trouver tous les points de Karush-Kuhn-Tucker (KKT),
3. Déterminer les points correspondant aux solutions optimales.
4.4 Exercices 93
Exercice 4.4.2. Résoudre graphiquement le problème suivant :

min f (x1 , x2 ) = x1 + 2x2 ,
x2 − x31 − 1 ≤ 0, x2 ≥ 1.
Peut-on résoudre ce problème par la règle des multiplicateurs de Lagrange ?

Justifier. votre réponse.
Exercice 4.4.3. Considérer le problème de minimisation avec contraintes sui-
vant : 

 min (x1 − 23 )2 + (x2 − 18 )2 ,
 1 − x1 − x2 ≥ 0,


1 − x1 + x2 ≥ 0,
1 + x1 − x2 ≥ 0,




1 + x1 + x2 ≥ 0.

1. Résoudre graphiquement ce problème ;

2. Trouver le point de Karush-Kuhn-Tucker associé à ce problème ;
3. Dire si ce point de KKT correspond à une solution locale ou globale du
problème, justifier.
Exercice 4.4.4. Considérer le problème de minimisation avec contraintes sui-
vant : 
 min f (x1 , x2 , x3 , x4 ),
x1 + x23 − x4 x5 = 0,
−x2 + x4 + x23 = 0.

1. Peut-on résoudre ce problème par la méthode d’élimination ?

2. Si oui, donner les étapes de l’algorithme. Sinon proposer un autre al-
gorithme en donnant ses étapes.
Euclidienne.
Exercice 4.4.6. Soit la fonction
f (x) = f (x1 , x2 ) = x21 + x22 − 8x1 − 10x2 .

4.4 Exercices 94
1) Quel est le point minimum global ?

2) Résoudre graphiquement le problème (P ) suivant :
f (x) −→ min
sous les contraintes
3x1 + 2x2 ≤ 6, x1 ≥ 0, x2 ≥ 0.
3) Formuler le système d’optimalité de KKT pour (P ).

4) Calculer alors les valeurs des paramètres correspondant à la solution op-
timale de (P ) trouvée précédemment.
Exercice 4.4.7. On considère le programme quadratique convexe suivant :

 F (x) = 6x1 + 4x2 − 13 − x21 − x22 → max,
Sous x1 + x2 ≤ 3,
x1 ≥ 0, x2 ≥ 0.

– Résoudre le problème graphiquement.

– Donner les conditions d’optimalité Karush-Kuhn-Tucker pour ce problème.
– Trouver le point de Karush-Kuhn-Tucker puis déduire le point opti-
mum.
Exercice 4.4.8. On considère le programme quadratique convexe suivant :

 F (x) = (1/2)xT Dx + cT x → min,
Sous Ax ≥ b,
Ãx = b̃,

où D est symétrique et semi-définie positive, c ∈ Rn .

1. Donner les conditions de Karush-Kuhn-Tucker (KKT) correspondantes
au problème.
2. Donner la condition sous laquelle le point de KKT est unique.
3. Donner le problème dual de ce problème.
4. Donner le théorème fort de la dualité appliqué à ce problème.
Exercice 4.4.9. Dans cet exercice, on étudie une méthode de minimisation
sans contraintes d’une fonction quadratique de la forme : f (x) = 21 xT Ax −
xT b.
4.4 Exercices 95
Définition 4.4.1. On dit que les vecteurs di , i = 0, . . . , n − 1 sont conjugués

par rapport à une matrice symétrique définie positive A si :∀i, j ∈ {i =
0, . . . , n − 1}, i 6= j ⇒ dTi Adj = 0.
• On note {di , i = 0, . . . , n − 1} une famille quelconque de vecteurs
conjugués par rapport à une matrice symétrique définie positive A de Rn×n .
On se donne par ailleurs un vecteur b ∈ Rn .
Soit un vecteur initial x0 ∈ Rn arbitraire.
A l’étape (k +1), supposant construits les vecteurs x1 , x2 , . . . , xk , ce qui sous-
entend que les vecteurs (Axl − b), l = 0, . . . , k − 1 sont tous différents de zéro,
deux cas peuvent se présenter :
– ou bien Axk − b = 0 et l’algorithme est terminé,
dT .(Ax −b)
– ou bien Axk − b 6= 0, auquel cas, on définit le nombre ρk = k dT Adkk ,
k
puis le vecteur xk+1 = xk − ρk .dk .
1. Justifier le choix de ρk .
2. En supposant que Axk − b 6= 0, ∀k = 1, . . . , n − 1, exprimer xl , pour l =
1, . . . , n en fonction de x0 , (ρi , i = 0, . . . , n − 1) et (di , i = 0, . . . , n − 1).
3. Montrer que dTk Axk = dTk Ax0 , ∀k = 0, . . . , n − 1.
4. – Calculer dTk (Axn − b).
– Déduire que xn est la solution du système Ax = b.
– Que peut-on dire sur la convergence de la méthode.
5. Appliquer cet algorithme pour résoudre le problème d’optimisation sui-
vant :
3 1
min 2 f (x1 , x2 ) = (x1 − )2 + (x2 − )2 .
(x1 ,x2 )∈R 2 8
6. Que devient la solution optimale si la fonction objectif est soumise aux
contraintes suivantes :

1 − x1 − x2 ≥ 0, 1 − x1 + x2 ≥ 0,
1 + x1 − x2 ≥ 0, 1 + x1 + x2 ≥ 0.
Exercice 4.4.10. Soit la fonction f (x) = f (x1 , x2 ) = x21 + x22 − 8x1 − 10x2 .
1) Quel est le point minimum global ?
2) Résoudre graphiquement le problème (P ) suivant :

f (x) −→ min,
3x1 + 2x2 ≤ 6, x1 ≥ 0, x2 ≥ 0.
4.4 Exercices 96
3) Formuler le système d’optimalité de Karush-Kuhn-Tucker pour (P ).

4) Calculer alors les valeurs des paramètres correspondant à la solution op-
timale de (P ) trouvée précédemment.
Exercice 4.4.11. On considère la fonction f définie sur R2 par
f (x, y) = x2 + y 2 + xy.
On note
D = {(x, y) ∈ R2 , x2 + y 2 ≤ 1 et x + y ≥ 1}.
– Montrer que f est strictement convexe sur R2 et qu’elle possède un
unique minimum sur D.
– En écrivant les relations de KKT, déterminer le point où f atteint son
minimum sur D.
Exercice 4.4.12. Soient m, n ∈ N∗ avec n ≥ 2, A ∈ Mn (R) une matrice
symétrique et définie positive, B ∈ Mm,n (R) et d ∈ Rn .
On considère la fonction f : Rn → R donnée par
1
f (x) = xT Ax − dT x, ∀x ∈ Rn
2
et l’ensemble des contraintes C
C = {x ∈ Rn : Bx = 0}.
– Montrer que C 6= ∅ et qu’on peut écrire C comme un ensemble donné

par 2m inégalités larges (à préciser).
– Montrer l’existence et l’unicité d’un point de minimum de f sur C ;
dans la suite nous notons par x∗ ce point de minimum.
– Montrer qu’il existe λ∗ ∈ Rm tel que le système suivant soit satisfait :
Ax∗ − d + B T λ∗ = 0

Bx∗ = 0
Exercice 4.4.13. Trouver le maximum de la fonction f (x1 , x2 ) = x1 x2 contrainte

au disque d’inéquation
1 − x21 − x22 ≥ 0.
4.4 Exercices 97
Exercice 4.4.14. On considère le problème suivant :


 min f (x1 , x2 ) = −2x1 + x2
(1 − x1 )3 − x2 ≥ 0,
x2 + 0.25x21 − 1 ≥ 0.

La solution optimale est x∗ = 0 .

Les conditions de KKT sont-elles satisfaites ?

Exercice 4.4.15. 1. Analyser le problème suivant :

min f (x1 , x2 ) = x1 + x2 ,
(4.70)
x21 + x22 = 2.
Trouver le point de KKT.

2. Analyser le problème suivant :

min f (x1 , x2 ) = x1 + x2 ,
2 − x21 − x22 ≥ 0.
Comparer avec (4.70).

3. Le problème à analyser est :

 min f (x1 , x2 ) = x1 + x2 ,
2 − x21 − x22 ≥ 0,
x2 ≥ 0.

Résoudre ce problème.
Exercice 4.4.16. Maximiser la fonction numérique f (x, y), sous la contrainte
g(x, y) = 0, lorsque :
1/ f (x, y) = xy, g(x, y) = x + 4y–16.
2/ f (x, y) = x2 y, g(x, y) = 2x2 + y 2 –3.
Exercice 4.4.17. Résoudre le problème suivant :

 min x21 + x22 + x23 ,
x1 + x2 + x3 = 3,
2x1 − x2 + x3 ≤ 5

4.4 Exercices 98
Exercice 4.4.18. (Problème de Kepler)

Inscrire dans l’ellipsoı̈de
2
y2 z2

3 x
E = (x, y, z) ∈ R / 2 + 2 + 2 = 1
a b c
le parallélépipède de volume maximal dont les arêtes sont parallèles aux axes.
Exercice 4.4.19. (Problème de Tartaglia) Décomposer le nombre 8 en deux
parties positives p1 , p2 de sorte que le produit de leur produit par leur
différence soit maximale.
Chapitre 5
Les méthodes numériques pour

l’optimisation avec contraintes
5.1 Méthode par élimination


min f (x),
(5.1)
Ax − b = 0
où f : Rn → R, A est une matrice m × n de rang plein, b ∈ Rm .
On suppose, sans perte de généralité, que les m premières colonnes de A sont
linéairement indépendantes.

On pose A = B R avec B est une m × n-matrice inversible, R est une
T
m × (n − m)-matrice, x = xB xR , avec xB ∈ Rm et xR ∈ Rn−m .
Le problème (5.1) devient alors

min f (xB , xR ),
(5.2)
BxB + RxR = b.
Pour satisfaire les contraintes de (5.2), il faut que
xB = B −1 (b − RxR ).
Le problème (5.2) devient alors le problème d’optimisation sans contraintes :
min F (B −1 (b − RxR ), xR ),

(5.3)
xR ∈ Rn−m .
99
5.1 Méthode par élimination 100
On a si (x∗B , x∗R ) est solution optimale de (5.1), x∗R est solution optimale de
(5.3).
Exemple 5.1.1. On considère le problème suivant :

 sin(x1 + x2 ) + x23 + 13 (x4 + x45 + x26 ) → min,
8x1 − 6x2 + x3 + 9x4 + 4x5 = 6,
3x1 + 2x2 − x4 + 6x5 + 4x6 = −4.

On réorganise la matrice A tel que

T
xT = x3 x6 x1 x2 x4 x5 .

1 0 8 −6 9 4
A= B R = ,
0 4 3 2 −1 6
avec
1 0
B= ,
0 4

8 −6 9 4
R= .
3 2 −1 6
La matrice B est diagonale,

−1 1 0
B = .
0 14
On obtient

x3 −1 6 − 8x1 + 6x2 − 9x4 − 4x5
xB = = B (b − RxR ) =
x6 −1 − 43 x1 − 12 x2 + 14 x4 − 32 x5
En remplaçant x3 et x6 dans la fonction objectif, on obtient le problème

sans contraintes suivant :
2 1
sin(x 1 + x2 ) + (6 − 8x1 + 6x2 − 9x4 − 4x 5) + 3
1 3 1 1 3

x4 + x45 − 2 + 8 x1 + 4 x2 − 8 x4 + 4 x5 → min,
(x1 , x2 , x4 , x5 ) ∈ R4 .
Remarque 5.1.1. On peut choisir autrement B et R mais il faut veiller à

choisir B et R de telle sorte à faciliter les calculs et B inversible.
5.1 Méthode par élimination 101


 f (x1 , x2 ), x3 , x4 ) → min,
x1 + x23 − x4 x3 = 0, (5.4)
−x2 + x4 + x23 = 0.

Les contraintes sont non linéaires.
x1 = −x23 + x4 x3
x2 = x4 + x23 .
On définit
h(x4 , x3 ) = f (−x23 + x4 x3 , x4 + x23 , x3 , x4 ).
Le problème (5.4) devient un problème sans contraintes comme suit :
min f (−x23 + x4 x3 , x4 + x23 , x3 , x4 ).

x4 , x3 ∈ R.
Remarque 5.1.2. Le danger de cette méthode d’élimination est illustré dans

l’exemple suivant appelé problème de Fletcher.
Exemple 5.1.3. Considérons le problème suivant :

min x2 + y 2
(x − 1)3 = y 2
Le graphe montre que la solution optimale est (1, 0).

On va essayer de résoudre le problème par élimination. On otient
h(x) = x2 + (x − 1)3 .
On voit bien que h(x) → −∞ quand x → −∞. On peut déduire que le

problème n’admet pas de solution.
Le problème, par cette approche, est qu’on ignore que (x − 1)3 = y 2 impose
que x ≥ 1. Cette contrainte doit tenue en considération.
Remarque 5.1.3. Cet exemple montre la limite de la méthode dans le cas de
contraintes non linéaires. En général, pour utiliser cette méthode, on doit
linéariser d’abord les contraintes non linéaires.
5.2 Méthodes de pénalisation 102
5.2 Méthodes de pénalisation

5.2.1 Principe de la méthode
Le principe est de remplacer la fonction objectif originale du problème
par une fonction de pénalité. La fonction de pénalité est composée de :
– la fonction objectif originale du problème d’optimisation avec contraintes,
et
– un terme supplémentaire pour chaque contrainte.
Ce terme est positif si le point courant x viole les contraintes et nul
dans le cas contraire.
Donc on remplace le problème avec contraintes suivant :

f (x) → min,
(5.5)
x ∈ C ⊂ Rn ,
par un problème sans contraintes suivant :
f (x) + µ1 α(x) → min,

(5.6)
x ∈ Rn ,
où α : Rn → R est une fonction de pénalisation des contraintes et µ > 0.

Le but est de trouver des fonctions α telles que les problèmes (5.5) et (5.6)
soient équivalents.
Nous supposons que α vérifie les propriétés suivantes :
1. La fonction α est continue sur Rn .
2. ∀x ∈ Rn , α(x) ≥ 0.
3. α(x) = 0 ⇔ x ∈ C.
Nous donnons quelques exemples de pénalisation pour différentes contraintes :
1. Pour une contrainte x ≥ 0, on a la fonction α(x) = kx− k2
2. Pour une contrainte h(x) = 0, on a la fonction α(x) = kh(x)k2
3. Pour une contrainte g(x) ≥ 0, on a la fonction α(x) = kg(x)− k2
où k − k est la norme euclidienne de Rn et x− = max(−x, 0).

égalités
Dans le cas de problème d’optimisation avec contraintes de type égalité,
la fonction pénalité utilisée est la fonction quadratique.
Le problème à résoudre est le suivant :

f (x) → min,
(5.7)
gi (x) = 0, 1 ≤ i ≤ m.
La fonction quadratique de pénalisation q(x, µ) pour (5.7) est :

m
1 X 2
q(x, µ) = f (x) + g (x) (5.8)
2µ i=1 i
où µ > 0 est le paramètre de pénalisation.

En tendant µ vers zéro, nous pénalisons les violations des contraintes.
Le principe est donc : on considère une séquence de valeurs de {µk } avec
µk → 0, k → +∞ et on calcule le minimum xk de q(x, µk ) pour chaque k.

min x1 + x2
x21 + x22 = 2.
La fonction de pénalisation quadratique associée est :

1 2
q(x, µ) = x1 + x2 + (x + x22 − 2)2 .
2µ 1
Pour µ = 1 , on trouve le minimum de q est (−1.1; −1.1) ;
Pour µ = 0.1 , on trouve le minimum de q est (−1; −1) ;
La solution du problème est donc (−1; −1).

mixtes
Considérons le problème d’optimisation avec contraintes mixtes suivant :

 f (x) → min,
gi (x) = 0, 1 ≤ i ≤ m, (5.9)
hj (x) ≥ 0, 1 ≤ j ≤ l.

On définit la fonction q de pénalisation comme suit :

m l
1 X 2 1 X −
q(x, µ) = f (x) + gi (x) + (h (x))2 , (5.10)
2µ i=1 2µ j=1 j
où y − = max(−y, 0).
5.2.4 Algorithme de la méthode de pénalisation qua-

dratique
Soient µ0 > 0, 0 > 0, et le point initial xs0 donnés.
Tant que k∇q(x, µk )k > k faire

– Trouver le minimum approximatif de q(., µk ), en partant de xsk ; soit
le minimum xk ;
– Choisir le nouveau paramètre de pénalisation µk+1 ∈ [0, µk ].
– Choisir le nouveau point xsk+1

Fin Tant que
Théorème 5.2.1. Supposons que chaque solution xk est un minimum global
exact de q(x, µk ) dans l’algorithme précédent et que µk → 0. Alors, chaque
point x∗ limite de la séquence {xk } est une solution du problème (5.7).
Démonstration. Soit x une solution globale du problème (5.7), alors
f (x) ≤ f (x), ∀x : gi (x) = 0, 1 ≤ i ≤ m.
Puisque xk minimise q(., µk ) pour chaque k, alors on a
q(xk , µk ) ≤ q(x, µk ),
d’où
m m
1 X 2 1 X 2
f (xk ) + g (xk ) ≤ f (x) + g (x) = f (x) (5.11)
2µk i=1 i 2µk i=1 i
alors m
X
gi2 (xk ) ≤ 2µk (f (x) − f (xk )). (5.12)
i=1
∗
Supposons que x est un point limite de {xk }, donc il existe une sous-séquence
K telle que
lim xk = x∗ .
k∈K,k→+∞
En passant aux limites dans (5.12), k → +∞, k ∈ K, on obtient

m
X m
X
gi2 (x∗ ) = lim gi2 (xk ) ≤ lim 2µk (f (x) − f (xk )) = 0;
k∈K k∈K
i=1 i=1
d’où, gi (x∗ ) = 0, 1 ≤ i ≤ m. x∗ est alors réalisable.

D’un autre côté, ayant k → ∞, k ∈ K dans l’équation (5.11), µk non négative
et gi2 (xk ), 1 ≤ i ≤ m non négatives, on a
m
1 X 2
f (x∗ ) ≤ f (x∗ ) + lim gi (xk ) ≤ f (x).
k∈K 2µk
i=1
Ayant x∗ réalisable et f (x∗ ) ≤ f (x), alors on conclut que x∗ est un minimum

global.
Théorème 5.2.2. Si les k de l’algorithme précédent vérifient
lim k = 0
k→∞
et les paramètres de pénalisation vérifient µk → 0, alors tous les points limites

x∗ de la séquence {xk } pour lesquelles les gradients ∇gi (x∗ ) sont linéairement
indépendants, on a x∗ est un point de Karush-Kuhn-Tucker du problème
(5.7). Pour ces points, on a une infinité de sous-séquence K tel que
lim xk = x∗ ,
k∈K
(5.13)
lim −gi (xk )/µk = λ∗i , 1 ≤ i ≤ m,
k∈K
où λ∗ est le vecteur multiplicateur qui satisfait les conditions de KKT.
Démonstration. Soit q(xk , µk ) = f (xk ) + 2µ1k m 2

P
i=1 gi (xk ), d’où
m
X gi (xk )
∇x q(xk , µk ) = ∇f (xk ) + ∇gi (xk ). (5.14)
i=1
µk
En appliquant le critère d’arrêt de l’algorithme, on obtient :

m
X gi (xk )
k∇f (xk ) + ∇gi (xk )k ≤ k (5.15)
i=1
µk
d’où m
X
k gi (xk )∇gi (xk )k ≤ µk (k + k∇f (xk )k) (5.16)
i=1
Quand k → ∞ pour k ∈ K, on a
k + k∇f (xk )k → k∇f (x∗ )k
d’où, comme µk → 0, on a
µk (k + k∇f (xk )k) → 0.
On obtient alors m
X
gi (x∗ )∇gi (x∗ ) = 0. (5.17)
i=1
Par hypothèse, on a ∇gi (x∗ ), 1 ≤ i ≤ m linéairement indépendants et

gi (x∗ ) = 0, 1 ≤ i ≤ m, d’où x∗ est réalisable. On va maintenant démontrer
la condition de KKT et montrer que la limite (5.13) du théorème 5.2.2 se
produit.
On dénote la matrice des gradients des contraintes par A(x),
A(x) = (∇gi (x))1≤i≤m (5.18)
et
g(xk )
λk = − ,
µk
on a alors comme dans (5.15) :

T −gi (xk )
A(xk ) λk = (∇gi (x)) = ∇f (xk ) − ∇x q(xk , µ) (5.19)
µk 1≤i≤m
k∇x q(xk , µ)k ≤ k .

Si on multiplie l’équation (5.19) par A(xk ), on a
−1
λk = A(xk )AT (xk ) A(xk ) (∇f (xk ) − ∇x q(xk , µ)) .
D’où −1
lim λk = λ∗ = A(x∗ )AT (x∗ ) A(x∗ )∇f (x∗ ).
k∈K
Conformément à l’équation (5.15), on a
∇f (x∗ ) − AT (x∗ )λ∗ = 0,
d’où λ∗ satisfait les conditions de KKT. Donc x∗ est un point de KKT.
5.2.5 Quelques exemples corrigés


 min x,
x2 ≥ 0,
x + 1 ≥ 0,

pour lequel x∗ = −1 est la solution. Ecrire la fonction de pénalisation P (x, µ)

associée à ce problème et trouver les minimums locaux.
5.3 Méthode du gradient projeté 108
Montrer que pour chaque séquence {µk }k telle que µk → 0, il existe une
séquence de minimums locaux x(µk ) qui convergent vers -1.
Solution :
On définit la fonction de pénalisation P (x, µ) comme suit :
1 1
P (x, µ) = x + ((x2 )− )2 + ((x + 1)− )2
2µ 2µ
avec
(x2 )− = max(0, −x2 ) = 0, ∀x,
(x + 1)− = max(0, −1 − x)
– Si x ≥ −1, alors (x + 1)− = 0. On a alors P (x, µ) = x.
– Si x < −1, alors (x + 1)− = −x − 1. On a alors P (x, µ) = x + 2µ
1
(x + 1)2 .
Dans les deux cas, on trouve que min P (x, µ) est atteint pour x → −1.
Exemple 5.2.3. Vérifier que les conditions de KKT du problème suivant :

 min f (x),
l ≤ x ≤ u,
x ∈ Rn ,

sont équivalentes à la condition :
P[l,u] ∇f (x) = 0,
où P[l,u] est l’opérateur de projection sur [l, u].

Solution :
Rappelons qu’on définit P[l,u]g , la projection du vecteur g ∈ Rn sur [l, u],
comme suit :

 min(0, gi ) si xi = li ,
(P[l,u] )gi = gi si xi ∈ (li , ui ),
max(0, gi ) si xi = u i .

5.3 Méthode du gradient projeté

Dans le cas d’optimisation sans contraintes, l’algorithme du gradient
s’énonce comme suit :
(0)
x ∈ Rn un point initial donné,
x(k+1) = x(k) + ρ(k) d(k) , d(k) ∈ Rn \{0}, ρ(k) ∈ R+∗ ,
5.3 Méthode du gradient projeté 109
où ρ(k) et d(k) sont choisis de telle sorte que :
f (x(k+1) ) ≤ f (x(k) ).
Dans le cas avec contraintes, on ne peut pas être sûr que x(k) reste sur l’en-
semble des contraintes C. Il est donc nécessaire de se ramener sur C, et ceci
grâce à une projection sur C, l’opérateur associé étant noté ΠC où C est
convexe fermé et non vide :
C : Rn → C
x → ΠC (x).
On obtient ainsi l’algorithme du gradient projeté, qui est identique à celui
du gradient à la projection près :
Initialisation :
k = 0, choix de x(0) et > 0.
Itération k :
Tant que le critère d’arrêt est non satisfait :
b(k+1) = x(k) − ρ(k) ∇f (x(k) )
x
x(k+1) = ΠC x
b(k+1)
k =k+1
Fin tant que
Théorème 5.3.1 (Convergence). Soit f une fonction de classe C 1 définie de
Rn dans R. On suppose que f est elliptique de dérivée lipschitzienne. Alors,
2α
si on choisit le pas ρ(k) dans un intervalle [β1 , β2 ] tel que 0 < β1 < β2 < M 2
(où α et M sont respectivement les constantes d’elliplicité
(∇f (x) − ∇f (y))T (x − y) ≥ αkx − yk2 )
et d’inégalité lipschitzienne
(kf (x) − f (y)k ≤ M kx − yk).
La suite (x(k) )k définie par la méthode du gradient projeté converge vers la

solution du problème.
Exemple 5.3.1. – Pour des contraintes de type x ≥ 0, l’opérateur de pro-
jection est
ΠC (x) = max(xi , 0)i=1,··· ,m .
5.4 Méthode Lagrange-Newton pour des contraintes égalité 110
– Pour des contraintes de type a ≤ x ≤ b, l’opérateur de projection est


 b, si x > b,
ΠC (x) = x, si a ≤ x ≤ b,
a, si x < a.

5.4 Méthode Lagrange-Newton pour des contraintes

égalité
5.4.1 Cas d’un problème quadratique avec des contraintes
affines égalités
Considérons un problème quadratique avec contraintes affines de type
égalité :
min 21 xT Qx − cT x,

Ax = b
où Q est une matrice carrée de R d’ordre n × n, c un vecteur de Rn , A une
matrice de R d’ordre m × n et b un vecteur de Rm .
Les conditions de KKT de premier ordre nous donnent
∇x ( 12 xT Qx − cT x + λT (Ax − b)) = 0,

Ax = b,
où λ ∈ Rm est le vecteur multiplicateur de Lagrange associé aux contraintes

Ax = b.
Par conséquent, le couple optimal (x∗ , λ∗ ) est la solution du système :
Qx∗ − c + AT λ∗ = 0,

Ax∗ = b.
Ce système peut s’écrire comme suit :

∗
Q AT x c
= .
A 0 λ∗ b

Q AT
Si la matrice est inversible, le système admet une solution que
A 0
l’on peut calculer par une des méthodes de résolution des systèmes linéaires.
5.5 Méthode de Newton projetée 111
5.4.2 Cas d’un problème non quadratique

Considérons un problème non quadratique suivant :

min f (x),
g(x) = 0
où f : Rn → R et g : Rn → Rm sont de classe C 2 .

Les conditions de premier ordre de KKT s’écrivent comme suit :

∇x L(x, λ) = 0,
g(x) = 0,
où λ ∈ Rm et L(x, λ) = f (x) + λT g(x) est le lagrangien du problème. On

résoud ce système d’équations non linéaires par la méthode de Newton. C’est
l’algorithme de Lagrange-Newton énoncé comme suit :
– Initialisation : k = 1, Choix de (x(0) , λ(0) ) ∈ Rn × Rm .
– Itération k
– Tant que le critère d’arrêt est non satisfait, faire
Résoudre le système linéaire suivant :
2 (k)
∇x,x L(x(k) , λ(k) ) ∇x g(x(k) )T d ∇x L(x(k) , λ(k) )T
=−
∇x g(x(k) ) 0 y (k) g(x(k) )
où ∇2x,x L(x(k) , λ(k) ) est le hessien de L par rapport à x.

Poser
x(k+1) = x(k) + d(k)
λ(k+1) = λ(k) + y (k)
k = k + 1.
– Fin tant que
5.5 Méthode de Newton projetée

5.5.1 Cas de contraintes de type x ≥ 0

min f (x)
(5.20)
x≥0
5.5 Méthode de Newton projetée 112
où f est de classe C 2 sur Rn . Si H (k) désigne la matrice hessienne de f en

(k)
x , une itération de la méthode de Newton est de la forme suivante :
x(k+1) = x(k) − [H (k) ]−1 (∇f (x(k) ).
On peut affiner en introduisant un pas α(k) > 0, ce qui donne :
x(k+1) = x(k) − α(k) [H (k) ]−1 (∇f (x(k) ).
Si on projete sur l’ensemble des contraintes, on obtient :

+
= x(k) − α(k) [H (k) ]−1 (∇f (x(k) )
(k+1)
x
où x+ = max(xi , 0)1≤i≤n .

On a le théorème de convergence suivant :
Théorème 5.5.1. On suppose que f est convexe et est de classe C 2 et que le
∂f
problème (5.20) a une solution unique x∗ vérifiant ∂x i
(x∗ ) > 0, ∀i ∈ Ia (x∗ ),
∗
(Ia (x ) est l’ensemble des indices actifs). On suppose de plus que l’on peut
trouver m1 et m2 deux réels strictement positifs tels que :
m1 kzk2 ≤ z T ∇2 f (x)z ≤ m2 kzk2 ,
dans chacun des cassuivants :

– pour tout z ∈ x/f (x) ≤ f (x(0) ) , d’une part ;
– x dans une boule centrée en x∗ et z 6= 0 tel que zi = 0 pour i ∈ Ia (x∗ ),
d’autre part.
Alors la suite x(k) engendrée par l’algorithme converge vers x∗ et le taux de
convergence est superlinéaire. On peut alors généraliser l’algorithme précédent
au problème à contraintes bornées.
5.5.2 Cas de contraintes de bornes

Dans ce cas, le problème se présente comme suit :

min f (x)
(5.21)
a≤x≤b
Nous appliquons les itérés de la méthode de Newton projetée comme dans le
cas du problème (5.20), en utilisant la projection suivante :
Proj
= x(k) − α(k) [H (k) ]−1 (∇f (x(k) )
(k+1)
x
5.6 Méthode d’Uzawa 113
où pour tout z ∈ Rn , z Proj = ΠC (z) désigne le vecteur :


 bi si bi ≤ zi ,
Proj
[z]i = zi si ai ≤ zi ≤ bi ,
ai si zi ≤ ai .

5.6 Méthode d’Uzawa

L’idée générale de la méthode est de considérer le Lagrangien L au lieu
de la fonction f . Ce choix est motivé par, au moins, deux raisons :
– La fonction de Lagrange L englobe la fonction f et les cotraintes g et
h ; donc L représente bien le problème ;
– Ensuite, nous avons vu qu’une condition nécessaire du premier ordre
pour que x∗ soit un minimum de f sous les contraintes est que x∗
(associé aux multiplicateurs de Lagrange) soit un point critique de L.
Notre problème à considérer est :

 min f (x)
hj (x) = 0 1 ≤ j ≤ l,
gi (x) ≤ 0 1 ≤ i ≤ m.

Le Lagrangien du problème est :

l
X m
X
L(x, µ, λ) = f (x) + µj hj (x) + λi gi (x).
j=1 i=1
Définition 5.6.1. On appelle point-selle de L sur Rn × Rl × R+m tout triplet

(x∗ , µ∗ , λ∗ ) ∈ Rn × Rl × R+m vérifiant l’équation suivante :
L(x∗ , µ, λ) ≤ L(x∗ , µ∗ , λ∗ ) ≤ L(x, µ∗ , λ∗ ), ∀(x, µ, λ) ∈ Rn × Rl × R+m .
On a alors le résultat suivant :

Théorème 5.6.1. Supposons que f, h et g soient des fonctions de classe C 1
et que le triplet (x∗ , µ∗ , λ∗ ) ∈ Rn × Rl × R+m soit un point selle de L sur
Rn × Rl × R+m . Alors, ce triplet vérifie les conditions de KKT.
Théorème 5.6.2. Supposons que f, h et g soient des fonctions convexes et
de classe C 1 . Alors, le triplet (x∗ , µ∗ , λ∗ ) ∈ Rn × Rl × R+m est un point selle
de L sur Rn × Rl × R+m si et seulement s’il vérifie les conditions de KKT.
5.6 Méthode d’Uzawa 114
L’algorithme d’Uzawa se base sur ces théorèmes. Il consiste à chercher un

triplet (x∗ , µ∗ , λ∗ ) ∈ Rn × Rl × R+m vérifiant les conditions de KKT de la
façon suivante :
1. Pour (µ∗ , λ∗ ) fixé dans Rl × R+m , nous allons chercher le minimum sur
Rn de la fonction définie ainsi :
x → L(x, µ∗ , λ∗ ).
2. Pour x∗ fixé sur Rn , on cherche le maximum sur Rl ×R+m de la fonction

définie ainsi :
(µ, λ) → L(x∗ , µ, λ).
En faisant ces deux calculs simultanément, on obtient l’algorithme d’Uzawa
suivant :
Initialisation – Poser k = 0 ;
– Choisir µ(0) ∈ Rl et λ(0) ∈ R+m
Itération k : Tant que le critère d’arrêt n’est pas satisfait, faire
a) Calculer x(k) ∈ Rn solution du problème :

min L(x, µ(k) , λ(k) )
x ∈ Rn .
b) Calculer µ(k+1) et λ(k+1) comme suit :

(
(k+1) (k)
µj = µj + ρhj (x(k) ), 1 ≤ j ≤ l,
(k+1) (k) (k)
λi = max(0, λi + ρgi (x )), 1 ≤ i ≤ m
où ρ > 0 est un réel fixé.
Théorème 5.6.3 (Convergence). On suppose que f est de classe C 1 et ellip-

tique, que h est affine, g est convexe de classe C 1 et que g et h sont lipschit-
ziennes. On suppose de plus que la fonction de Lagrange L possède un point-
selle (x∗ , µ∗ , λ∗ ) sur Rn × Rl × R+m . Alors, il existe ρ1 , ρ2 avec 0 < ρ1 < ρ2
tels que ∀ρ ∈ [ρ1 , ρ2 ] la suite (x(k) )k>0 générée par l’algorithme converge vers
x∗ .
5.7 Exercices 115
5.7 Exercices
Exercice 5.7.1. Expliquer si les problèmes suivants admettent des solutions
optimales : 
 min
 x1 + x2 ,
x1 + x22 = 0,
2

(5.22)

 0 ≤ x1 ≤ 1,
0 ≤ x2 ≤ 1.


 min x1 + x2 ,
x2 + x22 ≤ 1, (5.23)
 1
x1 + x2 = 3.

min x1 x2 ,
(5.24)
x1 + x2 = 2.
Exercice 5.7.2. Montrer que dans le problème de Fletcher, si on élimine x en
termes de y, alors la bonne solution du problème est obtenue en résolvant le
problème sans contraintes.
Euclidienne.
Exercice 5.7.4. Le problème de recherche de la plus courte distance entre
un point x0 ∈ Rn et l’hyperplan d’équation {x\Ax = b} où les lignes de
la matrice A sont linéairement indépendantes et b, un vecteur colonne de
taille n. Ce problème peut s’écrire comme un problème de programmation
quadratique :
min 12 (x − x0 )T (x − x0 ),

Ax = b.
– Montrer que le multiplicateur de Lagrange, à l’optimum est :
λ∗ = (AAT )−1 (Ax0 − b).
– Montrer que la solution optimale est :
x∗ = x0 + AT (AAT )−1 (b − Ax0 ).

5.7 Exercices 116
– Montrer que, dans le cas où A est un vecteur ligne, la plus petite dis-
tance entre x0 et l’hyperplan vaut :
kb − Ax0 k
d= .
kAk
Exercice 5.7.5. Considérons le problème de minimisation suivant :
1

min 1+x 2,
x≥1
Ecrire la fonction de pénalisation P (x, µ) associée à ce problème, puis montrer
que P (x, µ) est non bornée pour toute valeur positive de µ.
Exercice 5.7.6. On considère la fonctionnelle f définie sur R2 par : f (x, y) =
2x2 +3xy+2y 2 . On appelle Q le quadrant défini par : Q = x ≤ − 12 , y ≤ − 12 .

– Donner les étapes de l’algorithme du gradient projeté appliquées au

problème de minimisation suivant :

min f (x, y),
(x, y) ∈ Q.
– Donner les étapes de l’algorithme de Newton projeté appliquées à ce
problème.
– Donner les étapes de l’algorithme Uzawa appliquées à ce problème.
Exercice 5.7.7. En utilisant la méthode d’élimination, résoudre les problèmes
suivants :
– min f (x, y) = xy, sous x − y = 1,
– min f (x, y) = x2 + y 2 , sous x + y = 2,
– min f (x, y) = (x − 3)2 + (y + 1)2 , sous 2x − y = 1.
1

min 1+x 2,
x ≥ 1.
Ecrire la fonction de pénalisation Q(x, µ) associée à ce problème, puis montrer
que Q(x, µ) est non bornée pour toute valeur positive de µ.

 min x,
x2 ≥ 0,
x + 1 ≥ 0,

5.7 Exercices 117
pour lequel x∗ = −1 est la solution.

Ecrire la fonction de pénalisation Q(x, µ) associée à ce problème et trouver
les minimums locaux. Montrer que pour chaque séquence {µk }k telle que
µk → 0, il existe une séquence de minimums locaux x(µk ) qui converge vers
0.
Exercice 5.7.10. Vérifier que les conditions de KKT du problème suivant :

min f (x),
l ≥ x ≤ u,
sont équivalentes à la condition :
P[l,u] .∇f (x) = 0,
où P[l,u] est l’opérateur de projetion sur [l, u]. Indication : L’opérateur de
projection du vecteur g ∈ Rn sur [l, u] est défini ainsi :

 min(0, gi ), si xi = li ,
(P[l,u] g)i = gi , si xi ∈ [li , ui ],
max(0, gi ), si xi = ui ,

Exercice 5.7.11. Soit (P) le problème d’optimisation suivant :


 min f (x, y) = 3x2 + y 2 + xy − x,
g1 (x, y) = x + y ≤ 0,
g2 (x, y) = 1 − x ≤ 0,

1. Montrer que le point (1, −1) est régulier et qu’il vérifie les conditions
de Karush-Kuhn-Tucker.
2. Pour k ≥ 1 entier et pour tout (x, y) ∈ R2 , on définit la fonction :
fk (x, y) = f (x, y) + k[(g1− (x, y))2 + (g2− (x, y))2 ]
où g1− (x, y) = max(0, x + y) et g2− (x, y) = max(0, 1 − x).

Soit le problème (Pk ) défini : min(x,y)∈R2 fk (x, y).
a) En supposant que x + y > 0 et 1 − x > 0, donner (xk , yk ) la solution
optimale de (Pk ) en fonction de k. Vérifier que pour tout k ≥ 1, on
a xk + yk > 0 et 1 − xk > 0, puis calculer la limite de la suite (xk , yk )
lorsque k tend vers l’infini.
b) Montrer que (g1− (x, y))2 et (g2− )2 sont convexes. En déduire que
fk (x, y) est strictement convexe et que la solution (xk , yk ) trouvée
en a) est l’unique solution de (Pk ). En déduire une solution optimale
de (P).
– Calculer les limites des suites 2kg1 (xk , yk ) et 2kg2 (xk , yk ). Quelles
valeurs retrouve-t-on ?
Indication : Faire attention au calcul de ∇(g1− (x, y))2 et de ∇(g2− (x, y))2
Exercice 5.7.12. On considère le problème suivant où (x1 , x2 ) ∈ R2 :

min f (x1 , x2 ) = 3x21 + 2x22 ,
x1 + x2 ≥ 1,
– Exprimer le problème graphiquement.
– Donner les conditions de Karush-Kuhn-Tucker et les résoudre.
– Sont-elles suffisantes pour l’optimalité ? Justifier votre réponse.
– En déduire la solution du problème.
– Résoudre le problème par la méthode de pénalisation en prenant µk =
1/2k.
– Retrouver le multiplicateur de Lagrange des conditions de Karush-
Kuhn-Tucker.
Exercice 5.7.13. On considère le problème suivant où (x, y) ∈ R2 :

min f (x, y) = y,
x2 + y 2 ≤ 1,
1. Montrer que le point (0, 1) est régulier et qu’il vérifie les conditions de
Karush-Kuhn-Tucker.
2. Pour k ≥ 1 entier et pour tout (x, y) ∈ R2 , on définit la fonction :
fk (x, y) = f (x, y) + k(g − (x, y))2
où g − (x, y) = max(0, x2 + y 2 − 1).
Soit le problème (Pk ) défini : min(x,y)∈R2 fk (x, y).
a) Donner (xk , yk ) la solution optimale de (Pk ) en fonction de k. Vérifier
que pour tout k ≥ 1, on a x2k + yk2 > 1, puis calculer la limite de la
suite (xk , yk ) lorsque k tend vers l’infini.
b) Montrer que (g − (x, y))2 est convexe. En déduire que fk (x, y) est
strictement convexe et que la solution (xk , yk ) trouvée en a) est
l’unique solution de (Pk ). En déduire une solution optimale de (P).
– Calculer la limite de la suite 2kg(xk , yk ). Quelle valeur retrouve-t-on ?
118
Bibliographie
[1] S. Achmanov. Programmation linéaire. Edition Mir, Moscou, 1984.

[2] H. Bergounioux. Optimisation et contrôle des systèmes linéaires. Dunod
Paris, 2001.
[3] Leonard D. Berkovotz. Convexity and optimization in Rn. JOHN WI-
LEY and SONS, INC., 2002.
[4] P.G. Ciarlet. Introduction à l’analyse numérique matricielle et à l’opti-
misation. Dunod Paris, 1998.
[5] G.B. Dantzig. Applications et prolongements de la programmation
linéaire. Dunod, Paris, 1966.
[6] F. Margot. Composition de polytopes combinatoires : une approche par
projection. Presses polytechniques et universitaires romandes, 1995.
[7] M. Minoux. Programmation mathématique :Théorie et algorithmes,
Tome 1, 2. Collection technique et scientifique des télécommunications,
1983.
[8] S. Radjef. Cours Optimisation sans contraintes, L3 Mathématiques. Uni-
versité USTO MB, 2006.
[9] S. Radjef. Cours Optimisation avec contraintes, L3 Mathématiques. Uni-
[10] S. Radjef. Cours Optimisation convexe, Master 1 Mathématiques. Uni-
[11] R.T. Rockafellar. Convex analysis. Princeton University Press, 1970.
[12] D. De Werra and al. Recherche opérationnelle pour ingénieur I. Press
Polytechniques et universitaires romandes, Lausanne, 2003.
119
View publication stats

PolycopideRadjefSonia PDF

Transféré par

Droits d'auteur :

Formats disponibles

PolycopideRadjefSonia PDF

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

PolycopideRadjefSonia PDF

Transféré par

Droits d'auteur :

Formats disponibles

See discussions, stats, and author profiles for this publication at: https://www.researchgate.

Optimisation : Cours et exercices

Preprint · December 2019

Méthodes constructives d’optimisation et applications View project

The user has requested enhancement of the downloaded file.

Dr RADJEF Epouse DOUAR Sonia

I Optimisation sans contraintes 4

2 Optimisation non linéaire sans contraintes 22

2.4.1 Conditions nécessaires d’optimalité . . . . . . . . . . . 28

3 Les méthodes numériques pour l’optimisation sans contraintes 37

II Optimisation avec contraintes 56

5 Les méthodes numériques pour l’optimisation avec contraintes

Euler :”Rien ne se passe dans le monde qui ne soit la signification d’un

Optimisation sans contraintes

1.2 Vecteurs et matrices

où I = {1, 2, . . . , m} et J = {1, 2, . . . , n} représentent respectivement l’en-

la matrice A se note aussi

1.2.1 Matrices et vecteurs partitionnés

On peut partitionner une matrice d’une manière arbitraire. Par exemple, si

alors on peut partitionner A de la façon suivante :

A = (a1 , a2 , · · · , aj , · · · , an ) = [AB |AN ],

avec AB = A(I,h JBi), AN = A(I, JN ).

1.3 Discussion générale sur les solutions d’un

Le système (1.1) peut s’écrire sous la forme matricielle suivante :

Tout vecteur x vérifiant les équations (1.1) s’appelle solution du système. Le

Lemme 1.3.1. Soit m ≤ n et rang(A) = m. Alors le système Ax = b admet

1.4 Propriétés des formes quadratiques

où xT = (x1 , x2 , · · · , xn ) est un n-vecteur ligne et A = (aij , 1 ≤ i, j ≤ n) est

Pour i 6= j, le coefficient du terme xi xj s’écrit aij + aji . En vertu de

1.4.1 Gradient d’une forme quadratique

La dérivée partielle de F par rapport à chaque variable xj est donnée par :

Par conséquent, le gradient de F (x) est :

∇F (x) = 2Dx. (1.6)

Définition 1.4.3. Soit une fonction réelle de classe C 2 , F : Rn −→ R. Le

 ∂2F ∂2F ∂2F 

Définition 1.4.4. Soit F : Rn −→ R une fonction de classe C 1 . La dérivée

1.4.2 Forme quadratique définie et semi-définie posi-

Définition 1.4.6. F est dite définie négative si xT Dx < 0, ∀x ∈ Rn et x 6= 0.

1.4.3 Critère de Sylvester pour les formes quadratiques

Ce mineur est dit principal si : i1 = j1 , i2 = j2 , · · · , ip = jp , c’est-à-dire s’il

sont appelés mineurs principaux sucessifs. Alors, le critère de Sylvester se

Théorème 1.4.1 (Critère de sylvester). (i) Pour que la matrice D soit

D1 > 0, D2 > 0, · · · , Dn > 0; (1.8)

(ii) Pour que la matrice D soit semi-définie positive (D  0), il est

Remarque 1.4.1. Pour qu’une matrice D soit définie négative (D ≺ 0) ou non

1.4.4 Propriétés des matrices définies et semi-définies

Propriété 1.4.1. Soit la matrice D partitionnée de la manière suivante :

Propriété 1.4.2. Un élément de la diagonale d’une matrice symétrique D

1.5 Éléments d’analyse convexe

1.5.1 Ensembles convexes

– Combinaison affine des points de S si

– Combinaison conique des points de S si

– Combinaison convexe des points de S si

• On définit l’enveloppe conique (respectivement convexe) des points de

λx1 + (1 − λ)x2 = λ(x0 + α1 d) + (1 − λ)(x0 + α2 d)

Comme λα1 + (1 − λ)α2 ≥ 0, alors λx1 + (1 − λ)x2 ∈ S.

1.5.2 Fonctions convexes

Définition 1.5.4. Soit S ⊂ Rn un ensemble non vide et f : S → R. L’en-

Les théorèmes suivants indiquent la relation entre une fonction convexe

(ii) Pour que la matrice D soit semi-définie positive (D 0), il est

∃ > 0 tel que f (x0 ) ≤ f (x), ∀x ∈ Rn , avec kx − x0 k < .