4

7.2 Position du problème et définitions . . . . . . . . . . . . . . . 134

7.3 Formule d’accroissement de la fonction objectif . . . . . . . . . 136
7.4 Critère d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 137
7.5 Critère de suboptimalité . . . . . . . . . . . . . . . . . . . . . 139
7.6 Méthode de résolution . . . . . . . . . . . . . . . . . . . . . . 140
7.6.1 Construction d’une direction d’amélioration adaptée l . 141
7.6.2 Changement de plan . . . . . . . . . . . . . . . . . . . 142
7.6.3 Estimation de suboptimalité . . . . . . . . . . . . . . . 143
7.6.4 Changement de support . . . . . . . . . . . . . . . . . 144
7.6.5 Algorithme de résolution . . . . . . . . . . . . . . . . . 145

8 La dualité 147
8.1 La fonction duale de Lagrange . . . . . . . . . . . . . . . . . . 147
8.1.1 La fonction de Lagrange . . . . . . . . . . . . . . . . . 147
8.1.2 La fonction duale de Lagrange . . . . . . . . . . . . . . 148
8.1.3 Borne sur la fonction duale . . . . . . . . . . . . . . . . 148
8.1.4 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . 149
8.2 Le problème dual de Lagrange . . . . . . . . . . . . . . . . . . 150
8.2.1 Rendre les contraintes duales explicites . . . . . . . . . 151
8.2.2 La dualité faible . . . . . . . . . . . . . . . . . . . . . . 153
8.2.3 La dualité forte . . . . . . . . . . . . . . . . . . . . . . 153
8.3 Interprétation du point-selle (Saddle point) . . . . . . . . . . . 154
8.3.1 Définition des points-selle (ou cols) ; Problème de mini-
maximisation . . . . . . . . . . . . . . . . . . . . . . . 154
8.3.2 Points-selle de lagrangiens . . . . . . . . . . . . . . . . 155
8.3.3 Condition d’optimalité d’un point-selle (Dualité forte) . 157
8.4 Exercices corrigés . . . . . . . . . . . . . . . . . . . . . . . . . 159
8.4.1 Exercice 1 . . . . . . . . . . . . . . . . . . . . . . . . . 159
8.4.2 Solution de l’Exercice 1 . . . . . . . . . . . . . . . . . . 159
8.4.3 Exercice 2 . . . . . . . . . . . . . . . . . . . . . . . . . 160
8.4.4 Solution de l’Exercice 2 . . . . . . . . . . . . . . . . . . 160
8.4.5 Exercice 3 . . . . . . . . . . . . . . . . . . . . . . . . . 162
8.4.6 Solution de l’Exercice 3 . . . . . . . . . . . . . . . . . . 162
8.5 Exercices non corrigés . . . . . . . . . . . . . . . . . . . . . . 164

Bibliographie 167
 Première partie

Optimisation sans contraintes

5
Chapitre 1

Concepts et Considérations
Théoriques

1.1 Introduction
Dans ce chapitre, on donne quelques rappels sur l’algèbre linéaire et la
programmation mathématique. On rappelle tout d’abord les propriétés essen-
tielles des formes quadratiques, ainsi que la notion des ensembles et fonctions
convexes.

1.2 Vecteurs et matrices

Définition 1.2.1. Soit n, m ∈ N∗ . Une matrice d’ordre m × n à coefficients
dans R est un tableau à deux dimensions, ayant m lignes et n colonnes,
représenté sous la forme suivante :
 
a11 a12 · · · a1n
 a21 a22 · · · a2n 
A = A(I, J) = (aij , i ∈ I, j ∈ J) =  ..
 
.. . . .. 
 . . . . 
am1 am2 · · · amn

où I = {1, 2, . . . , m} et J = {1, 2, . . . , n} représentent respectivement l’en-

semble des indices des lignes et des colonnes de A. Pour des calculs pratiques,

6
1.2 Vecteurs et matrices 7

la matrice A se note aussi

 
A1
 A2 
 .. 
.
 
A = (a1 , a2 , · · · , aj , · · · , an ) =  ,
 
 Ai 
 .. 
 . 
Am
 
a1j
 a2j 
