République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Université A/MIRA de Bejaïa
Faculté des Sciences Exactes
Département de Recherche Opérationnelle

Support de Cours
Méthodes d’optimisation avancées

Destiné aux étudiants de Master 1 en Science des Données et Aide à la décision

Réalisé par :

Dr. Belkacem BRAHMI.

Année universitaire 2022/2023

 Table des matières

Introduction Générale 2

1 Introduction à l’optimisation non linéaire 3

1.1 Propriétés des formes quadratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Gradient d’une forme quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Matrice définie et semi-définie positive . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.3 Caractérisation des formes quadratiques . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.4 Propriétés des matrices définies et semi-définies positives . . . . . . . . . . . . . . . 7
1.2 Notions sur la convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Optimisation non linéaire sans contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Conditions d’optimalité sans contraintes . . . . . . . . . . . . . . . . . . . . . . . . . 11

Bibliographie 14

1
 Introduction Générale

La programmation mathématique ou l’optimisation numérique est une branche des mathématiques appli-
quées ayant pour objet l’étude théorique des problèmes d’optimisation, ainsi que la conception et la mise en
oeuvre d’algorithmes de résolution. La présence du terme "programmation" dans le nom donné à cette disci-
pline peut s’expliquer historiquement par le fait que les premières recherches et applications se sont développées
dans le contexte de l’économie et de la recherche opérationnelle.
L’optimisation est largement utilisée dans les sciences, ingénierie, économie et l’industrie et son domaine
d’application ne cesse de croître à nos jours. L’optimisation est un outil très important en aide à la decision et
dans l’analyse des systèmes réels. Pour l’utiliser, il faut tout d’abord identifier un objectif (ou in critère), une
mesure quantitative de la performance du système étudié. Cet objectif, peut être un profit, le temps, l’énergie
ou n’importe quelle quantité ou une combinaison de quantités qui peut être représenté par un seul nombre réel.
L’objectif depends de certains caractéristiques du système, appelées variables ou paramètres qui sont inconnus.
Le but est de trouver les valeurs de ces variables qui optimise l’objectif. Souvent les variables sont soumises à
des contraintes imposées par le système étudié. Par exemple, les quantités produites des articles dans une usine
ne peuvent pas être négatives.
Le processus d’identification de l’objectif, variables et les contraintes pour un problème donné est connu
sous le nom de "Modélisation". La construction d’un modèle approprié est la première étape ; souvent c’est
l’étape la plus importante dans le processus d’optimisation.

2
 Introduction à l’optimisation non linéaire
1
Dans ce chapitre introductif, nous rappelons les concepts mathématiques nécessaires à l’optimisation non
linéaire. Premièrement, nous rappelons les formes quadratiques et en particulier les formes quadratiques définies
et semi-définies positives qui jouent un rôle très important en optimisation. Par la suite, des notions d’ensembles
et fonctions convexes, noyau de l’optimisation convexe, sont abordées. Dans la deuxième partie de ce chapitre,
on présente les conditions d’optimalité pour les problèmes d’optimisation non linéaire sans contraintes.

1.1 Propriétés des formes quadratiques

Définition 1.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 n
X
f (x) = aij xi xj + cj xj = x0 Ax + c0 x, (1.1)
i=1 j=1 j=1

où x = (x1 , x2 , · · · , xn )0 et c sont des n-vecteurs colonnes ; A = (aij , 1 ≤ i, j ≤ n) est une matrice carrée
d’ordre n. Le symbole (0 ) est l’opérateur de transposition vectorielle et matricielle.

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
aij + aji
dij = dji = , 1 ≤ i, j ≤ n,
2
on obtient une nouvelle matrice D = (dij , 1 ≤ i, j ≤ n) symétrique. Il est clair qu’après une redéfinition des
coefficients, la valeur de la forme quadratique f (x) reste inchangée :

f (x) = x0 Ax + c0 x = x0 Dx + c0 x, ∀x ∈ Rn . (1.2)

3
Pour cela, il est naturel de considérer que la matrice d’une forme quadratique est toujours symétrique.

