Optimisation differentiable sous contraintes

Khalfi Hamza
Problèmes de minimisation avec contraintes

Soit f : U −→ R une fonction numérique définie sur un ensemble de Rn .

Il s’agit de déterminer le point a ∈ U qui vérifie

f (a) = min f (x)

x∈U

En général U est définie par l’intersection d’une famille de contraintes de

la forme:
I g (x) ≤ 0,
I h(x) = 0,
I Bx ≤ c où B est une matrice et c un vecteur,
I Cx = d où C est une matrice et d un vecteur,
I lb ≤ x ≤ ub où les lb et ub sont des bornes sur la solution x,
i.e. lbi ≤ xi ≤ ubi ∀i
Problèmes avec contraintes (suite)

Le type de problème que nous allons considérer par la suite, s’écrira de

manière plus compact
min f (x)
g (x) ≤ 0
h(x) = 0
où g = (g1 , g2 , . . . , gm ) sont les contraintes d’inégalité (en incluant les
bornes sur x) et h = (h1 , h2 , . . . , hp ) les contraintes d’égalité. Cette
écriture inclut aussi les contraintes linéaires.

Remarques:
I U = {x | g (x) ≤ 0 et h(x) = 0} n’est pas convexe en général.
I Si les gi sont convexes et les hj linéaires, alors U est convexe.
Condition d’optimalité du premier ordre: cas convexe
Théorème: Condition nécessaire d’optimalité du premier ordre

Soit f : U −→ R une fonction numérique de classe C 1 définie sur un

ensemble convexe fermé U ⊂ Rn . Si a ∈ U est un point minimisant de f ,

f (a) = min f (x),

x∈U

alors
(∇f (a), x − a) ≥ 0 ∀x ∈ U
Preuve: a, x ∈ U =⇒ a + t(x − a) ∈ U car U est convexe pour
0 ≤ t ≤ 1. Par hypothèse, on a que

f (a + t(x − a)) − f (a) ≥ 0

f (a + t(x − a)) − f (a)
lim ≥ 0
t→0 t
(∇f (a), x − a)) ≥ 0
Condition d’optimalité (suite)

Remarques:

I Géométriquement parlant, la condition (∇f (a), x − a) ≥ 0

s’interprète en disant que l’angle θ entre le vecteur ∇f (a) et x − a
est dans l’intervalle
−π/2 ≤ θ ≤ π/2.
I Si U = Rn , on retrouve la condition d’optimalité sans contrainte:
∇f (a) = 0.
I Si le point minimisant a se trouve à l’intérieur de U, on a aussi
∇f (a) = 0.
En effet il suffit de prendre x = a ± r y pour r suffisamment petit et
y ∈ Rn quelconque. On introduit ce point dans la condition
d’optimalité (∇f (a), x − a) ≥ 0. Ceci implique

(∇f (a), ±y ) ≥ 0 =⇒ (∇f (a), y ) = 0 ∀y =⇒ ∇f (a) = 0.

Condition d’optimalité cas convexe (suite)

Théorème: Condition nécessaire et suffisante d’optimalité du premier

ordre

Soit f : U −→ R une fonction numérique convexe de classe C 1 définie

sur un ensemble convexe fermé U ⊂ Rn .
On a la caractérisation suivante:
a ∈ U est un point minimisant de f si et seulement si

(∇f (a), x − a) ≥ 0 ∀x ∈ U

Preuve: Il suffit de montrer ⇐=

Par le critère de convexité du premier ordre, on a

f (x) ≥ f (a) + (∇f (a), x − a) ∀x ∈ U.

Mais (∇f (a), x − a) ≥ 0. On obtient

f (x) ≥ f (a) + (∇f (a), x − a) ≥ f (a) ∀x ∈ U.

Choix particuliers de U

I U est un sous-espace linéaire de Rn . Dans ce cas, la condition

d’optimalité s’écrit sous la forme

(∇f (a), y ) = 0 ∀y ∈ U.

C’est-à-dire que ∇f (a) ∈ U ⊥ .

I U est un sous-espace affine de Rn , i.e. U = x0 + W avec W un
sous-espace linéaire. La condition d’optimalité s’écrit sous la forme

(∇f (a), w ) = 0 ∀w ∈ W .

ou ∇f (a) ∈ W ⊥ ou encore

