UNIVERSITÉ FACULTÉ DES SCIENCES ET

A BDELMALEK ESSAÂDI TECHNIQUES DE TANGER

OPTIMISATION

A. BEL FEKIH
(Département de Mathématiques)

mars 2020
 Sommaire
1. PRÉLIMINAIRES 3

2. OPTIMISATION SANS CONTRAINTES 13

3. OPTIMISATION AVEC CONTRAINTES 17

4. PROGRAMMATION LINÉAIRE 29

1
 Préliminaires
Chapitre 1

6.2 Fonctions quadratiques à 2 variables . . . . . . . . . . . . . . . . . . 7

Sommaire 6.3 Fonction quadratique à plusieurs variables . . . . . . . . . . . . . . 7

6.4 fonction quadratique associée à une fonction 2 fois différen-
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 tielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Minimum et borne inférieure . . . . . . . . . . . . . . . . . . . . . . . . 3 7 Point-selle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Fonctions continues - Différentiables . . . . . . . . . . . . . . . . . . . 4 8 Problèmes d’optimisation. . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.1 Dérivée directionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 8.1 Définition d’un problème d’optimisation. . . . . . . . . . . . . . . . 10
3.2 Le vecteur gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 8.2 Problème sans contraintes. . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 La matrice hessienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 8.3 Problème avec contraintes. . . . . . . . . . . . . . . . . . . . . . . . . 10

4 Rappels sur les matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 a) Problème avec contraintes égalités . . . . . . . . . . . . . . . . . . . 10

b) Problème avec contraintes inégalités . . . . . . . . . . . . . . . . . 10
5 Les fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
c) Problème avec contraintes égalités-inégalités . . . . . . . . . . . . 11
5.1 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
a) Polytopes et polyèdres . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5.2 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1 - Introduction
a) Fonctions une fois différentiables. . . . . . . . . . . . . . . . . . . . 6
De nombreux problèmes nécessitent de minimiser une fonction :
b) Fonctions deux fois différentiables . . . . . . . . . . . . . . . . . . . 6

• Minimiser la distance entre un point et une courbe ;

6 Fonctions quadratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.1 Fonctions quadratiques à une variable . . . . . . . . . . . . . . . . . 7 • Trouver l’ état d’équilibre d’un système mécanique (Minimiser Epot ) ;

2
Chap. 1- Préliminaires A . BELFEKIH 2. Minimum et borne inférieure

• Trouver l’état d’équilibre d’un gaz, d’un mélange (Maximiser Entropie) ; 2. On dit que a est un minimum local de f si on peut trouver R > 0 tel que

• Minimiser le coût d’une production ; f (a) É f (x ) ∀x ∈ Rn vérifiant kx – ak É R

• Maximiser le profit d’une production ;

• Etc. . . . Définition 2
1. On dit que β ∈ R est un minorant de f si
Tous ces problèmes entrent dans une même catégorie : L’optimisation
∀x ∈ Rn : β É f (x )
Remarque 1
Maximiser F (x ) équivaut à minimiser –F (x ) . Donc minimiser et maximiser sont 2. Si f admet des minorants on appelle borne inférieure de f le plus grand
en fait le même type de problèmes et pour résoudre des minorants on le note
½
maximiser F (x ) inf ou inff (x )
x∈K x ∈Rn

si f n’admet aucun minorant on pose

il suffit de résoudre ½
minimiser – F (x )
inff (x ) = –∞
x∈K

Exemple 1
2 - Minimum et borne inférieure Soit la fonction à 2 variables
¢2
f x,y = (x – 1)2 + y – 2 + 3
¡ ¢ ¡
Dans tout ce document, et sauf mention contraire, f est à plusieurs variables et à
images réelles :
f : Rn → R alors h ¢2 i
inff = inf (x – 1)2 + y – 2 + 3 = 3
¡
x,y ∈R

Définition 1
1. On dit que a ∈ Rn est un minimum global de f si
Proposition 1 :
n
f (a) É f (x ) ∀x ∈ R Si a est un minimum global de f alors infn f (x ) = f (a) .
x ∈R

page 3
Chap. 1- Préliminaires A . BELFEKIH 3. Fonctions continues - Différentiables

Remarque 2 Définition 4
1. L’existence d’un minimum assure que la borne inférieure est finie (> –∞) et On appelle gradient de f en a le vecteur
elle vaut la valeur de f au minimum.
 ∂f (a) 
