Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

1. Quelques rappels et généralités

Cette partie est destinée à rappeler quelques notions nécessaires pour l'optimisation
statique.
1.1. Les matrices
1.1.1.

Une matrice (1,1) est juste un scalaire a. Le déterminant de cette matrice est égal à
a.
Matrice (2,2) : soit le déterminant de M s'écrit
Matrice (n,n) : soit

Pour calculer le déterminant de M,

selon la première ligne » :
on associe à chaque coefficient de la première ligne de la matrice M un signe
+ si i est impair et un signe - si i est pair.
Le déterminant de M n
(n 1) obtenus en éliminant de la matrice M la ligne et la colonne contenant le
coefficient . Chacun de ces déterminants est multiplié par
Exemple:
Calculer les déterminants des matrices suivantes

B=

1.1.2.
Soit M une matrice carré symétrique de dimension (n, n). Un mineur principal
k est le déterminant de la sous-matrice de M k obtenue en supprimant (n
k) lignes et les (n k) colonnes correspondantes dans M.

Exemple : Soit M =

sont: , , et .
Les trois sont: ,

et

Exemple :

Déterminer les mineurs principaux de M

Page 1
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

1.1.3.
Soit M une matrice carré symétrique de dimension (n, n). Le mineur principal diagonal
k (noté Dk) de la matrice M est le déterminant de la matrice de taille (k, k)
obtenue en éliminant les (n k) dernières lignes et (n k) dernières colonnes de la matrice
M n admet n mineurs principaux diagonaux.

Exemple : Soit M =

Le mineur principal diagonal M est: .

est:

Le mineur principal diagonal

Exemple : Soit M1 = M2 =

Déterminer les mineurs principaux diagonaux de M1 et M2

1.1.4. Valeur propre / vecteur propre

Si A est une matrice carrée de dimension n, est un polynôme de
degré n en

On l'appelle polynôme caractéristique de A

On dit qu'un scalaire est une valeur propre de la matrice carrée A de dimension n
lorsqu'il existe un vecteur non nul tel que:

Un tel vecteur V s'appelle vecteur propre de A associé à la valeur propre .

Théorème:
Les valeurs propres d'une matrice A sont les racines de son polynôme caractéristique.
Exemple: Déterminer les valeurs propres des matrices suivantes.

1.1.5. Matrices (semi) définies négatives, matrice (semi) définies positives

[Link]. Matrice définie positive
Soit M une matrice carrée symétrique. Soit A un vecteur colonne quelconque. On note A
sa transposée. M est dite définie positive si et seulement si :

NB: Les éléments diagonaux aii > 0.

équivalent à dire que toutes les valeurs propres de M sont strictement positives.

Page 2
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

[Link]. Matrice semi-définie positive

Soit M une matrice carrée symétrique. Soit A un vecteur colonne quelconque. On note A
sa transposée. M est dite semi-définie positive si et seulement si :

NB: Les éléments diagonaux aii -définie positive sont tous 0.

aussi équivalent à dire que toutes les valeurs propres de M sont positives.
[Link]. Matrice définie négative
Soit M une matrice carrée symétrique. Soit A un vecteur colonne quelconque. On note A
sa transposée. M est dite définie négative si et seulement si :

NB: Les éléments diagonaux aii 0.

[Link]. Matrice semi-définie négative

Soit M une matrice carrée symétrique. Soit A un vecteur colonne quelconque. On note A
sa transposée. M est dite semi-définie négative si et seulement si :

N.B. : Les éléments diagonaux aii -définie positive sont tous 0.

[Link]. Caractérisation des matrices

[Link].1. Méthode basée sur les mineurs principaux
Soit M n.
M définie positive tous ses n mineurs principaux diagonaux Dk sont
strictement positives.
M définie négative si et seulement si tous ses n mineurs principaux diagonaux
(Dk) changent alternativement de signe le premier étant négatif.
est du signe de

Si l'un des mineurs principaux diagonaux d'ordre k est non nul mais ne respecte
pas l'une de ces deux structures de signe alors M est indéfinie.
M semi-définie positive tous ses mineurs principaux (et pas seulement
diagonaux Dk) sont tous 0. (Si chaque mineur principal de M est positif ou nul)
M semi-définie négative tous ses mineurs principaux Dk (et pas seulement
diagonaux) sont alternativement 0(k impair) et 0 (k pair). Chaque mineur
principal d'ordre impair est négatif ou nul et si chaque mineur principal d'ordre
pair est positif ou nul.
[Link].2. Méthode basée sur les valeurs propres
M est définie positive ssi toutes les valeurs propres de M sont positives;
M est définie négative ssi toutes les valeurs propres de M sont négatives;
M est semi-définie positive ssi toutes les valeurs propres de M sont positives ou
nulles;
M est semi-définie négatives ssi toutes les valeurs propres de M sont négatives ou
nulles; et
M est indéfinie ssi M a une valeur propre positive et une valeur propre négative.
Exemple: Caractériser les matrices précédentes des points 2) et 4)