(∇f (a), x − a) = 0 ∀x ∈ U.
Exemple
Considérons le problème de calculer la projection du point (2, 2) sur un
polygone convexe. Le problème s’écrit sous la forme
min (x1 − 2)2 + (x2 − 2)2
x1 + 2x2 ≤ 3
x1 ≥ 0, x2 ≥ 0

Ce problème admet une solution unique.

Selon le dessin, le gradient doit être dans
la direction du vecteur normal à la
droite x1 + 2x2 = 3.

(x1 − 2, x2 − 2) = t(−1, −2)

pour t ≥ 0. On trouve
t = 3/5 =⇒ x1 = 7/5, x2 = 4/5.
Lagrangien et point de selle

Soient A ⊂ Rn et B ⊂ Rm deux ensembles non vide et

L:A×B →R

une fonction appellée lagrangien.

Définition: Un point (x̄, ȳ ) ∈ A × B est un point de selle du lagrangien

L si
L(x̄, y ) ≤ L(x̄, ȳ ) ≤ L(x, ȳ ) ∀x ∈ A, ∀y ∈ B.

Exemple: Le point (0, 0) est un point de selle de la fonction

L(x, y ) = x 2 − y 2 avec A = B = R car

L(0, y ) = −y 2 ≤ 0 = L(0, 0) ≤ x 2 = L(x, 0) ∀x, y ∈ R.

Théorème du min-max
Théorème: Si (x̄, ȳ ) est un point de selle de L, alors
max min L(x, y ) = min max L(x, y ) = L(x̄, ȳ )
y ∈B x∈A x∈A y ∈B

Autrement dit, on peut inverser l’ordre du min et du max.

Démonstration: Montrons en premier que
max min L(x, y ) ≤ min max L(x, y ).
y ∈B x∈A x∈A y ∈B

En effet, on a que
min L(x, y ) ≤ L(x, y ) ≤ max L(x, y )
x∈A y ∈B

Le membre de gauche est une fonction de y seulement. De même, pour

le membre de droite qui est une fonction de x uniquement. Ceci implique
max min L(x, y ) ≤ max L(x, y ), ∀x ∈ A
y ∈B x∈A y ∈B

et, en prenant le minimum par rapport à x,

max min L(x, y ) ≤ min max L(x, y ),
y ∈B x∈A x∈A y ∈B

d’où le résultat.
Condition d’optimalité du lagrangien
Soient U, V ⊂ Rn deux sous-ensembles convexes et fermés. On fera les
hypothèses suivantes:
I Pour y fixé, la fonction L : x → L(x, y ) est convexe.
I Pour x fixé, la fonction L : y → L(x, y ) est concave (−L est
convexe).
Au point-selle (x̄, ȳ ) du lagrangien L, la condition d’optimalité du
minimum L(x̄, ȳ ) ≤ L(x, ȳ ) ∀x ∈ U s’écrit

∂L
( (x̄, ȳ ), x − x̄) ≥ 0 ∀x ∈ U
∂x

De même, la condition d’optimalité du maximum

L(x̄, y ) ≤ L(x̄, ȳ ) ∀y ∈ V s’écrit

∂L
( (x̄, ȳ ), y − ȳ ) ≤ 0 ∀y ∈ V
∂y
∂L
où ∂x est le gradient de la fonction L(x, y ) pour y fixé.
Fonction indicatrice

Soit K ⊂ Rn un sous-ensemble quelconque et non vide.

Definition: La fonction indicatrice de l’ensemble K est définie par

0 si x ∈ K ,
IK (x) =
∞ sinon.

La fonction indicatrice sert à enlever les contraintes. Pour un problème

de minimisation, on a évidemment la relation

min f (x) = min f (x) + IK (x)

x∈K x

Pour un problème de maximisation, on a plutôt

max f (x) = max f (x) − IK (x)

x∈K x
Contraintes de la forme: Bx = c
Appliquons la dualité lagrangienne au problème (primal)

min f (x)
Bx=c

où B est une matrice de format m × n et c ∈ Rm . Ce problème a un sens

seulement si c ∈ Im B ou encore que le rang de B est maximal
(Im B = Rm ).

Lemme: La fonction indicatrice de K = {x ∈ Rn | Bx = c} est donnée

par
IK (x) = maxm (λ, Bx − c)
λ∈R