Exemple 1.1. Soit la forme quadratique suivante : f (x) = 3x21 + x22 − 4x1 x2 + 2x2 x3 .
La matrice symétrique associée à la forme quadratique f est
 
3 −2 0
 
D = −2 1 1 .
 
 
0 1 0

1.1.1 Gradient d’une forme quadratique

Définition 1.2. Soit f : Rn −→ R une fonction réelle continûment différentiable . Son gradient au point x est
défini par :
 
∂f (x)
 ∂x1 
 ∂f (x) 
 ∂x2 
∇f (x) =  .  ,
  (1.3)
 .. 
 
∂f (x)
∂xn
∂f (x)
où ∂xi est la dérivée partielle de f par rapport à la composante xi du vecteur x.

Le gradient de la forme quadratique (1.2) est

∇f (x) = 2Dx + c.

Définition 1.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 (x) = ∂f
∇ ∂x , ∇ ∂f
∂x2 , · · · , ∇ ∂f
∂xj , · · · , ∇ ∂f
∂xn
1
 
∂2f ∂2f 2f

 ∂x21 ∂x1 ∂x2 · · · ∂x∂1 ∂x n

 ∂2f ∂2f ∂2f 


 ∂x ∂x ∂x2 2 · · · ∂x2 ∂xn 
=  2. 1 .. ..  . (1.4)
 . 
 . . . 
 2 
∂ f ∂2f ∂2f
∂xn ∂x1 ∂xn ∂x2 · · · ∂x2
n

Le Hessien de la forme quadratique (1.2) est tout simplement

∇2 f (x) = 2D.

Définition 1.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 :
∂f (x) f (x + td) − f (x)
= lim
∂d t→0+ t
∂f ∂f
= (x + td)|t=0+ d1 + · · · + (x + td)|t=0+ dn
∂x1 ∂xn
= d0 ∇f (x).

4
1.1.2 Matrice définie et semi-définie positive

Soit D une matrice carrée d’ordre n, supposée symétrique.

Définition 1.5. D est dite définie positive et on note D > 0 si x0 Dx > 0, ∀x ∈ Rn , x 6= 0. Elle est dite semi-
définie positive ( ou définie non négative) et on note D ≥ 0 si x0 Dx ≥ 0, ∀x ∈ Rn . Si la forme quadratique
x0 Dx est positive pour certaines valeurs de x et négatives pour d’autres, alors D est dite indéfinie.

Définition 1.6. f (x) est dite définie négative si x0 Dx < 0, ∀x ∈ Rn et x 6= 0. Elle est dite semi-définie négative
ou définie non positive si x0 Dx ≤ 0, ∀x ∈ Rn .

Une forme quadratique f (x) = x0 Dx+c0 x est dite définie positive (resp. semi-définie positive) si sa matrice
associée D > 0 (resp D ≥ 0).

1.1.3 Caractérisation des formes quadratiques

L’intérêt du critère du Sylvester est de caractériser une forme quadratique 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 des colonnes j1 , j2 , · · · , jp , sera noté comme suit :

di1 j1 di1 j2 · · · di1 jp

 
i1 , i2 , · · · , ip di2 j1 di2 j2 · · · di2 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-à-dire, s’il est formé de lignes et de colonnes
portant les mêmes numéros. Les mineurs suivants

d11 d12 · · · d1n

d11 d12 d21 d22 · · · d2n
D1 = d11 , D2 = , · · · , Dn = .. .. .. = D,
d21 d22 . . .
dn1 dn2 · · · dnn

sont appelés mineurs principaux successifs. Alors, le critère de Sylvester se formule comme suit :

5
Théorème 1.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 mineurs
principaux successifs soient positifs :

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

