Optimisation dans Rn (et ailleurs ?

) : quelques
résultats de base
G. Barles
Master de Mathématiques de TOURS

Quand on veut traiter des problèmes d’optimisation (qui se présentent généralement

sous la forme min f ou max f ), on est confronté à trois types de questions :
K K
(i) Existence du (ou des) point(s) de minimum ou de maximum, donc existence (ou
pas) de la solution du problème.
(ii) Unicité éventuelle de cette solution.
(iii) Propriété d’optimalité : quelle(s) équation(s) cette solution satisfait-elle ? On
pense évidemment à un gradient nul en un point de minimum ou de maximum
local.
L’objectif de ce mini-cours est de décrire les résultats de base dans ces trois directions.

1 Existence
À tout seigneur, tout honneur, nous commençons par le :

Théorème 1.1. Soit K ⊂ Rn un compact et f : K → R une fonction continue. Il existe

au moins deux points x0 , x1 ∈ K tels que :

f (x0 ) = min f et f (x1 ) = max f .

K K

En d’autres termes, sous les conditions du Théorème 1.1, nos problèmes d’optimisation
ont au moins une solution.
Malheureusement (ou heureusement), beaucoup de problèmes d’optimisation ne sont
pas posés sur des compacts. Il nous faut donc une (légère) généralisation du Théorème 1.1.

Théorème 1.2. Soit F ⊂ Rn un fermé et f : F → R une fonction continue qui est aussi
coercive, i.e.
f (x) → +∞ quand |x| → +∞ .
Alors il existe au moins un point x0 ∈ F tels que f (x0 ) = min f .
K

1
 La coercivité assure donc la compacité nécessaire à la résolution du problème de mi-
nimisation.

Exemples - Exercices : on considère les exemples modèles suivants qui seront repris
tout au long du cours :
(i) min (Ax, x), max (Ax, x).
|x|=1 |x|=1
(ii) min (ax + by), où a, b sont deux réels donnés.
x≥0,y≥0
x+y≤1
 
1
(iii) minn (Ax, x) − (b, x) : quelles sont les hypothèses nécessaires pour appliquer
x∈R 2
le Théorème 1.2 ? 
1
(iv) min (Ax, x) − (b, x) . Même problème.
(c,x)−d≥0 2
Exercices :
(i) Montrer, sur des exemples simples, que les hypothèses des théorèmes 1.1 et 1.2
sont (presque) optimales, en donnant des contre-exemples où l’on n’a pas forcément
de solutions si l’une d’elles n’est pas satisfaite.
(ii) Prouver néanmoins que les théorèmes 1.1 et 1.2 restent vrais si on suppose seule-
ment f s.c.i
(iii) (sujet d’étude) Que se passe-t-il si on remplace Rn par un espace de Hilbert ?

2 Unicité
Dans cette section, le message est très simple : dans le cas de problèmes de minimi-
sation (sur lesquels on va désormais se concentrer laissant les problèmes de maximisa-
tion en exercices (faciles)), la seule hypothèse qui fournit des résultats généraux est la
stricte convexité ; encore faut-il pouvoir l’appliquer ce qui nécessite un domaine convexe.
D’où la définition suivante.
Définition 2.1.
– Un sous-ensemble A ⊂ Rn est convexe si, pour tous x, y ∈ A et pour tous α ∈ [0, 1],
αx + (1 − α)y ∈ A.
– Si A est convexe et si f est une application de A dans R, on dit que f est convexe
si, pour tous x, y ∈ A et pour tout α ∈ [0, 1],

f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y) .