Démonstration: en effet, si Bx 6= c, on peut prendre

λ = r (Bx − c) =⇒ (λ, Bx − c) = r kBx − ck2 → ∞ si r → ∞

Le maximum sera ∞.
Au contraire, si Bx = c, on a que (λ, Bx − c) = 0 ∀λ ∈ Rm de
maximum 0.
Contraintes de la forme: Bx = c (suite)
Par conséquent, on peut écrire

min f (x) = min f (x) + IK (x) = min f (x) + maxm (λ, Bx − c)

Bx=c x x λ∈R

Ceci suggère la fonction lagrangienne

L(x, λ) = f (x) + (λ, Bx − c) ∀x ∈ Rn , ∀λ ∈ Rm .

ce qui transforme le problème primal en un problème de point-selle

min f (x) = minn maxm L(x, λ)

Bx=c x∈R λ∈R

La condition d’optimalité du lagrangien sera

∂L


 = 0 ⇐⇒ ∇f (x) + B t λ = 0
∂x
 ∂L = 0 ⇐⇒ Bx = c

∂λ
Point de vue des cônes duaux: Bx = c

La condition d’optimalité du problème f (a) = min f (x) s’écrit

Bx=c

(∇f (a), x − a) ≥ 0 ∀x ∈ U = {x | Bx = c}.

Sachant que c ∈ Im B, on a que U = x0 + Ker B où Bx0 = c. Ce qui

implique que U est un sous-espace affine et dans ce cas, la condition
d’optimalité correspond à

∇f (a) ∈ (Ker B)⊥ = Im B t =⇒ ∃λ ∈ Rm ∇f (a) = −B t λ.

Ceci fournit les conditions en disant que a et λ sont solutions du système

∇f (x) + B t λ = 0,

Bx = c.

Ce sont les mêmes conditions que celles obtenues par la méthode de

Lagrange.
Contraintes de la forme: Bx ≤ c

Appliquons la dualité lagrangienne au problème (primal)

min f (x)
Bx≤c

où B est une matrice de format m × n et c ∈ Rm .

Lemme: La fonction indicatrice de K = {x ∈ Rn | Bx ≤ c} est donnée

par
IK (x) = max(λ, Bx − c)
λ≥0

Démonstration: en effet, si Bx > c, on peut prendre

λ = r (Bx − c) ≥ 0 =⇒ (λ, Bx − c) = r kBx − ck2 → ∞ si r → ∞.

Le maximum sera ∞.
Au contraire, si Bx ≤ c, on a que (λ, Bx − c) ≤ 0 ∀λ ≥ 0
car Bx − c ≤ 0. Donc le maximum sera 0.
Contraintes de la forme: Bx ≤ c (suite)

Par conséquent, on peut écrire

min f (x) = min f (x) + IK (x) = min f (x) + max(λ, Bx − c)

Bx≤c x x λ≥0

Ceci suggère la fonction lagrangienne

L(x, λ) = f (x) + (λ, Bx − c) ∀x ∈ Rn , ∀λ ≥ 0 et λ ∈ Rm .

ce qui transforme le problème primal en un problème de point-selle

min f (x) = minn max L(x, λ)

Bx≤c x∈R λ≥0
Contraintes de la forme: Bx ≤ c (suite)

La condition d’optimalité du lagrangien sera

∂L
I ( , x − x̄) ≥ 0 ∀x ∈ Rn ce qui donne
∂x
∂L
= 0 ⇐⇒ ∇f (x̄) + B t λ = 0
∂x
∂L
I ( , λ − λ̄) ≤ 0 ∀λ ≥ 0 . Etant donné que {λ ≥ 0} forme un cône
∂λ
convexe, on obtient les conditions suivantes
∂L
( , λ) = (B x̄ − c, λ) ≤ 0 ∀λ ≥ 0 =⇒ B x̄ − c ≤ 0 ⇐⇒ B x̄ ≤ c
∂λ
∂L
( , λ̄) = 0 ⇐⇒ (B x̄ − c, λ̄) = 0
∂λ
Conditions KKT pour les contraintes: Bx ≤ c

A partir des conditions d’optimalité du lagrangien L(x, λ), on peut écrire

les conditions dites de Karush-Kuhn-Tucker (KKT) pour le problème

min f (x)
Bx≤c