∂x1
2. Une borne inférieure finir n’assure pas l’existence de minimum. C’est le cas  .. 
pour Of (a) = 
 .


1 ∂f (a)
f (x ) = , x∈R ∂xn
1 + x2
pour laquelle inf f (x ) = 0 alors que ∀x ∈ R on a f (x ) > 0.
x ∈R
Définition 5
On dit que a ∈ Rn est un point critique de f si Of (a) = 0 ou encore
3 - Fonctions continues - Différentiables ∂f (a)
=0 , j = 1,2, · · · ,n
∂xj
3.1 DÉRIVÉE DIRECTIONNELLE
f : Rn → R, a ∈ Rn et d ∈ Rn .
3.3 LA MATRICE HESSIENNE
Définition 3
On appelle dérivée de f en a dans la direction d la limite suivante lorsqu’elle Quand la dérivée partielle d’ordre i de la dérivée partielle d’ordre j existe on la note
existe :
∂2 f (x ) ∂ ∂f (x )
µ ¶
1£ ¡ = , 1 É i,j É n
lim f a + td – f (a) ≡ f 0 (a) .d
¢ ¤
t →0 t ∂xi ∂xj ∂xi ∂xj

Définition 6
3.2 LE VECTEUR GRADIENT La matrice hessienne est la matrice carrée suivante
f : Rn → R et a ∈ Rn . La dérivée partielle de f par rapport à xi est la dérivée direc-  ∂2 f (x) ∂2 f (x )

tionnelle dans la direction de d = ei où ei est le vecteur n◦ i de la base canonique ∂ x 2 · · · ∂x1 ∂xn
 i 
{e1 , . . . ,en } de Rn . Donc O2 f =  ... .. ..
 
 2 . . 

2
∂ f (x ) ∂ f (x )
∂f (a) 1£ ¤ ∂xn ∂x1 · · · ∂x 2
= lim f (a + tei ) – f (a) n
∂xi t →0 t

page 4
Chap. 1- Préliminaires A . BELFEKIH 4. Rappels sur les matrices

∂2 f (x ) ∂2 f (x ) 5 - Les fonctions convexes

Si les dérivées secondes sont continues alors = et donc O2 f (x )
∂xi ∂xj ∂xj ∂xi
est symétrique.
5.1 ENSEMBLES CONVEXES
domaine convexe

4 - Rappels sur les matrices x,y ∈ D , 0 É λ É 1 =⇒ λx + (1 – λ) y ∈ D

Définition 7 a) Polytopes et polyèdres

Soit A une matrice symétrique. Un demi-espace dans Rn est de la forme

1. A est dite semi-définie positive si 〈Ax,x 〉 Ê 0, ∀x ∈ Rn ; x ∈ Rn / a1 x1 + · · · + an xn Ê b

© ª

2. A est dite définie positive si 〈Ax,x 〉 > 0, ∀x ∈ Rn , x 6= 0 ; Polytope : intersection de plusieurs demi-espaces.
3. A est dite semi-définie négative si –A est semi-définie positive. Polyèdre : Polytope borné.

4. A est dite définie négative si –A est définie positive. Proposition 3 :

Tout polytope peut être ramené au polytope suivant

P 0 = y / Ay = b , yj Ê 0 , 1 É j É m
© ª
Proposition 2 :
Soit A une matrice symétrique d’ordre n.

1. A est semi-définie positive si, et seulement si, toutes ses valeurs Définition 8
propres sont positives.
Un vecteur x ∈ Rn est une combinaison convexe de vecteur ak k si
¡ ¢

2. A est semi-définie négative si, et seulement si, toutes ses valeurs p p

propres sont négatives. λk ak avec λk Ê 0 et λk = 1
X X
x=
k=1 k=1
3. A est définie positive si, et seulement si, toutes ses valeurs propres sont
strictement positives.

4. A est définie négative si, et seulement si, toutes ses valeurs propres
5.2 FONCTION CONVEXE
sont strictement négatives.

5. Toute matrice définie positive (ou définie négative) est inversible.

page 5
Chap. 1- Préliminaires A . BELFEKIH 5. Les fonctions convexes

2. f est strictement convexe surK si, et seulement si,

Définition 9
­ ®
f (z) > f (x ) + Of (x ) ,z – x , ∀x 6= z ∈ K
1. f fonction convexe sur D convexe si