où 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, noté x = x(J) = (xj , j ∈ J), sera ainsi considéré comme un
vecteur-colonne tandis que le vecteur-ligne sera noté xT . La matrice trans-
posée de A sera notée
AT = AT (J, I) = (aji , j ∈ J, i ∈ I).
Notons qu’un vecteur-colonne de dimension n peut être considéré comme une
matrice d’ordre (n × 1), tandis qu’un vecteur ligne de dimension n peut être
considéré comme une matrice d’ordre (1 × n).
La matrice A est dite carrée si on a m = n ; de plus, si A = AT , la matrice
est dite symétrique.
La matrice identité d’ordre n sera notée In .

1.2.1 Matrices et vecteurs partitionnés

On peut effectuer le produit d’une matrice A et d’un vecteur x, après les
avoir partitionnés judicieusement. On dit alors qu’on a effectué le produit
par blocs. En effet, si l’on a
 
x1
A = [A1 |A2 ], x = ,
x2
alors on peut écrire :

x1
Ax = [A1 |A2 ] = A 1 x1 + A 2 x2 .
x2
1.3 Discussion générale sur les solutions d’un système linéaire 8

De même pour
     
A11 A12 x1 b1
A= ,x = ,b = ,
A21 A22 x2 b2
l’équation Ax = b peut alors s’écrire :

A11 x1 + A12 x2 = b1 ,
A21 x1 + A22 x2 = b2 .

On peut partitionner une matrice d’une maniè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 faç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 é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 générale sur les solutions d’un

système linéaire
Soient m et n deux nombres entiers. Un système de m équations linéaires
à n inconnues x1 , x2 , · · · , xn s’é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 Propriétés des formes quadratiques 9

où les coefficients aij sont des réels. Les nombres b1 , b2 , · · · , bm sont appelés
les membres libres du systè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 système (1.1) peut s’écrire sous la forme matricielle suivante :

Ax = b. (1.2)

Tout vecteur x vérifiant les équations (1.1) s’appelle solution du système. Le

système (1.1) est dit compatible s’il possède une ou plusieurs solutions. Dans
le cas contraire, il est dit incompatible ou impossible. Lorsque le vecteur b
est nul, le système (1.2) est dit homogène. Tout système homogène possède
la solution triviale x = 0.

Définition 1.3.1. Le système liné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 système Ax = b admet

toujours des solutions, quelque soit le second membre b :
a) une et une seule solution si m = n,
b) une infinité de solutions si m < n.

1.4 Propriétés des formes quadratiques

Définition 1.4.1. Une fonction F : Rn −→ R, est dite forme quadratique
de n variables x1 , x2 , · · · , xn si elle s’écrit sous la forme suivante :
n X
X n
F (x) = aij xi xj = xT Ax (1.3)
i=1 j=1

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

une matrice carrée d’ordre n.
1.4 Propriétés des formes quadratiques 10

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

cela, la matrice A peut être supposée symétrique. En effet, en définissant de
nouveaux coefficients
dij = dji , 1 ≤ i, j ≤ n.
On obtient une nouvelle matrice D symétrique telle que
aij + aji
D = (dij , 1 ≤ i, j ≤ n), avec dij = dji = .
2
Il est clair qu’après une redéfinition des coefficients, la valeur de la forme
quadratique F (x) reste inchangée pour tout point x ∈ Rn :
F (x) = xT Ax = xT Dx.
Pour cela, il est naturel de considérer que la matrice d’une forme quadratique
est toujours symétrique.

1.4.1 Gradient d’une forme quadratique

Définition 1.4.2. Soit F : Rn −→ R une fonction réelle continûment
différentiable. Son gradient au point x est défini par :
 ∂F 
∂x1
(x)
 ∂F (x) 
 ∂x2
∇F (x) =  (1.4)

.. 
 . 
∂F
∂xn
(x)
Soit F une forme quadratique et D sa matrice symétrique associée :
F (x) = xT Dx. (1.5)
En é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
1.4 Propriétés des formes quadratiques 11

La dérivée partielle de F par rapport à chaque variable xj est donné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 conséquent, le gradient de F (x) est :

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

Définition 1.4.3. Soit une fonction réelle de classe C 2 , F : Rn −→ R. Le

Hessien de la fonction F est dé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)

Définition 1.4.4. Soit F : Rn −→ R une fonction de classe C 1 . La dérivé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 définie et semi-définie posi-

tive
Soit F (x) = xT Dx une forme quadratique avec D symétrique.
Définition 1.4.5. F est dite définie positive si xT Dx > 0, ∀x ∈ Rn et x 6= 0.
elle est dite semi-définie positive ou définie non négative si xT Dx ≥ 0, ∀x ∈
Rn .
1.4 Propriétés des formes quadratiques 12