Observons que (B x̄ − c, λ̄) = 0 avec λ̄ ≥ 0 signifie que λ̄i (B x̄ − c)i = 0

pour tous les i = 1, . . . , m.

Les conditions KKT s’écrivent sous la forme:



 ∇f (x) + B t λ = 0,


λi ≥ 0, ∀i = 1, . . . , m,




 (Bx)i ≤ ci , ∀i = 1, . . . , m,


λi (Bx − c)i , = 0 ∀i = 1, . . . , m.

Cas général: contraintes g (x) = 0
Appliquons la méthode de Lagrange au problème
min f (x)
g (x)=0

où g = (g1 , g2 , . . . , gm ) désigne m contraintes scalaires. En général,

l’ensemble des contraintes n’est pas convexe.

On prend la fonction lagrangienne

m
X
L(x, λ) = f (x) + (λ, g (x)) = f (x) + λi gi (x) ∀x ∈ Rn , ∀λ ∈ Rm .
i=1

Ceci transforme le problème primal en un problème de point-selle

min f (x) = minn maxm L(x, λ)
g (x)=0 x∈R λ∈R

La condition d’optimalité du lagrangien sera

 m
∂L X
= 0 ⇐⇒ ∇f (x) + λi ∇gi (x) = 0,



∂x
i=1
 ∂L = 0 ⇐⇒ gi (x) = 0,

∀i = 1, . . . , m.

∂λ
Contraintes d’égalité (suite)

En résumé, le point optimal a ∈ U doit vérifier le système non linéaire:

m

 f (x) + X λ ∇g (x) = 0,

i i
 i=1
gi (x) = 0, ∀i = 1, . . . , m.


qui correspond à la condition d’optimalité du lagrangien

m
X
L(x, λ) = f (x) + (λ, g (x)) = f (x) + λi gi (x) ∀x ∈ Rn , ∀λ ∈ Rm .
i=1
Contraintes de la forme: g (x) ≤ 0
Appliquons la dualité lagrangienne au problème (primal)

min f (x)
g (x)≤0

où g (x) = (g1 (x), g2 (x), . . . , gm (x)).

Lemme: La fonction indicatrice de K = {x ∈ Rn | g (x) ≤ 0} est donnée

par
IK (x) = max(λ, g (x))
λ≥0

Démonstration: en effet, si gi (x) > 0, on peut prendre λ = 0 sauf pour

la composante i

λi = r (gi (x)) > 0 =⇒ (λ, g (x)) = r gi (x)2 → ∞ si r → ∞.

Le maximum sera ∞.
Au contraire, si g (x) ≤ 0, on a que (λ, g (x)) ≤ 0 ∀λ ≥ 0
car g (x) ≤ 0. Donc le maximum sera 0.
Contraintes de la forme: g (x) ≤ 0 (suite)

Par conséquent, on peut écrire

min f (x) = min f (x) + IK (x) = min f (x) + max(λ, g (x))

g (x)≤0 x x λ≥0

Ceci suggère la fonction lagrangienne

Xm
L(x, λ) = f (x)+(λ, g (x)) = f (x)+ λi gi (x) ∀x ∈ Rn , ∀λ ≥ 0 et λ ∈ Rm .
i=1

ce qui transforme le problème primal en un problème de point-selle

min f (x) = minn max L(x, λ)

g (x)≤0 x∈R λ≥0
Contraintes de la forme: g (x) ≤ 0 (suite)

La condition d’optimalité du lagrangien sera

∂L
I ( , x − x̄) ≥ 0 ∀x ∈ Rn ce qui donne
∂x
m
∂L X
= 0 ⇐⇒ ∇f (x̄) + λi ∇gi (x̄) = 0
∂x
i=1

∂L
I ( , λ − λ̄) ≤ 0 ∀λ ≥ 0 . Etant donné que {λ ≥ 0} forme un cône
∂λ
convexe, on obtient les conditions suivantes
∂L
( , λ) = (g (x̄), λ) ≤ 0 ∀λ ≥ 0 =⇒ g (x̄) ≤ 0
∂λ
∂L
( , λ̄) = 0 ⇐⇒ (g (x̄), λ̄) = 0
∂λ
Conditions KKT pour les contraintes: g (x) ≤ 0
A partir des conditions d’optimalité du lagrangien L(x, λ), on peut écrire
les conditions dites de Karush-Kuhn-Tucker (KKT) pour le problème