Enfin, f est dite strictement convexe si cette inégalité est stricte pour tous x 6= y et
α ∈]0, 1[.
Théorème 2.1. Soit F un sous-ensemble convexe de Rn et f : F → R une fonction
continue, strictement convexe. Alors le problème d’optimisation min f a au plus une so-
F
lution.

2
Exemples - Exercices :
(i) Reprendre les exemples donnés ci-dessus et voir dans quels cas le théorème d’unicité
s’applique.
(ii) Donner un exemple de fonction convexe dans R qui a plusieurs points de minimum.

3 Conditions d’optimalité
Comme nous l’avons déjà fait ci-dessus, nous nous concentrons sur les problèmes de
minimisation, laissant, au lecteur, les adaptations (évidentes) aux problèmes de maximi-
sation.
Là aussi à tout seigneur, tout honneur.
Théorème 3.1. Soit D un sous-ensemble quelconque de Rn et f : D → R. Si x ∈ D est
un point de minimum local de f sur D et si x est un point intérieur à D alors :
(i) Si f est dérivable en x alors ∇f (x) = 0.
(ii) Si f est de classe C 1 dans un voisinage de x et si f est deux fois dérivable en x
alors on a ∇f (x) = 0 et D2 f (x) ≥ 0.
Exercices :
(i) Reprendre les exemples modèles donnés ci-dessus et voir dans quels cas le Théorème 3.1
s’applique.
(ii) Étudier les points critiques de la fonction f : R2 → R définie par :
f (x, y) = x3 + y 3 − 3x − 3y ,
et donner leurs natures.
1/2
(iii) Si |x| = (x21 + · · · x2n ) , étudier le problème d’optimisation :
min |x| .
|x|≤1

Quels sont les points critiques ? Comment trouve-t-on le ou les points de minimum ?

Le théorème 3.1 ne donne de résultats que pour des points intérieurs à D ; il ne nous
renseigne pas pour des cas où l’intérieur de D est vide comme dans l’exemple (i) de notre
collection d’exemples modèles ou dans le cas où le minimum est atteint sur le bord de D.
Dans les cas d’optimisation avec contrainte(s) où x est tenu à appartenir à un sous-
ensemble strict de Rn , on doit disposer de résultats complémentaires et nous proposons
les deux plus classiques.
On s’intéresse d’abord au cas des contraintes d’égalités, typiquement l’exemple (i) de
notre collection d’exemples modèles. Si f : Rn → R est la fonction à minimiser (on dit
souvent le critère), on lui associe des contraintes :
G1 (x) = 0, G2 (x) = 0, · · · , Gm (x) = 0 ,
où les Gi sont des fonctions de Rn dans R ; on note G = (G1 , G2 , · · · , Gm ) : Rn → Rm .
On suppose que f et les Gi sont de classe C 1 .

3
Théorème 3.2. On note D = {x ∈ Rn ; G(x) = 0}. Si x ∈ D est un point de minimum
local de f sur D, i.e. s’il existe r > 0 tel que :

f (x) ≤ f (y) pour tout y ∈ B(x, r) ∩ D ,

et si rang{DG(x)} = m, il existe des constantes λ1 , λ2 , · · · , λm ∈ R, appelées multiplicateurs

de Lagrange telles que :

∇f (x) = λ1 ∇G1 (x) + λ2 ∇G2 (x) + · · · + λm ∇Gm (x) .

L’équation aux multiplicateurs de Lagrage semble impossible à résoudre car elle contient
n + m inconnues (les n coordonnées xi et les m multiplicateurs de Lagrange λi ) et on a
seulement n équations correspondant aux n dérivées partielles. Mais il ne faut pas oublier
les équations de contraintes G1 (x) = 0, G2 (x) =, · · · , Gm (x) = 0 qui fournissent les m
équations manquantes.

Exemple : 2min
2
(x + y).
x +y =1
Ici f (x, y) = x + y, m = 1 et G1 (x, y) = x2 + y 2 − 1. L’ensemble :

D = {(x, y) ∈ R2 ; x2 + y 2 = 1}

est compact et donc on sait qu’il existe au moins une solution (NB : de même que pour le
problème de maximisation) ; f et G1 sont de classe C 1 et DG(x, y) = DG1 (x, y) = (2x 2y)
est de rang 1 pour tout (x, y) ∈ D puisque x2 + y 2 = 1 (ce qui implique que x et y ne
peuvent pas être simultanément nuls).
Le système des multiplicateurs de Lagrange s’écrit :
∂f ∂G1
(x, y) = λ1 (x, y) −→ 1 = 2λ1 x ,
∂x ∂x
∂f ∂G1
(x, y) = λ1 (x, y) −→ 1 = 2λ1 y ,
∂y ∂y
G1 (x, y) = 0 −→ x2 + y 2 = 1 .
On a bien 3 équations à 3 inconnues. L’expérience montre qu’il est souvent plus facile de
calculer d’abord le multiplicateur de Lagrange : c’est le cas ici. En élevant au carré les
deux premières égalités et en sommant, on a :

12 + 12 = 4λ1 2 (x2 + y 2 ) = 4λ1 2 .

√
2 1 2
D’où λ1 = , i.e. λ1 = ± .
2 2
Pourquoi deux multiplicateurs possibles ? (on pourrait d’ailleurs en avoir plus...). Ici
l’explication est simple car on a un point de minimum ET un point de maximum de f sur
le cercle et ces deux points satisfont la même équations aux multiplicateurs de Lagrange.

4
 √
On√les différencie
√
par√ les valeurs des
√ √
fonctions : comme λ1 = − 22 est associé au point
(− 22 , − 22 ) et λ1 = 22 au point ( 22 , 22 ), on examine les valeurs :
√ √ √ √
2 2 √ 2 2
f (− ,− ) = − 2 −→ (− ,− ) est le point de minimum ,
2 2 2 2
√ √ √ √
2 2 √ 2 2
f( , ) = 2 −→ ( , ) est le point de maximum .
2 2 2 2

NB : faire un dessin et vérifier géométriquement que ce résultat est raisonnable !

Exercices :
(i) Traiter l’exemple (i) de la collection d’exemples modèles.
(ii) Soient 1 < p, q < +∞ deux réels. Étudier le problème d’optimisation :

min ||x||p ,
||x||q =1

où si 1 < r < +∞, ||x||r := (|x1 |r + |x2 |r + · · · + |xn |r )1/r .

(iii) Soit A une matrice n × n symétrique et λ1 < λ2 < · · · λn ses valeurs propres
(que l’on suppose donc toutes distinctes vu les inégalités strictes). Soit enfin e1 un
vecteur propre associé à λ1 . Résoudre :

min (Ax, x) .
||x||2 =1
(x,e1 )=0

(iv) Discuter le problème d’optimisation :

 
1
min (Ax, x) − (b, x) ,
(c,x)=d 2
où A une matrice n × n symétrique, b, c ∈ Rn et d ∈ R.

Preuve du Théorème 3.2 : Nous ne considèrerons que le cas m = 1, le cas général

constituant un excellent sujet d’étude.
L’hypothèse rang{DG(x)} = m = 1 se réduit à ∇G1 (x) 6= 0. On suppose, par exemple,
∂G1
que (x) 6= 0. Le Théorème des Fonctions Implicites donne alors l’existence d’un
∂xn
voisinage U de x et d’une fonction ϕ définie sur un voisinage V de (x1 , · · · , xn−1 ) dans
Rn−1 telle que :
y ∈ U et G(y) = 0 ⇐⇒ yn = ϕ(y1 , · · · , yn−1 ) .
Le fait que x soit un point de minimum local de f sur D se réinterprète en disant que
(x1 , · · · , xn−1 ) est un point de minimum local dans V de la fonction :

y 7→ f (y1 , · · · , yn−1 , ϕ(y1 , · · · , yn−1 )) .

5
Il suffit maintenant d’appliquer le Théorème 3.1 à cette fonction : pour la iième dérivée
partielle, on obtient :
∂f ∂f ∂ϕ
(x) + (x) (x1 , · · · , xn−1 ) = 0 pour i = 1, 2, · · · , n − 1.
∂xi ∂xn ∂xi
Mais, par le Théorème des Fonctions Implicites :
∂G
∂ϕ (x)
(x1 , · · · , xn−1 ) = − ∂x
∂G
i
,
∂xi ∂xn
(x)
∂f
∂xn
(x)
et en notant λ1 = ∂G
, on voit que :
∂xn
(x)

∂f ∂G
(x) = λ1 (x) pour i = 1, 2, · · · , n − 1.
∂xi ∂xi
Comme cette égalité est trivialement vraie pour i = n à cause de la définition de λ1 , la
preuve est complète.

Les résultats démontrés jusqu’à présent nous permettent de traiter tous les exemples
de notre collection d’exemples modèles sauf le (ii) ; en effet, le (iv) peut se découpler
en considérant séparément les cas où le point de minimum est atteint à l’intérieur (→
Théorème 3.1) ou sur le bord (→ Théorème 3.2).
Mais l’exemple (ii) ne permet pas cette stratégie car l’utilisation du Théorème 3.2
nécessite que le bord soit une sous-variété régulière (i.e. qu’il s’écrive sous la forme yn =
ϕ(y1 , · · · , yn−1 ) avec ϕ de classe C 1 dans un bon système de coordonnées) et les coins du
triangle sont un obstacle à cette propriété...
On a donc besoin d’un résultat plus sophistiqué : le Théorème de Kuhn et Tucker où
l’on peut mélanger toutes les contraintes possibles (égalités et inégalités).
Plus précisément, on va minimiser une fonction f de classe C 1 sur Rn sous les contraintes :

g1 (x) = 0, g2 (x) = 0, · · · , gm (x) = 0 et h1 (x) ≤ 0, h2 (x) ≤ 0, · · · , hl (x) ≤ 0 .

Ceci est le cas général car, par exemple, une contrainte du type h1 (x) ≥ 0 se réécrit
−h1 (x) ≤ 0. On note D l’ensemble des points x de Rn vérifiant ces contraintes ; on le
supposera, bien sûr, non vide.
Théorème 3.3. Si x ∈ D est un point de minimum local de f sur D et si, au point x, les
vecteurs ∇g1 (x), ∇g2 (x), · · · , ∇gm (x), ∇hj1 (x), · · · , ∇hjk (x) sont linéairement indépendants
où j1 , · · · , jk sont les indices pour lesquels hj (x) = 0, alors il existe des constantes
λ1 , λ2 , · · · , λm ∈ R et µ1 , µ2 , · · · , µl ≤ 0 telles que :
m
X l
X
∇f (x) = λi ∇gi (x) + µj ∇hj (x) ,
i=1 j=1

6
avec, pour tout j :
µj ≤ 0 et µj hj (x) = 0 .
En d’autres termes, le coefficient µj ne peut être non nul que si hj (x) = 0 donc si j =
j1 , · · · , jk .

Exercices :
(i) Écrire les conditions d’optimalité pour :
 
1
min (Ax, x) − (b, x) ,
(c,x)≤d 2
(e,x)−f =0

(ii) Résoudre le problème de la ménagère : comment maximiser son utilité (ou son
plaisir) quand on a un budget limité R (= Revenu) et que l’on peut acheter n biens
dont les prix sont notés pi (i = 1, 2, · · · , n) (ils sont, bien entendu, strictement
positifs...) ? Ceci conduit au problème :

max U (x1 , · · · , xn ) ,
Pn xi ≥0
i=1 pi xi =R

avec U (x1 , · · · , xn ) = (x1 · · · xn )α avec 0 < α < 1. Les xi sont les quantités de
chacun des biens que l’on peut (ou que l’on veut) acheter et la forme de la fonction
d’utilité U est justifiée par le fait que (i) quand on n’a pas d’un bien, on en a très
envie, d’où la pente (infinie) de la fonction t 7→ tα en 0 mais (ii) par contre, quand
on en a beaucoup, l’utilité marginale d’en avoir encore plus devient faible, d’où la
pente faible de cette même fonction pour t grand.

Preuve du Théorème 3.3 : on procède par pénalisation des contraintes, ce qui signifie
que l’on se ramène à un problème sans contraintes mais où l’on fait payer de plus en plus
cher le fait de s’éloigner du domaine D.
Plus précisément, si x est un point de minimum de f sur B(x, r) ∩ D, on introduit le
problème de minimisation :
( m l
)
2
X [gi (y)]2 X [(hj (y))+ ]2
min f (y) + |y − x| + + ,
y∈B(x,r)
i=1
ε j=1
ε

où t+ = max(t, 0) si t ∈ R et 0 < ε  1 est un paramètre destiné à tendre vers 0. Si

y satisfait les contraintes - i.e. si y ∈ D-, les deux derniers termes ont nuls ; dans le cas
contraire, on “paye” une quantité de l’ordre de 1/ε. Donc, quand ε → 0, on a de plus en
plus intérêt à satisfaire les contraintes et intuitivement les points de minimum devraient
se rapprocher de D, et le minimum devrait ressembler au minimum sur B(x, r) ∩ D... ce
qui est l’idée de la méthode.
À noter enfin le terme |y −x|2 qui transforme x point de minimum de f sur B(x, r)∩D
en un point de minimum local strict de y 7→ f (y) + |y − x|2 sur B(x, r) ∩ D.

7
 Comme B(x, r) est compact, il existe au moins un point de minimum xε ∈ B(x, r) qui
satisfait, en particulier :
m l
2
X [gi (xε )]2 X [(hj (xε ))+ ]2
(1) f (xε ) + |xε − x| + + ≤ f (x) ,
i=1
ε j=1
ε

car x ∈ B(x, r).

On déduit de (1), plusieurs informations : comme f est borné sur le compact B(x, r),
on peut introduire M = ||f ||L∞ (B(x,r)) et on a :

m
X l
X
2
[gi (xε )] + [(hj (xε ))+ ]2 ≤ (2M + r2 )ε .
i=1 j=1

De plus :
f (xε ) + |xε − x|2 ≤ f (x) .
En utilisant une nouvelle fois la compacité de B(x, r), on peut extraire une sous-suite
convergente de la suite (xε )ε , que l’on notera de la même manière pour simplifier les
notations et on peut donc supposer que xε → x.
En passant à la limite dans les deux dernières inégalités, il vient :
m
X l
X
2
[gi (x)] + [(hj (x))+ ]2 ≤ 0 ,
i=1 j=1

donc gi (x) = 0 pour tout i et hj (x) ≤ 0 pour tout j, ce qui signifie que x ∈ D. D’autre
part :
f (x) + |x − x|2 ≤ f (x) = min f .
B(x,r)∩D

Il en résulte immédiatement que x = x et en particulier xε ∈ B(x, r) pour ε assez petit

(donc xε est dans l’intérieur de B(x, r)).
Par le Théorème 3.1, on a donc :
m l
X 2gi (xε ) X 2(hj (xε ))+
(2) ∇f (xε ) + 2(xε − x) + ∇gi (xε ) + ∇hj (xε ) = 0 .
i=1
ε j=1
ε

On note alors, pour i = 1, · · · , m et j = 1, · · · , l :

2gi (xε ) 2(hj (xε ))+
λεi := − et µεj := − ,
ε ε
de telle sorte que :
m
X l
X
(3) ∇f (xε ) + 2(xε − x) = λεi ∇gi (xε ) + µεj ∇hj (xε ) .
i=1 j=1

8
Pour pouvoir passer à la limite, on doit prouver que les λεi et µεj sont bornés ce qui
permettra d’extraire des sous-suites convergentes.
On remarque d’abord que, si hj (x) < 0 alors hj (xε ) < 0 pour ε assez petit et donc
µεj = 0. Donc, dans la somme en j, il suffit de ne prendre en compte que les termes
d’indices j1 , · · · , jk .
D’autre part, si les λεi et µεj ne sont pas bornés alors max |λεi |, |µεj | → +∞. On


i,j
considère le terme pour lequel le max est atteint : supposons, par exemple, que ce soit
pour |λε1 | le long d’une sous-suite, i.e.
|λε1 | = max |λεi |, |µεj | → +∞ .


i,j

λεi µεj
En divisant (3) par |λε1 |, on se retrouve avec des coefficients bornés ( et ) et, après
|λε1 | |λε1 |
extraction de sous-suites convergentes, le passage à la limite donne une égalité du type :
m
X l
X
0 = ∇g1 (x) + λi ∇gi (x) + µj ∇hj (x) .
i=2 j=1

Prenant en compte la remarque ci-dessus montrant que, dans la seconde somme, seuls
les termes d’indices j1 , · · · , jk apparaissent, cette égalité est une contradiction avec l’hy-
pothèse d’indépendance des vecteurs ∇g1 (x), ∇g2 (x), · · · , ∇gm (x), ∇hj1 (x), · · · , ∇hjk (x).
Donc les λεi et µεj sont bornés et en passant à la limite dans (3) après extractions de
sous-suites convergentes, on a la propriété souhaitée avec la propriété sur les µj découlant
de la remarque déjà utilisée au paragraphe précédent.

Remarque : Dans le théorème de Kuhn et Tucker, comme dans celui des fonctions impli-
cites qui donne le résultat pour les problèmes d’optimisation avec contraintes d’égalités,
on voit bien que f , ainsi que les fonctions donnant les contraintes, n’ont pas besoin d’être
C 1 partout mais simplement au voisinage du point de minimum local. Cette remarque
peut être utile pour traiter certains problèmes.

Exercice : De la capacité à raisonner comme un micro-économiste...

On reprend le problème d’optimisation associé au Théorème 3.3. On introduit le Lagra-
gien :
m
X l
X
L(y, λ, µ) := f (y) − λi gi (y) − µj hj (y) ,
i=1 j=1

où λ := (λi )i et µ := (µj )j . On suppose que f est convexe, coercive et de classe C 1 et que
les fonctions gi , hj sont affines. En utilisant L, montrer que, si x satisfait les conditions
d’optimalité du Théorème 3.3 pour un certain λ et µ alors x est un point de minimum
global de y 7→ L(y, λ, µ) sur Rn et x est un point de minimum global de f sur D.
Application : Résoudre les problèmes d’optimisation dans R3 avec :
1 2
f (x, y, z) := x + y 2 + 4z 2 + 4xy + 6xz − 8x − 4y − 7z ,
2

9
et avec les contraintes d’inégalités :
(i) 4x + 2y ≥ 6
ou bien :
(i) 4x + 2y ≤ 6
ou enfin avec la contrainte d’égalité :
(i) 4x + 2y = 8.

Sujets d’études : Quid en dimension infinie ?

1. “Revoir” les analogues des théorèmes de ce mini-cours dans le cas d’un espace de Hilbert
H. On pourra se contenter du cas où :
1
f (x) := (Ax, x) − (b, x) ,
2
où b ∈ H et A : H → H est un opérateur linéaire, continu et coercif, i.e.

(Ax, x) ≥ α||x||2 pour tout x ∈ H ,

où α > 0.
2. Réfléchir aux bonnes hypothèses pour résoudre (par pénalisation ?) les problèmes min f (x)
G(x)=0
ou min f (x) dans le cas où f est convexe, coercive.
G(x)≤0
Application : minimiser la fonctionnelle :
Z 1 Z 1
1 0 2
J(v) = [v (t)] dt − f (t)v(t) ,
2 0 0

dans H = H01 (]0, 1[) sous la contrainte :

Z 1
[v(t)]2 dt = 1 (ou ≤ 1) .
0

(Sur ce dernier problème, on fera le lien avec le théorème de projection.)

10