Définition 1.4.6. F est dite définie négative si xT Dx < 0, ∀x ∈ Rn et x 6= 0.

Elle est dite semi-définie négative ou définie non positive si xT Dx ≤ 0, ∀x ∈
Rn .
Définition 1.4.7. Une matrice symétrique D est dite matrice définie positive
(respectivement non négative) et on note D  0 (respectivement D  0)
si elle est associée à une forme quadratique définie positive (respectivement
non négative).

1.4.3 Critère de Sylvester pour les formes quadratiques

définies et semi-définies
L’intérêt du critère du Sylvester est de caractériser une forme quadra-
tique définie ou semi-définie. Pour cela, considérons la matrice symétrique
suivante :  
d11 d12 · · · d1n
 d21 d22 · · · d2n 
D =  ..
 
.. .. 
 . . . 
dn1 dn2 · · · dnn
Le mineur de la matrice D, formé des lignes i1 , i2 , · · · , ip et les colonnes
j1 , j2 , · · · , jp , sera noté comme suit :

di1 j1 di1 j2 · · · di1 jp

di2 j1 di2 j2 · · · di2 jp
 
i1 i2 · · · ip
D = .. .. .. .
j1 j2 · · · jp . . .
dip j1 dip j2 · · · dip jp

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

est formé des lignes et des colonnes portant les mêmes numéros.
Les mineurs suivants :
d11 d12 · · · d1n
d11 d12 d21 d22 · · · d2n
D1 = d11 , D2 = , · · · , Dn = .. .. .. ,
d21 d22 . . .
dn1 dn2 · · · dnn

sont appelés mineurs principaux sucessifs. Alors, le critère de Sylvester se

formule comme suit :
1.4 Propriétés des formes quadratiques 13

Théorème 1.4.1 (Critère de sylvester). (i) Pour que la matrice D soit

définie positive (D  0), il est né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-définie positive (D  0), il est

nécessaire et suffisant que tous ses mineurs principaux soient non né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 définie né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 critère de Sylvester n’est valable que pour les matrices
symétriques.

1.4.4 Propriétés des matrices définies et semi-définies

positives
Les matrices symétriques définies ont des propriétés très intéressantes. En
voici quelques unes :

Propriété 1.4.1. Soit la matrice D partitionnée de la maniè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 définies
positives (non négatives). D’une manière générale, toute sous-matrice prin-
cipale d’une matrice définie positive (non négative) est aussi définie positive
(non négative).
1.5 Éléments d’analyse convexe 14

Propriété 1.4.2. Un élément de la diagonale d’une matrice symétrique D

définie non négative ne peut s’annuler que si les autres éléments de la même
ligne et colonne s’annulent aussi.
Propriété 1.4.3. Soit D une matrice symétrique définie non-négative. Si
x ∈ Rn est un point quelconque fixe tel que xT Dx = 0, alors on aura Dx = 0.

1.5 Éléments d’analyse convexe

Dans les problèmes d’optimisation, avec ou sans contraintes, une notion va
jouer un rôle très important : celle de convexité. En effet, pour la plupart des
algorithmes, la convergence vers un optimum global ne pourra être démontrée
qu’avec des hypothèses de convexité.

1.5.1 Ensembles convexes

Dé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 définition peut s’interpré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.
Définition 1.5.2. Soit S = {p1 , p2 , . . . , pk } un ensemble de k points de Rn .
• Un point p ∈ Rn peut être obtenu par :
– Combinaison liné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
1.5 Éléments d’analyse convexe 15

– 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 définit l’enveloppe conique (respectivement convexe) des points de

S comme l’ensemble des points de Rn pouvant être obtenus par com-
binaison conique (respectivement convexe) des points de S.
• L’espace affine (respectivement espace vectoriel) engendré par les points
de S est l’ensemble des points de Rn pouvant être obtenus par combi-
naison affine (respectivement linéaire) des points de S.
• Les points de S sont dits affinement indépendants (respectivement
linéairement indépendants) si aucun des points de S ne peut être ob-
tenu par une combinaison affine (respectivement linéaire) des autres
points de S.
Propriété 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,
où 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,

où α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.

Théorè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.
Théorème 1.5.2. Soit S ⊂ Rn un ensemble convexe. Alors
1. l’intérieur de S, noté IntS, est un ensemble convexe ;
2. la clôture S de S est un ensemble convexe.