(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. (1.6)
i1 , i2 , · · · , ip

Remarque 1.1. Pour qu’une matrice D soit définie négative (D < 0) ou non positive (D ≤ 0), les conditions
(1.5) et (1.6) se reformulent ainsi :

(i) D < 0 ⇔ (−1)p Dp > 0, p = 1, 2, · · · , n.

 
i1 , i2 , · · · , ip
(ii) D ≤ 0 ⇔ (−1)p D   ≥ 0, 1 ≤ i1 < i2 < · · · < ip ≤ n, p = 1, 2, · · · , n.
i1 , i2 , · · · , ip

Remarque 1.2. Le critère de Sylvester n’est valable que pour les matrices symétriques.

Les formes quadratique définies et semi-définies positives peuvent être aussi reliées aux valeurs propres,
comme le montre le théorème suivant :

Théorème 1.2. (critère sur les valeurs propres) Soit D une matrice symétrique d’ordre n. On note par {λi }i=1,··· ,n
ses valeurs propres réelles. On a les équivalences suivantes :

1. D ≥ 0 ⇐⇒ λi ≥ 0, i = 1, · · · , n.

2. D > 0 ⇐⇒ λi > 0, i = 1, · · · , n.

3. D est indéfinie si et seulement si certains λi sont positifs et d’autres négatifs.

Exemple 1.2. Soit la matrice  

2−1
 .
−1 1

XApplication de la définition : Pour tout x = (x1 , x2 )0 ∈ R2 , on a :

  
2 −1 x
x0 Ax = (x1 , x2 )0    1  = 2x21 − 2x1 x2 + x2 = x21 + (x1 − x2 )2 > 0, pour x 6= 0.
−1 1 x2

6
La forme quadratique f (x) = x0 Ax est strictement définie positive (A > 0). Le gradient et le hessien de f sont
respectivement    
∂f (x)
4x1 − 2x2
∇f (x) =  ∂x1  =  et ∇2 f (x) = A.
∂f (x)
∂x2 −2x1 − 4x2
XApplication du critère de Sylvester :


−1 2
D1 (A) = 2 > 0, D2 (A) = det   = 1 > 0,
−1 1

d’où f est strictement définie positive.

1.1.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és 1. Soit la matrice D partitionnée de la manière suivante :

m k
 
D11 D12 m
D=   , m + k = n.
D21 D22 k

Si D > 0 (D ≥ 0), alors les sous-matrices principales D11 et D22 sont aussi définies positives (non négatives).
D’une manière générale, toute sous-matrice principale d’une matrice définie positive (non négative) est aussi
définie positive (non négative).

Propriétés 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és 3. Soit D une matrice symétrique semi-définie positive. Si x ∈ Rn est un point quelconque fixe tel
que x0 Dx = 0, alors on aura : Dx = 0.

Théorème 1.3. Soit D une matrice symétrique carrée d’ordre n et A est une m × n-matrice, avec m < n.

(i) Si la matrice D est définie positive, alors elle est inversible et son inverse est aissi définie positive.

ii) Si D est semi-définie positive, alors la matrice symétrique ADA0 est aussi semi-définie positive.

iii) Si D est définie positive et rang(A) = m, alors ADA0 est aussi définie positive.

Preuve. i) Posons y = A0 x, alors la forme quadratique correspondant à la matrice symétrique ADA0 est
x0 ADA0 x = y 0 Dy ≥ 0 pour tout y ∈ Rn et donc pour tout x ∈ Rm . Par conséquent, ADA0 est semi-définie
positive.

7
 ii) Comme rang(A) = m, alors les m colonnes de A sont linéairement indépendants. Le fait que x 6= 0
entraîne y = A0 x 6= 0 et puisque D est définie positive, alors y 0 Dy > 0 pour tout y 6= 0. Donc, il s’ensuit que
x0 ADA0 x > 0 pour tout x 6= 0. 

Corollaire 1. La matrice symétrique AA0 , appelée matrice de Graham de A, est définie positive ou semi-définie
positive selon que le rang de A est égale à m ou inférieur à m.

Preuve. Ceci est une conséquence directe du théorème précédent en remplaçant D par la matrice identité I.


Théorème 1.4. [36] Si D est une n × n matrice symétrique de rang r < n, alors il existe une matrice non
singulière P , telle que :  
Mr 0
P 0 DP =  ,
0 0
où Mr est une sous-matrice carrée d’ordre r, symétrique et non singulière.

1.2 Notions sur la convexité

La notion de convexité joue un rôle très important dans la théorie classique de l’optimisation. Elle est un
outil indispensable pour la recherche des conditions à la fois nécessaires et suffisantes d’optimalité. En effet, la
majorité des algorithmes proposés dans le cas de l’optimisation convexe sont efficaces.