min f (x)
g (x)≤0

Observons que (g (x̄), λ̄) = 0 avec λ̄ ≥ 0 signifie que λ̄i gi (x̄) = 0 pour
tous les i = 1, . . . , m.

Les conditions KKT s’écrivent sous la forme:

m

 X



 ∇f (x) + λi ∇gi (x) = 0,

 i=1

λi ≥ 0, ∀i = 1, . . . , m,

gi (x) ≤ 0, ∀i = 1, . . . , m,






λi gi (x) = 0 ∀i = 1, . . . , m.

Méthodes numériques: contraintes d’égalité

Considérons le problème de minimisation ayant seulement des contraintes

d’égalité
min f (x)
g (x)=0

où g = (g1 , g2 , . . . , gm ) désigne m contraintes scalaires.

En gros, il y a deux classes de méthodes numériques pour ce type de

problème.
I Approche couplée: basée sur la méthode des multiplicateurs de
Lagrange, résolution en (x, λ).
I Approche découplée: basée sur la théorie de la dualité, résolution en
x seulement.
Méthodes numériques: contraintes d’égalité
L’idée consiste à résoudre directemment le système d’équations obtenu
par la méthode des multiplicateurs de Lagrange. Si on introduit la
fonction lagrangienne
m
X
L(x, λ) = f (x) + (λ, g (x)) = f (x) + λi gi (x) ∀x ∈ Rn , ∀λ ∈ Rm .
i=1

la condition d’optimalité du problème min f (x) s’écrit

g (x)=0

( Pm
∇f (x) + i=1 λi ∇gi (x) = 0,
gi (x) = 0, ∀i = 1, . . . , m.

Ces équations forment un système de n + m équations par rapport aux

n + m variables x et λ.
Notons ce système par F (x, λ) = (Fx (x, λ), Fλ (x, λ)) = (0, 0) où
Pm
Fx (x, λ) = ∇f (x) + i=1 λi ∇gi (x),
Fλ (x, λ) = g (x) = (g1 (x), g2 (x), . . . , gm (x))t .
Méthodes numériques: contraintes d’égalité (suite)
Le système 
Fx (x, λ) = 0
F (x, λ) = 0 ⇐⇒
Fλ (x, λ) = 0
sera résolu par l’algorithme de Newton
1. Résoudre: DF (Xk ) ∆X = −F (Xk ),
2. Xk+1 = Xk + ∆X ,
où X = (x, λ) et DF (X ) est la matrice tangente (jacobienne) au point X
du système.
Calculons la matrice tangente qui a la forme d’une matrice 2 × 2 par blocs
∂Fx ∂Fx
 

DF (X ) =  ∂x ∂λ 

∂Fλ ∂Fλ 
∂x ∂λ
On a les formules
m
∂Fx X
I = Hf + λi Hgi ,
∂x
i=1
∂Fλ
I = Dg où Dg est la matrice jacobienne m × n de l’application g ,
∂x
∂Fx ∂Fλ
I = Dg t et = 0.
Méthode de pénalisation

En utilisant la fonction indicatrice de l’ensemble U = {g (x) = 0}, nous

pouvons enlever les contraintes d’égalité

min f (x) = min f (x) + IU (x)

g (x)=0 x

Le principe de la méthode de pénalisation consiste à approcher la

fonction indicatrice par une fonction plus régulière IU (x) ≈ r Ψr (x) où r
est un paramètre qui tend vers ∞. La fonction Ψr (x) vérifie les propriétés

1. Ψr (x) ≥ 0 ∀x ∈ Rn ∀r > 0,
2. Ψr (x) = 0 ⇐⇒ x ∈U ∀r > 0,
3. lim Ψr (x) = 0 ⇐⇒ x∈
/ U.
r →∞
Méthode de pénalisation (suite)

Pour les contraintes d’égalité, la fonction Ψr (x) la plus utilisée est

r
Ψr (x) = kg (x)k2
2

Par conséquent, le problème pénalisé s’écrit

r
minn f˜r (x) = minn f (x) + ||g (x)||2
x∈R x∈R 2
où r > 0 est un paramètre réel, en général grand, fixé d’avance.

On calcule le point minimum grâce à la condition d’optimalité

∇f˜r (x) = 0.