x,y ∈ D , 0 É λ É 1 f λx + (1 – λ) y É λf (x ) + (1 – λ) f y
¡ ¢ ¡ ¢
=⇒
Remarque 3
En prenant z = x + h la caractérisation de convexe sur K devient
2. f fonction strictement convexe sur D convexe si
, ∀x,h ∈ Rn / x,x + h ∈ K
¡ ¢ ­ ®
f x + h Ê f (x ) + Of (x ) ,h
x 6= y ∈ D , 0 < λ < 1 f λx + (1 – λ) y < λf (x ) + (1 – λ) f y
¡ ¢ ¡ ¢
=⇒
Dans R avec K = R elle devient

f x + h Ê f (x ) + f 0 (x ) h, ∀x,h ∈ R
¡ ¢
Propriétés 1
⇔f x + h – f (x ) Ê f 0 (x ) h, ∀x,h ∈ R
¡ ¢
¡ ¢
1. f fonction convexe sur D si, et seulement si, l’ensemble f x + h – f (x )
⇔∀x ∈ R : Ê f 0 (x ) , ∀h > 0
h
x,y ∈ Rn+1 / y Ê f (x )
©¡ ¢ ª

est convexe.
b) Fonctions deux fois différentiables
2. f convexe dans D SSI pour tout x,y ∈ D, ϕ (t ) = f tx + (1 – t ) y est convexe sur
¡ ¢

[0,1] . Théorème 2 :
Soient K ⊆ Rn et f : K → R 2 fois différentiable (O2 f existe) alors

a) Fonctions une fois différentiables 1. f est convexe sur K si, et seulement si, pour tout x ∈ K , la matrice
O2 f (x ) est semi-définie positive :
Théorème 1 : ­£ 2
∀d ∈ Rn
¤ ®
∀x ∈ K : O f (x ) d,d Ê 0 ,
Soit f : Rn → R de classe C 1 .
2. f est strictement convexe sur K si, et seulement si, pour tout x ∈ K , la
1. f est convexe sur K ⊆ Rn si, et seulement si,
matrice O2 f (x ) est définie positive :
­ ®
f (z) Ê f (x ) + Of (x ) ,z – x , ∀x,z ∈ K ­£ 2
∀d ∈ Rn ,
¤ ®
∀x ∈ K : O f (x ) d,d > 0 , d 6= 0

page 6
Chap. 1- Préliminaires A . BELFEKIH 6. Fonctions quadratiques

Exemples 1 si on écrit ce polynôme sous la forme

1
q (x ) = hx 2 – gx + c , h,g,c ∈ R
1. Prenons K = R2 et 2
alors
f (x1 ,x2 ) = 2x12 + 2x22 – 2x1 x2 – 5x1 – 2x2 q 0 (x ) = hx – g , q 00 (x ) = h , ∀x ∈ R
A part le cas h = 0 où la courbe de q est une droite, le courbe de q est strictement
alors
convexe si h > 0 ou strictement concave si h < 0. C’est une parabole dont la conca-
µ ¶
4 –2
O2 f (x1 ,x2 ) = vité est dirigée vers le haut si h > 0 ou vers le bas si h < 0.
–2 4
de valeurs propres λ1 = 2 et λ2 = 6. Donc f est strictement convexe sur R2 .
6.2 FONCTIONS QUADRATIQUES À 2 VARIABLES
2. Prenons K le polytope limité par les droites x2 = – π4 – x1 et x2 = π4 – x1 :
une fonction quadratique à 2 variables est de la forme
n π π o
q x,y = ax 2 + bxy + cy 2 + px + qy + r
¡ ¢
K = (x1 ,x2 ) / – – x1 É x2 É – x1
4 4
ax + 21 by
¿µ ¶ µ ¶À ¿µ ¶ µ ¶À
x p x
et = 1 , + , +r
2 bx + cy y q y
f (x1 ,x2 ) = sin2 (x1 + x2 ) *Ã !µ ¶+ ¿µ
a b2
¶ µ ¶ µ ¶À
x x p x
alors = b , + , +r
1 1
µ ¶
2 c y y q y
2
O f (x1 ,x2 ) = 2cos (2 (x1 + x2 ))
1 1 donc
q (x ) = 21 〈Ax,x 〉 – b,x + r , x ∈ R2
­ ®
de valeurs propres λ1 = 0 et λ2 = 4cos (2x1 + 2x2 ) . On vérifie que λ2 Ê 0 sur K
car avec µ ¶ µ ¶
π π π π 2a b –p
– – x1 É x2 É – x1 ⇒ – É (2x1 + 2x2 ) É ⇒ cos (2x1 + 2x2 ) Ê 0 A= , b=
b 2c –q
4 4 2 2