1.2.1 Ensembles convexes

Définition 1.7. Un ensemble C ⊂ Rn est dit convexe si pour tout x et y de C, le segment [x, y] est tout entier
contenu dans C, c.à.d,
∀λ ∈ [0, 1], λx + (1 − λ)y ∈ C. (1.7)

La figure suivante illustre cette notion.

Figure 1.1 – Exemple d’ensemble convexe et non convexe

8
 Plus généralement, étant donnés p points x1 , x2 , · · · , xp de Rn , on dit que x ∈ Rn est une combinaison
convexe de ces p points s’il existe des coefficients λ1 , λ2 , · · · , λp , tels que :
p
X p
X
x= λi xi , avec λi = 1, λi ≥ 0, i = 1, 2, · · · , p.
i=1 i=1

L’hyperplan H = {x ∈ Rn : a0 x = b} est un ensemble convexe, où a ∈ Rn est un vecteur non nul, appelé

vecteur normal à l’hyperplan et b est un scalaire. Pour l’hyperplan H, si b = 0 alors il peut être réduit à un
sous-espace de vecteurs orthogonaux à a. L’hyperplan H coupe l’espace Rn en deux demi-espaces H − = {x ∈
Rn : a0 x ≤ b} et H + = {x ∈ Rn : a0 x ≥ b} qui sont des ensembles fermés et convexes.
Les polyèdres représentent un cas spécial et important des ensembles convexes.

Définition 1.8 (Polyèdre). L’intersection d’un nombre fini de demi-espaces fermés

S = {x ∈ Rn : a0i x ≤ bi , i = 1, 2, · · · , m}

est appelé polyèdre, où chaque ai est un vecteur non nul et bi est un scalaire. Un polyèdre est un ensemble
convexe.

Définition 1.9 (Point extrême). Soit S ⊂ Rn un ensemble non vide. Un vecteur x ∈ S est dit point ex-
trême(sommet), s’il ne peut pas s’écrire sous forme de combinaison convexe de deux points quelconques de
S, i.e.,
∀x1 , x2 ∈ S, ∀λ ∈ [0, 1] : x = λx1 + (1 − λ)x2 =⇒ x = x1 = x2 .

Définition 1.10 (Cône). L’ensemble non vide C de Rn est appelé cône de sommet zero si

∀x ∈ C =⇒ λx ∈ C, pour tout réel λ ≥ 0.

De plus, si C est un convexe alors C est dit cône convexe.

Une classe spéciale des cônes convexes est celle des cônes polaires, définis comme suit :

Définition 1.11 (Cône polaire). Soit S un ensemble non vide de Rn . Alors, le cône polaire de S, noté par S ∗ ,
est donné par :
S ∗ = {a| a0 x ≤ 0, pour tout x ∈ S}.

Si S = ∅, S ∗ est tout simplement l’espace Euclidien Rn . Les cônes tangent et normal jouent un rôle spécial
en optimisation non linéaire.

Définition 1.12. Soit S un ensemble fermé et convexe.

9
 – Le cône normal de S en x̄ est défini comme suit :

N (x̄) = {y ∈ Rn | y 0 (x − x̄) ≥ 0, ∀x ∈ S}.

– Le cône tangent de S en x̄ est le polaire du cône normal en x̄, qui est :

T (x̄) = N (x̄)∗ = {d| d = lim λ(x − x̄), λ ≥ 0, x ∈ S}.

x→x̄

Le théorème de Farkas suivant joue un rôle très important pour la déduction des conditions d’optimalité de
premier ordre en optimisation linéaire et non linéaire avec contraintes.

Théorème 1.5 (Lemme de Farkas [23]). Soit A ∈ Rm×n et c ∈ Rn . Alors exactement un des deux systèmes
suivants admet une solution :

Système 1 : Ax ≤ 0, c0 x > 0, (1.8a)

Système 2 : A0 y = c, y ≥ 0. (1.8b)

Un résultat plus général concernant les équations et les inégalités linéaires est donné dans le théorème des
alternatives suivant :