2. Fonctions
Soit f : U R une fonction de n variables (x1, x2, ..., xn
de définition U constitue un sous-ensemble de Rn. On supposera toujours que f est
continue et deux fois différentiable. On note la dérivée partielle de f par rapport à xi

Page 3
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

et on note la dérivée croisée de f par rapport à xi et xj

2.1. Matrice hessienne

On appelle matrice hessienne H(x1, x2, ..., xn) de f la matrice des dérivées secondes
de f évaluées au point (x1, x2, ..., xn) :

NB: Comme (i, j), la matrice hessienne de f est une matrice symétrique
d'ordre n.

2.2. Matrice hessienne bordée

On appelle matrice hessienne bordée de f la matrice des dérivées
secondes de f, bordée par la matrice des dérivées premières de f :

La matrice hessienne bordée de f n+ 1.

Exemple : Déterminer la matrice hessienne et hessienne bordée de f au point A(1,1,1) de
f(x,y,z) = x2y2z2.

2.3. Matrice jacobienne

Soit G = (g1, g2, ..., gm) une fonction définie de Rn dans Rm. A tout vecteur
la fonction G associe le vecteur de fonctions (g1( ), g2( ), ..., gm( )). On
appelle matrice jacobienne de G la matrice de dimension (m, n) JG des
dérivées partielles des m fonctions qui composent G

JG

Exemple: Déterminer la Jacobienne de la fonction suivante

2.4. Ensembles (strictement) convexes

2.4.1. Ensemble convexe
Un ensemble S de Rn est convexe ssi, (x, y) S2 :
(1 )x + S, [0, 1].

Page 4
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

Intuitivement, un ensemble convexe est tel que tout segment reliant deux points de cet

Exemple: convexe non convexe

2.4.2. Ensemble strictement convexe

Un ensemble S de Rn est strictement convexe ssi, (x, y) S2 :
(1 )x + intérieur S, [0, 1].
N.B. :
2.5. Fonctions concaves (convexes)
Soit f une fonction de plusieurs variables définie sur un ensemble convexe S.

2.5.1. Fonction concave

f est concave sur S ssi, (x, y) S2 et [0, 1], on a :
f((1 )x + ) (1 )f(x) + (y)
f est strictement concave sur S ssi :
f((1 )x + > (1 )f(x) + (y)

Autrement dit, une fonction f est concave ssi le segment reliant tout couple de points
situés sur la surface définie par f est situé au-dessous de cette surface.

Exemple:

2.5.2. Fonction convexe

f est convexe sur S ssi, (x, y) S2 et [0, 1], on a :
f((1 )x + (1 )f(x) + (y)
f est strictement convexe sur S ssi :
f((1 )x + < (1 )f(x) + (y)

Autrement dit, une fonction f est convexe si le segment reliant tout couple de points
situés sur la surface définie par f est situé au-dessus de cette surface.

N.B. : ensemble convexe avec celle de

fonction convexe.
Propriétés importantes

Page 5
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

f concave f convexe
Si f et g sont des fonctions concaves (resp. convexes), alors (a, b) R2+,
(a.f+b.g) est une fonction concave (resp. convexe).
Si f est une fonction concave et g est une fonction croissante et concave, alors la
fonction g(f(x)) est concave.
Si f est une fonction convexe et g est une fonction croissante et convexe, alors la
fonction g(f(x)) est convexe.
Une fonction affine est à la fois concave et convexe.

Caractérisation pour les fonctions à une seule variable

f concave f (x) 0 x R.
f (x) < 0 x R f
nécessairement vraie).
f convexe f (x) 0 x R.
f (x) > 0 x R f
nécessairement vraie).

Caractérisation pour les fonctions à plusieurs variables

f concave la matrice hessienne de f est semi-définie négative x Rn.
la matrice hessienne de f est définie négative x Rn f strictement concave

f convexe la matrice hessienne de f est semi-définie positive x Rn.

la matrice hessienne de f est définie positive x Rn f strictement convexe

Exemple : Préciser si les fonctions suivantes sont (strictement) concaves ou convexes

f(x, y) = (x 2)2 + (y 2)2.
f(x, y) = 6 (x+2)2 (y+2)2
f(x, y, z) = x2 + 2y2 + 3z2 + 2xy + 2xz

2.6. Fonctions quasi-concaves (convexes)

2.6.1. Fonctions quasi-concaves
Une fonction à valeurs réelles f définie sur Rn est dite quasi-concave ssi ses contours
supérieurs forment des ensembles convexes, c.-à-d. P={ Rn : f(
c} est convexe pour toutes les valeurs de c.

2.6.2. Fonctions strictement quasi-concaves

Une fonction à valeurs réelles f définie sur Rn est dite strictement quasi-concave ssi ses
contours supérieurs forment des ensembles convexes, c.-à-d. P={ Rn :
f( c} est strictement convexe pour toutes les valeurs de c.
2.6.3. Fonctions quasi-convexes
Une fonction à valeurs réelles f définie sur Rn est dite quasi-convexe si ses contours
inférieurs forment des ensembles convexes, c.-à-d. si P = { Rn : f( c} est convexe
pour toutes les valeurs de c.

2.6.4. Fonctions strictement quasi-convexes

Une fonction à valeurs réelles f définie sur Rn est dite strictement quasi-convexe si ses
contours inférieurs forment des ensembles convexes, c.-à-d. si P = { Rn : f( c} est
strictement convexe pour toutes les valeurs de c.

Page 6
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

Propriétés importantes :
o f concave (resp. convexe) f quasi-concave (resp. quasi-convexe) (attention : la

o f quasi-concave ( f) quasi-convexe.
o La somme de deux fonctions quasi-concaves (resp. quasi-
nécessairement une fonction quasi-concave (resp. quasi-convexe).
o
fonction quasi-concave (resp. quasi-convexe) : si f est une fonction concave (resp.
convexe) et g est une fonction monotone, alors la fonction g(f(x)) est quasi
concave (resp. quasi-convexe).

Caractérisation
f quasi-concave les mineurs principaux diagonaux Dk de la matrice hessienne
bordée de f alternent en signe à partir de k = 3, avec Dk >= 0 pour k impair et Dk
<= 0 (k pair). x Rn
Les mineurs principaux diagonaux Dk de la matrice hessienne bordée de f
alternent en signe à partir de k = 2, avec Dk > 0 pour k impair et Dk < 0 (k pair)
x Rn f quasi-concave.
f quasi-convexe les mineurs principaux diagonaux Dk de la matrice hessienne
bordée de f sont tous <= 0 à partir de k = 3 x Rn
pas nécessairement vraie).
Les mineurs principaux diagonaux Dk de la matrice hessienne bordée de f sont
tous < 0 à partir de k = 2 x Rn f quasi-convexe.
Exemple : Trouver une condition suffisante sur x et y
fonction f(xy)= xy est quasi-concave. (Solution x et y sont strictement positifs)

Page 7
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

2. Optimisation statique
2.1.
minimum ou de maximum (en un mot
extremum réelles f appelée fonction objectif (par exemple
coût, profit, charges, etc.) définie sur un ensemble E
maximiser sur un ensemble E dont les éléments sont appelés les points réalisables ou
admissibles.
2.1.1. Notations

maximisation sous contraintes et sous la forme :

max f(x1, x2, ..., xn)
P x1,x2,...,xn
s.c. contrainte(j) j = 1, ...,m (avec s.c. pour « sous contraintes»)

minimisation sous contraintes.

min f(x1, x2, ..., xn)

P' x1,x2,...,xn
s.c. contrainte(j) j = 1, ...,m

La fonction f est appelée fonction objectif. Le programme consiste à chercher les valeurs
pour laquelle la valeur de cette fonction est maximale (ou minimale) sous
les contraintes. On appelle Optimum
maximum minimum.
sans contraintes.

2.1.2. Les contraintes

Les contraintes peuvent prendre plusieurs formes distinctes :
contraintes en équations : gj(x1, x2, ..., xn) = cj j = 1, ...,m
contraintes en inéquations : gj(x1, x2, ..., xn) <= cj j = 1, ...,m
contraintes de non-négativité : xi >= 0 i = 1, ..., n

2.1.3. Définitions
Maximum, minimum
La valeur qui résout le programme P est un maximum de la fonction f sous les
contraintes du programme.
La valeur qui résout le programme P est un minimum de la fonction f sous les
contraintes du programme.

Optimum local
La variable x* f S
> 0 tel que f(x) <= f(x*) x S et |x x*| <=
La variable x* f S
> 0 tel que f(x) >= f(x*) x S et |x x*| >=

Optimum global
La variable x* f
S f(x) <= f(x*) x S
La variable x* f

Page 8
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

S f(x) >= f(x*) x S

2.1.4. Remarques
Transformation de la fonction objectif
Soit g une fonction à une seule variable
solutions du programme
max f(
P
s.c. contraintes
*:
max g(f( )
P*
s.c. contraintes
Transformation des programmes de minimisation
Tout programme de minimisation peut aisément être transformé en programme de
maximisation en remplaçant la fonction objectif f par son opposée f :
min f( max -f(

s.c. contraintes s.c. contraintes

Transformation de contraintes d'inéquations
gj(x1, x2, ..., xn) >= cj -gj(x1, x2, ..., xn) <= -cj j = 1, ...,m

programmes de maximisation sous contraintes. On précisera, en cas de besoin, comment

adapter la méthode de résolution au cas des programmes de minimisation sous
contraintes.

2.1.5.
Pour trouver la solution
traditionnellement deux types de conditions :

Les conditions du premier ordre (CPO) sont les conditions nécessaires que doit

Les conditions du second ordre (CSO) garantissent que les conditions du premier
ordre sont suffisantes pour que

Page 9
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

2.2. Optimisation sans contraintes (ou libres)

2.2.1.
f
maximise sans contrainte.
On considère le programme de maximisation P suivant :
max f(
P

Condition du premier ordre

Si x* est une solution du programme de maximisation P, alors x* vérifie :
f (x*) = 0

Conditions du second ordre pour un optimum local

x* qui vérifie la CPO. Alors :
x* est un maximum local f''(x*) 0
f (x*) < 0 x* est un maximum local
x* est un minimum local f (x*) 0
f (x*) > 0 x* est un minimum local

Conditions suffisantes du second ordre pour un optimum global

x* qui vérifie la CPO. Alors :
f (x) 0 x (f est concave) x* est un maximum global
f (x) 0 x (f est convexe) x* est un minimum global

Exemple
Trouver max f(x) = (x 2)2+5 min f(x) = 2x2+2 x +1

2.2.2.
Soit une fonction f à n variables.
On considère le programme de maximisation P suivant :

Conditions du premier ordre

Si est une solution du programme de maximisation , alors
vérifie :
i = 1, ..., n

Conditions du second ordre pour un optimum local

qui vérifie les CPO. Alors :
H( ) est définie négative est un maximum local
est un maximum local H( ) est semi-définie négative
H( ) est définie positive est un minimum local
est un minimum local H( ) est semi-définie positive où H( ) désigne la matrice
hessienne de f évaluée au point .

Page 10
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

Conditions suffisantes du second ordre pour un optimum global

qui vérifie les CPO. Alors :
H( ) est semi-définie négative (f est concave) est un maximum global

H( ) est semi-définie positive (f est convexe) est un minimum global où H( )

désigne la matrice hessienne de f évaluée au point .

Exemple
Résoudre le programme de maximisation:
P : max f(x, y) = 3xy x3 y3
x,y
Solution : (0, f et (1, 1) est un maximum local, mais
pas un maximum global de f.

2.3.
f à n variables sous m contraintes
de la forme : gj(x1, x2, ..., xn) = cj , j = 1, ...,m

2.3.1. Cas à une seule contrainte

On considère le programme de maximisation P suivant :
max f(
P
s.c g(
Lagrangien : On appelle Lagrangien, noté L, la fonction suivante :
L( ) = f( ) (g( ) c)
où la variable est appelée multiplicateur de Lagrange associé à la contrainte.

Conditions de qualification de la contrainte

Pour pouvoir utiliser le Lagrangien dans la résolutio

(a) Les dérivées partielles de la fonction contrainte g ne sont

pas simultanément nulles, c.-à-d. pour au moins un xi, i = 1, ..., n.
(b) La fonction contrainte g est linéaire.

N.B. : Les conditions de qualification des contraintes garantisse

a pas de contraintes potentiellement contradictoires.

Conditions du premier ordre

On suppose que la contrainte de qualification est vérifiée. Si le vecteur
est une solution du programme de maximisation P, alors il existe un
unique tel que x* vérifie les n + 1 conditions suivantes :

Page 11
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

Matrice hessienne bordée du Lagrangien dans le cas à une seule contrainte

On appelle matrice hessienne bordée du Lagrangien HL évaluée au point la matrice des
dérivées partielles secondes de L par rapport à xi bordée par les dérivées partielles
premières de la fonction contrainte g :

Conditions suffisantes du second ordre pour un optimum local

qui vérifie les CPO.
Les n 1 derniers mineurs principaux diagonaux de la matrice hessienne bordée du
Lagrangien HL( > 0 et < 0, le dernier
n
Dn+1) étant de même signe que ( 1) est un maximum local.
Les n 1 derniers mineurs principaux diagonaux de la matrice hessienne bordée du
Lagrangien HL( <0 est un minimum local.

Conditions suffisantes du second ordre pour un optimum global

qui vérifie les CPO. Alors :
Le Lagrangien L est une fonction concave (ce qui est le cas en particulier si f est
concave et si est convexe) est un maximum global.
Le Lagrangien L est une fonction convexe (ce qui est le cas en particulier si f est
convexe et est concave) est un minimum global.

Exemple:
max f(x,y
P x,y
s.c x+y=6
Solution : Le programme P admet un maximum local en (3, 3).

2.3.2. Cas à m contraintes

Le programme précédent se généralise aisément au cas à m contraintes.
On considère le programme de maximisation P suivant (où ):
max f(
P
s.c gj(

Lagrangien : On appelle Lagrangien, noté L, la fonction suivante :

L( , j) = f( )
où les variables sont appelées multiplicateurs de Lagrange associé aux j contrainte et
.

Page 12
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

Conditions de qualification des contraintes

vérifiée :
(a) La matrice jacobienne des fonctions contraintes gj , j = 1, ...,m, notée JG et de taille
(m, n) est de rang m x*.
(b) Les fonctions contraintes gj sont toutes linéaires.

N.B. : uées ici) portant sur les fonctions contraintes

qui permettent de garantir que la condition de qualification de la contrainte est vérifiée.

On suppose que la contrainte de qualification est vérifiée. Si le vecteur

est une solution du programme de maximisation P, alors il existe un
unique tel que vérifie les n + m conditions suivantes :

Matrice hessienne bordée du Lagrangien dans le cas à m contraintes

On appelle matrice hessienne bordée du Lagrangien dans le cas à m contraintes la
matrice hessienne du Lagrangien (dérivées partielles secondes de L par rapport à xi
bordée par les dérivées partielles premières des m fonctions contraintes gj , évaluée au
point :

m + n.

Conditions suffisantes du second ordre pour un optimum local

qui vérifie les CPO.
Les n m derniers mineurs principaux diagonaux de la matrice hessienne bordée du
Lagrangien HL( , > 0 et < 0, le dernier
n
Dn+m) étant de même signe que ( 1) est un maximum local.
Les n m derniers mineurs principaux diagonaux de la matrice hessienne bordée du

Page 13
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

Lagrangien HL( , même signe que

( 1)m est un minimum local.

Conditions suffisantes du second ordre pour un optimum global

qui vérifie les CPO. Alors :
Le Lagrangien L est une fonction concave (ce qui est le cas en particulier si f est
concave et si est convexe j=1,...,m) est un maximum global.

Le Lagrangien L est une fonction convexe (ce qui est le cas en particulier si f est
convexe et est concave j=1,...,m) est un minimum global.

Exemple : Résoudre le programme de maximisation

P :max x2 + y2 + z2
x,y,z
s.c. x + 2y + z = 1 et 2x y 3z = 4
Solution ( 1 2) = (16/15,1/3, 11/15,52/75,54/75) maximum global

2.4.
Kuhn et Tucker
On considère le programme de maximisation P suivant :
max f(
P
s.c g(
Soit la solution de ce programme. Deux situations sont envisageables pour chaque
contrainte j
soit gj( ) = cj : dans ce cas, on dit que la contrainte j est saturée
soit gj( ) < cj : dans ce cas, on dit que la contrainte j est non saturée

Comme précédemment, on définit le Lagrangien comme la fonction L suivante :

Lagrangien : On appelle Lagrangien, noté L, la fonction suivante :
L( , ) = f( ) -
où les variables sont appelées multiplicateurs de Lagrange associé aux j contrainte et
.

Conditions de qualification des contraintes

suivantes soit vérifiée :

(a) Soit s <= m m . On suppose sans perte
s premières contraintes gj , j = 1, ..., s. Si la matrice
jacobienne de ces s fonctions contraintes, notée JG et de taille (s, n), est de rang s
, alors la condition de qualification des contraintes
est vérifiée.
(b) Les fonctions contraintes gj , j = 1, ..., s sont toutes linéaires.

Les conditions du premier ordre que doit vérifier toute solution , du programme P
sont légèrement modifiées par rapport au cas précédent (contraintes prenant la forme

pour propriété que le multiplicateur de Lagrange j associé à la contrainte j est nul

Page 14
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

Conditions du premier ordre (Kuhn et Tucker)

On suppose que la contrainte de qualification est vérifiée. Si le vecteur
est une solution du programme de maximisation P, alors il existe un
unique vecteur tel que vérifie les n + 3m conditions suivantes :

= 0 et gj( ) = cj simultanément.
En pratique, la résolution des conditions de Kuhn et Tucker est compliquée par le fait

j sont
a bonne solution, il faut procéder par élimination, en

contradictions.

Conditions suffisantes du second ordre pour un optimum local

qui vérifie les CPO. Soit s le nombre de contraintes saturées
la matrice hessienne du Lagrangien bordée par les
s
+ n.

Les n s derniers mineurs principaux diagonaux de la matrice ( , ) évaluée à

> 0 et < Dn+s) étant de même
signe que ( 1)n est un maximum local.

Les n s derniers mineurs principaux diagonaux de la matrice ( , ) évaluée à

1)m est un minimum local.

Conditions suffisantes du second ordre pour un optimum global

qui vérifie les CPO. Alors :

j=1,...,m est un maximum global.

-concave et les gj sont quasi-convexes j=1,...,m et

est un maximum global.

e et les gj sont concaves j=1,...,m est un minimum global.

-convexe et les gj sont quasi-concaves j=1,...,m et

est un minimum global.
Le Lagrangien L est une fonction convexe (ce qui est le cas en particulier si f est
convexe et est concave j=1,...,m) est un minimum global.

Page 15
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

f (notées f i) est nulle au point ,

alors peut être ou ne pas être un maximum (ou un minimum) global. Pour le savoir, il
peut être utile de calculer la valeur de f en et de la comparer à la valeur prise par f pour

Note sur les programmes de inéquations

Il
forme
Soit P le programme de minimisation suivant :

Pour pouvoir appliquer les conditions de Kuhn et Tucker évoquées ci-dessus, il suffit
de transformer le programme P en un programme de maximisation P* :

P*

Exemple : Résoudre le programme de maximisation P :

Max [ (x 4)2 (y 4)2]
x,y
s.c. x + y <= 4
x + 3y <= 9
CCl : Le programme P admet un maximum global en (2, 2, 4, 0).

2.5.
contraintes de non-négativité
Dans de nombreuses applications
considérés imposent que les variables considérées ne puissent pas être négatives (le
travail ou le capital dans la fonction de production, par exemple).
On considère le programme de maximisation P suivant :
max f(
P
s.c g(

étudié dans la section précédente (il suffit de réécrire les contraintes xi > 0 sous la forme
xi la méthode
exposée précédemment exigerait de travailler avec n + m multiplicateurs de Lagrange, ce
qui est peu commode lorsque n
difié », à partir duquel
on peut dériver des conditions de Kuhn et Tucker plus simples à manipuler.

Lagrangien modifié
Le Lagrangien modifié, noté M( , ), s'écrit :

M( , ) = f( ) -

Page 16
 Cours d'Optimisation Premier Semestre de Master Sciences Economiques et de Gestion - 2019-2020

On remarquera que ce Lagrangien ne contient pas explicitement les conditions de non

négativité

Condition de qualification des contraintes

On suppose que la contrainte de qualification est vérifiée. Si le vecteur

est une solution du programme de maximisation P, alors il existe un
unique vecteur tel que vérifie les 3(n + m) conditions suivantes :

Conditions du premier ordre (Kuhn et Tucker)

Conditions suffisantes du second ordre pour un optimum local

Conditions suffisantes du second ordre pour un optimum global : Cf. cas précédent.

incluant des contraintes de non-négativité est compliquée par le fait que non seulement il
faut envisager toutes les configurations possibles pour les j , mais aussi toutes les
configurations possibles pour les variables xi : elles sont strictement positives à

solution, il faut ensuite procéder par éliminatio

possibilités, certaines aboutissent à des contradictions. Une solution pour laquelle un ou
plusieurs xi

Exemple : Résoudre le programme de maximisation P :

max
x,y
s.c.

Le programme P admet un maximum global en (3, 3).

Page 17