6.3 FONCTION QUADRATIQUE À PLUSIEURS VARIABLES

6 - Fonctions quadratiques Plus généralement une fonction quadratique est donnée par
n n
αij xi xj +
X X ­ ®
q (x ) = bi xi + c = 〈Dx,x 〉 – b,x + r
6.1 FONCTIONS QUADRATIQUES À UNE VARIABLE i,j =1 i=1
Ce sont les polynômes de degré É 2 : avec
α11 α1n –b1
   
···
q (x ) = ax 2 + bx + c , a,b,c ∈ R  ..
D= . ..
.
.. 
, b=
 .. 
.  . 
αn1 ··· αnn –bn

page 7
Chap. 1- Préliminaires A . BELFEKIH 6. Fonctions quadratiques

D n’est pas symétrique. En posant A = D + D T on a Théorème 4 :

1
­1 ¡ T¢ ® 1¡ ­ T ®¢ 1 • Si A est définie positive alors q admet un minimum global unique x ∗ ∈
2 〈Ax,x 〉 = 2 D + D x,x = 2 〈Dx,x 〉 + D x,x = 2 (〈Dx,x 〉 + 〈x,Dx 〉) Rn
= 21 (〈Dx,x 〉 + 〈Dx,x 〉) = 〈Dx,x 〉 q x ∗ É q (x ) , ∀x ∈ R2
¡ ¢

donc qui coïncide avec l’unique solution du système linéaire Ax ∗ = b.

T
q (x ) = 21 〈Ax,x 〉 – b,x + r avec A = A
­ ®
• Si A est définie négative alors q admet un maximum global unique x ∗ ∈
Rn
q x ∗ Ê q (x ) , ∀x ∈ R2
¡ ¢
Proposition 4 :
La fonction quadratique qui coïncide avec l’unique solution du système linéaire Ax ∗ = b.

q (x ) = 21 〈Ax,x 〉 – b,x + r avec AT = A

­ ®

est différentiable à tout ordre son gradient et sa hessienne sont Théorème 5 :

Supposons que le système linéaire Ax = b admet une solution a.
Oq (x ) = Ax – b , O2 q (x ) = A , ∀x ∈ Rn
• Si A est semi-définie positive alors a est un minimum global de q ;

Dès que n Ê 2 les fonctions quadratiques sont parfois convexes parfois concaves • Si A est semi-définie négative alors a est un maximum global de q.
et le reste du temps aucune de ces deux propriétés. Plus précisément :

Théorème 3 :
• q est convexe sur Rn si, et seulement si, la matrice A est semi-définie 6.4 FONCTION QUADRATIQUE ASSOCIÉE À UNE FONCTION 2
positive ; FOIS DIFFÉRENTIELLE
• q est strictement convexe sur Rn si, et seulement si, la matrice A est Soit a ∈ Rn fixé et f : Rn → R 2 fois différentiable. On lui associe la fonction quadra-
définie positive ;Elle est convexe sur Rn si A est semi-définie positive. tique

1 ­£ 2
O f (a) (x – a) ,x – a – Of (a) ,x – a + f (a) , x ∈ Rn
¤ ® ­ ®
En effet dans ce cas on a q (x ) =
2
∀x ∈ Rn , O 2 q (x ) = A
La nature de f autour de a est la même que celle de q autour de a. Plus précisé-
on applique alors le théorème précédent. ment :

page 8
Chap. 1- Préliminaires A . BELFEKIH 7. Point-selle

admet (0,0,0) pour point-selle car