Théorème 1.6 (Lemme de Motzkin [23]). Soit A1 ∈ Rm1 ×n , A2 ∈ Rm2 ×n et c ∈ Rn . Alors exactement un des
deux systèmes suivants admet une solution :

Système 3 : A1 x = 0, A2 x ≤ 0, c0 x > 0, (1.9a)

Système 4 : A01 y1 + A02 y2 = c, y2 ≥ 0. (1.9b)

1.2.2 Fonctions convexes

Définition 1.13. On dit qu’une fonction f : S ⊂ Rn −→ R, définie sur un ensemble convexe S, est convexe si
elle vérifie
∀(x, y) ∈ S 2 , ∀λ ∈ [0, 1], f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y). (1.10)

f est dite strictement convexe si l’inégalité stricte est toujours vérifiée pour x 6= y et λ ∈]0, 1[.

Définition 1.14. L’épigraphe d’une fonction f , noté épi(f ), est l’ensemble suivant des vecteurs à n + 1 com-
posantes (x, µ) :
épi(f ) = {(x, µ)/f (x) ≤ µ, x ∈ Rn , µ ∈ R} ⊂ Rn+1 .

Propriétés 4. Une fonction f est convexe si et seulement si épi(f ) est un ensemble convexe.

10
 Figure 1.2 – Fonction convexe

Pour des fonctions différentiables, les fonctions convexes peuvent être caractérisées comme suit :

Théorème 1.7. [27] Si f est continûment différentiable, les conditions (a) et (b) ci-dessous sont équivalentes :
Si f est deux fois continûment différentiable, les conditions (a), (b) et (c) ci-dessous sont équivalentes :

(a) f est convexe ;

(b) ∀x ∈ S, ∀y ∈ S : f (y) ≥ f (x) + ∇f (x)0 (y − x) ;

(c) ∀x ∈ S, le Hessien ∇2 f (x) est une matrice semi-définie positive.

Alors d’après le théorème précédent, on déduit facilement qu’une fonction quadratique f (x) = x0 Dx + c0 x
est convexe si et seulement si sa matrice associée D est semi-définie positive.

1.3 Optimisation non linéaire sans contraintes

1.3.1 Conditions d’optimalité sans contraintes

Soit le programme non linéaire et sans contraintes suivant :

min f (x). (1.11)

x∈Rn

La fonction f est supposée au moins deux fois continûment différentiable. Soit x0 un minimum local pour ce
problème. Alors, pour tout α > 0 assez petit, on a nécessairement :

f (x∗ ) ≤ f (x∗ + αd), ∀d ∈ Rn .

11
Ceci implique :
f (x∗ + αd) − f (x∗ )
lim = d0 ∇f (x∗ ) ≥ 0.
α→0 α
En particulier, la direction d = −∇f (x∗ ) est admissible et on déduit que

∇f (x∗ )0 ∇f (x∗ ) = ||∇f (x∗ )||2 ≤ 0 ⇔ ∇f (x∗ ) = 0.

Théorème 1.8. (condition nécessaire du premier ordre)

Soit x∗ un minimum local (global) pour le problème (1.11). Alors on a :

∇f (x∗ ) = 0.

Un point x∗ satisfaisant cette condition est appelé point stationnaire (ou point critique). Au deuxième ordre,
on obtient :

f (x∗ ) ≤ f (x∗ + αd),

α2 0 2
f (x∗ ) ≤ f (x∗ ) + α∇f (x∗ )0 d + d ∇ f (x∗ )d + o(α2 ),
2

où o(α2 ) dénotant une fonction telle que :

o(α2 )
lim = 0.
α→0 α2

Comme x∗ est un minimum local, on a :

α2 0 2
0≤ d ∇ f (x∗ )d + o(α2 ).
2

En divisant par α2 et en prenant la limite on aura le théorème suivant :

Théorème 1.9. (conditions nécessaires de second ordre)

Soit x∗ un minimum local (global) du problème (1.11). On a alors :

∇f (x∗ ) = 0,

d0 ∇2 f (x∗ )d ≥ 0, ∀d ∈ Rn .

Ces conditions ne sont pas suffisantes comme le montre, par exemple, la fonction x3 et l’exemple suivant :
   
2x1 2 0
Exemple 1.3. Soit la fonction f (x) = x21 − x22 , avec ∇f (x) =   et ∇2 f (x) =  .
−2x2 0 −2
     
0 0 2 0
Pour x∗ =  , on a ∇f (x∗ ) =   et ∇2 f (x∗ ) =  . On remarque que x∗ est un point stationnaire
0 0 0 −2
et que la matrice hessienne ∇ f (x ) n’est pas semi-définie positive, alors x∗ n’est ni un minimum local, ni un
2 ∗

maximum local.

12
 De plus si la condition de second ordre est strictement satisfaite, on obtient la condition suffisante suivante :

Théorème 1.10. conditions suffisantes de deuxième ordre

Soit x∗ un point vérifiant :

∇f (x∗ ) = 0,

d0 ∇2 f (x∗ )d > 0, ∀d ∈ Rn , d 6= 0.

Alors x∗ est un minimum local strict.

Exemple 1.4.
  Soit f (x) = x21 + x
2.
2   
0 0 2 0
Pour x∗ =  , on a ∇f (x∗ ) =   et ∇2 f (x∗ ) =   > 0. Alors x∗ est un minimum local strict de
0 0 0 2
f.

Exemple 1.5. Considérons la fonction

1 1 1
f (x) = x31 + x21 + 2x1 x2 + x22 − x2 + 9.
3 2 2

La condition d’optimalité de premier ordre (stationarité) est :

 
x21 + x1 + 2x2
∇f (x) =   = 0.
2x1 + x2 − 1

A partir de la deuxième condition , on aura x2 = 1 − 2x1 et on la remplaçant dans la première équation on

obtient : x21 − 3x1 + 2 = 0 =⇒ (x1 − 1)(x1 − 2) = 0 =⇒ x1 = 1 ou x1 = 2.
Donc on obtient les deux points critiques suivants :
   
1 2
xa =   et xa =  .
−1 −3
 
2x 1 + 1 2
La matrice hessienne de la fonction f est ∇2 f (x) =  .
2 1
   
3 2 5 2
∇2 f (xa ) =  , ∇2 f (xb ) =  .
2 1 2 −1

∇2 f (xb ) > 0 est définie positive, alors xa est un minimum local. Par contre la matrice ∇2 f (xb ) est indéfinie,
alors on peut rien dire sur le point xa .

13
 Bibliographie

[1] J. Abadie. On the Kuhn-Tucker theorem. In J. Abadie, editor, Nonlinear Programming. North Holand,
Amesterdam, 1967.

[2] E. W. Barankin and R. Dorfman. On quadratic programming, volume II. Publications in statistics, Uni-
versity of California, 1958.

[3] D. Bertsekas. Nonlinear Programming. Athena Scientific, Belmont MA, 1995.

[4] J. C. G. Boot. Quadratic Programming : Algorithms, Anomalies and Applications. North-Holland Publi-
shing Company, Amsterdam, The Netherlands, 1964.

[5] S. Boyed and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

[6] B. BRAHMI. Méthodes primales et duales pour l’optimisation quadratique convexe :extension et appli-
cations. Thèse de doctorat, Université de Béjaia, 2011.

[7] E. K. P. Chong and S. H. Zak. An Introduction to Optimization. John Wiley and Sons, Inc., 2001.

[8] N. Cristianini and J. Shawe-Taylor. Introduction to Support Vector Machines and other kernel-based lear-
ning methods. Cambridge University Press, United Kingdom, 2000.

[9] G. B. Dantzig. Linear programming and extensions. Princeton University Press, Princeton, N.J, 1963.

[10] G. B. Dantzig and M. N. Thapa. Linear Programming, volume I : Introduction. Springer-Verlag, New
York, 1997.

[11] G. B. Dantzig and M. N. Thapa. Linear Programming, volume II : Theory and Exrensions. Springer-Verlag,
New York, 2003.

[12] W. S. Dorn. Duality in quadratic programming. Quarterly of Applied Mathematics, 18 :155–162, 1960.

[13] R. Fletcher. Practical Methods of Optimization. J. Wiley and Sons, Chichester, England, second edition,
1987.

[14] J. Gauvin. Leçons de programmation mathématique. Editions de l’Ecole Polytechnique de Montréal, 1995.

14
[15] P. E. Gill and W. Murray. Numerical Methods For Constrained Optimization. Acadamic Press Inc, 1974.

[16] P. E. Gill, W. Murray, and M. H. Wright. Numerical Linear Algebra and Optimization, volume 1. Addison-
Wesley Publishing Company, 1991.

[17] P. E. Gill, W. Murray, and M. H. Wright. Practical Optimization. Academic Press Inc, London, 1981.

[18] G. H. Golub and C. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, Third
Edition, 1996.

[19] R. Hartley. Linear and non linear programming : an introduction to linear methods in mathematical
programming. Ellis Horwood, England, 1985.

[20] H.W. Kuhn and A.W. Tucker. Nonlinear programming. In J. Neyman, editor, Proceedings of the Second
Berkeley Symposium on Mathematical Statistics and Probability, pages 481–492, University of California
Press, Berkeley, California, 1951.

[21] C. E. Lemke. A method of solution for quadratic programs. Management Science, 8 :442–453, 1962.

[22] D. Luenberger. Introduction to Linear and Nonlinear Programming. Addison-Wesley, second edition,
1984.

[23] O. L. Mangasarian. Nonlinear Programming. McGraw-Hill, New York, 1969.

[24] H. M. Markowitz. Portfolio selection. Journal of Finance, 7(1) :77–91, 1952.

[25] H. M. Markowitz. The optimization of a quadratic function subject to linear constraints. Naval Research
Logistics Quarterly, 3 :111–133, 1956.

[26] H. M. Markowitz. Portfolio Selection : Efficient Diversification in Investments. John Wily and Sons, New
York, 1959.

[27] M. Minoux. Programmation Mathématique. Bordas et C.N.E.T.-E.N.S.T., Paris, 1983.

[28] S. G. Nash and A. Sofer. Linear and Nonlinear Programming. McGraw-Hill, New York, 1996.

[29] Y. E. Nesterov and A. S. Nemirovsky. Interior-Point Polynomial Methods in Convex Programming. SIAM
Publications, 1994.

[30] J. Nocedal and S. J. Wright. Numerical Optimization. Springer-Verlag, New York, 1999.

[31] C. Van De Panne. Methods for Linear and Quadratic Programming. North Holland, Amsterdam, the
Netherlands, 1975.

[32] Singiresu S. Rao. Engineering Optimization : Theory and Practice. John Wiley And Sons, New York,
third edition, 1996.

15
[33] G. V. Reklaitis, A. Ravindran, and K. M. Ragsdell. Engineering Optimization : Methods and Applications.
Wiley Interscience, New York, 1983.

[34] C. Roos, T. Terlaky, and J.-Ph. Vial. Theory and Algorithms for Linear Optimization : An Interior Point
Approach. John Wiley & Sons, Chichester, UK, 1997.

[35] B. Schölkopf and A. J. Smola. Learning With Kernels : Support Vector Machines, Regularization, Opti-
mization and Beyond. MIT Press, 2002.

[36] S. M. Sinha. Mathematical Programming :Theory and Methods. Elsevier, 2006.

[37] W. Sun and Y. X. Yuan. Optimization Theory and Methods :Nonlinear Programming. Springer, New York,
2006.

[38] R. J. Vanderbei. Linear Programming : Foundations and Extensions. Princeton University Press, Prince-
ton, NJ 08544, 2001.

[39] V. N. Vapnik. Estimation of Dependencies Based on Empirical Data. Springer Verlag, Berlin, 1982.

[40] P. Wolfe. The simplex method for quadratic programming. Econometrica, 27 :382–398, 1959.

[41] P. Wolfe. A duality theorem for nonlinear programming. Quarterly of Applied Mathematics, 19 :239–244,
1961.

[42] S.J. Wright. Primal-Dual Interior-Point Methods. SIAM Publications, Philadelphia, 1997.

16