Proposition 5 :
1. f est convexe dans un voisinage de a si, et seulement si, q est convexe ;
¡ 2
0 + 02 – z 2 É 02 + 02 – 0 2 É x 2 + y 2 – 0 2 , ∀ x,y,z ∈ Ω = ]–1,1[3
¢ ¡ ¢ ¡ ¢

2. f est strictement convexe dans un voisinage de a si, et seulement si, q

3. La fonction f x,y = x 2 – 4y 2 x admet (0,0) pour point-selle.
¡ ¢
est strictement convexe ;

3. a est un point critique de f si, et seulement si, a est un point critique

de q ;
Proposition 6 :
4. a est un minimum de f si, et seulement si, a est un minimum de q. Tout point-selle a ∈ Rn de f est un point critique de f :

Of (a) = 0

7 - Point-selle La réciproque est fausse.

Soient p,q entiers non nuls n = p + q, f : Rp × Rq → R et x ∗ ,y ∗ ∈ Rp × Rq = Rn .

¡ ¢
Proposition 7 :
Si a est un point critique de f et si la hessienne de f en ce point admet
Définition 10
certaines v.p. > 0 et d’autres < 0 alors a est un point-selle.
On dit que x ∗ ,y ∗ est un point-selle de f s’il existe un ensemble ouvert
¡ ¢

convexe Ω ⊆ Rn contenant x ∗ ,y ∗ tel que

¡ ¢

f x ∗ ,y É f x ∗ ,y ∗ É f x,y ∗ , ∀ x,y ∈ Ω Proposition 8 :

¡ ¢ ¡ ¢ ¡ ¢ ¡ ¢

Soit a ∈ Rn un point critique de f et A = O2 f (a) .

c.a.d. x ∗ est un minimum local de x → f x,y ∗ et y ∗ est un maximum local de
¡ ¢
¡ ∗ ¢ 1. Si toutes les valeurs propres de A sont > 0 alors a est un minimum local
y → f x ,y .
de f ;

Exemples 2 2. Si toutes les valeurs propres de A sont < 0 alors a est un maximum local
= x2 – y 2 de f ;
¡ ¢
1. La fonction f x,y admet (0,0) pour point-selle car
3. Si certaines valeurs propres de A sont > 0 et d’autres < 0 alors a est un
02 – y 2 É 02 – 02 É x 2 – 02 , ∀ x,y ∈ R2
¡ ¢
point-selle de f .

2. La fonction
f x,y,z = x 2 + y 2 – z2
¡ ¢

page 9
Chap. 1- Préliminaires A . BELFEKIH 8. Problèmes d’optimisation

Exemple 2 8.2 PROBLÈME SANS CONTRAINTES

Prenons C’est le cas où
f x,y,z = x 4 + y 4 – z4 + αx 2 + αy 2 – βz2 , α, β ∈ R∗
¡ ¢
K = Rn
alors les problèmes sont alors
2x ¡α + 2x 2 ¢ 12x 2 + 2α
¡ ¢ 
0 0
  
½
2 Minimiser ou Maximiser f (x )
Of =  2y ¡α + 2y 2 ¢  , O f = 0 12y 2 + 2α 0
x ∈ Rn

–2z β + 2z2 0 0 2
–12z – 2β

son gradient est nul en (0,0,0) et sa hessienne vaut en ce point 8.3 PROBLÈME AVEC CONTRAINTES
2α 0 0 C’est le cas où
 
 0 2α 0  K 6= Rn
0 0 –2β
a) Problème avec contraintes égalités
de valeurs propres λ1 = 2α et λ2 = –2β :
Ce sont des problèmes du type
1. Si α > 0 et β < 0 alors λj > 0 : c’est un minimum ;
 Minimiser ou Maximiser f (x )

2. Si α < 0 et β > 0 alors λj < 0 : c’est un maximum ; g (x ) = 0
 i
1ÉiÉp
3. Si α > 0 et β > 0 (ou l’inverse) alors λ1 > 0 et λ2 < 0 (ou l’inverse) : c’est un
point-selle. On pose
, gi : Rn → R
© ª
K = x / gi ( x ) = 0 , 1 É i É m
Remarque 4 ce qui donne un problème avec contraintes.
Cette condition sur les valeurs propres n’est pas nécessaire. Il existe des points-
selle où la hessienne est nulle (et donc toutes ses valeurs propres nulles). b) Problème avec contraintes inégalités

Ce sont des problèmes du type

8 - Problèmes d’optimisation  Minimiser ou Maximiser f (x )



hi (x ) É 0
8.1 DÉFINITION D ’ UN PROBLÈME D ’ OPTIMISATION 1ÉiÉq


pour K ⊆ Rn et f : K → R. ce qui correspond à l’ensemble de contraintes

½ ½
Minimiser f (x ) Maximiser f (x )
, hi : Rn → R
© ª
ou K = x / h i (x ) É 0 , 1 É i É p
x∈K x∈K

page 10
Chap. 1- Préliminaires A . BELFEKIH 8. Problèmes d’optimisation

c) Problème avec contraintes égalités-inégalités

C’est le cas où on a les deux types de contraintes

 Minimiser ou Maximiser f (x )


gi (x ) = 0, 1 É i É p
hi (x ) É 0, 1 É i É q


ce qui correspond à l’ensemble de contraintes

© ª
K = x / gi (x ) = 0, 1 É i É p et hj (x ) É 0, 1 É j É q

page 11