Introduction à l’optimisation, aspects théoriques et numériques

Yannick Privat

IRMA, univ. Strasbourg

Résumé no 6
Algorithmes pour l’optimisation SOUS contrainte(s)

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 1/8

Plan

1 Algorithme de pénalisation

2 La méthode du gradient projeté

3 L’algorithme d’Uzawa

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 2/8

 Algorithme de pénalisation

Sommaire

1 Algorithme de pénalisation

2 La méthode du gradient projeté

3 L’algorithme d’Uzawa

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 3/8

 Algorithme de pénalisation

Les méthodes de pénalisation

! Objectif : donner un exemple de méthode pour l’optimisation sous contraintes.
! Bien d’autres existent. Par exemple, l’agorithme du gradient projeté, d’Uzawa, etc.
! Le principe : on remplace le problème avec contraintes.

(P) inf J (x)

x∈C ⊂Rn

par un problème sans contrainte

1
(Pε ) infn J (x) + α (x) ,
x∈R ε
où α : Rn → R est une fonction de pénalisation des contraintes et ε > 0.
! Choix de la fonction α : le but est de trouver des fonctions α telles que les problèmes
(P) et (Pε ) soient équivalents, c’est-à-dire, tels qu’ils aient les mêmes solutions.

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 4/8

 Algorithme de pénalisation

Les méthodes de pénalisation

On compare les problèmes
Avec contraintes Sans contrainte
1
(P) inf J (x) (Pε ) infn J (x) + α (x)
x∈C ⊂Rn x∈R ε
Supposons que α vérifie les propriétés suivantes :
1 α est continue sur Rn (en pratique, α est C 1 )
n
2 ∀x ∈ R , α (x) > 0
3 α (x) = 0 ⇔ x ∈ C

Voici quelques exemples de fonction de pénalisation pour différentes contraintes :

2
Contrainte x 6 0 : la fonction α est α (x) = x + .
Contrainte h (x) = 0 : la fonction α est α (x) = kh (x)k2 .
2
contrainte g (x) 6 0 : la fonction α est α (x) = g (x)+ .
On note x + = max{x, 0} et on généralise cette notation à des vecteurs.

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 4/8

 Algorithme de pénalisation

Les méthodes de pénalisation

Initialisation
k = 1 : choisir x (0) ∈ Rn , ε(1) > 0
Iteration k : tant que le critere d’arret  n’est pas satisfait :
1
min J (x) + ε(k) α (x)
a) Resoudre le sous probleme (Pε(k) )
x ∈ Rn
avec x (k−1) le point d’initialisation.
b) k ← k + 1, prendre ε(k+1) < ε(k) .

Table – Algorithme de pénalisation extérieure

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 4/8

 Algorithme de pénalisation

Les méthodes de pénalisation

Théorème (convergence de la méthode de pénalisation)
Soit J une fonction continue et coercive. Soit C un ensemble fermé non vide. On suppose
que α vérifie les conditions suivantes :
1 α est continue sur Rn .
2 ∀x ∈ Rn , α (x) > 0.
3 α (x) = 0 ⇔ x ∈ C .
On a alors :
∀ε > 0, (Pε ) a au moins une solution xε
La famille (xε )ε>0 est bornée
Toute sous-suite convergente extraite de (xε )ε>0 converge vers une solution de (P)
lorsque ε → 0.

Exemple
Une formulation pénalisée du problème d’optimisation (P) inf x 4 + 6y 6 − 3x 2 + x − 7y
x≥0
1
4 6 2
est (Pε ) inf x + 6y − 3x + x − 7y + min{x, 0}2 . On peut vérifier que les
(x,y )∈R2 ε
hypothèses du théorème ci-dessus sont satisfaites.
Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 4/8
 La méthode du gradient projeté

Sommaire

1 Algorithme de pénalisation

2 La méthode du gradient projeté

3 L’algorithme d’Uzawa

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 5/8

 La méthode du gradient projeté

La méthode du gradient projeté

On cherche à résoudre numériquement le problème

inf J(x) avec J : Rn → R différentiable

x∈C

et C ⊂ Rn , un ensemble de contraintes.
X Dans le cas sans contrainte, l’algorithme du gradient est une méthode de descente
s’écrivant sous la forme générique.
 (0)
x ∈ Rn donné.
x (k+1) = x (k) + ρ(k) d(k) ,

où d(k) ∈ Rn \ {0} est la direction de descente, ρ(k) ∈ R+∗ est le pas à l’itération k.
Ces deux paramètres sont choisis de sorte que
   
J x (k+1) 6 J x (k) .

X Problème numérique : lorsque l’on minimise sur un ensemble de contraintes C , il

n’est pas sûr que x (k) reste dans C . Il est donc nécessaire de se ramener sur C .
On réalise cette dernière opération grâce à une projection sur C .

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 6/8

 La méthode du gradient projeté

La méthode du gradient projeté

On cherche à résoudre numériquement le problème

inf J(x) avec J : Rn → R différentiable

x∈C

et C ⊂ Rn , un ensemble de contraintes.
Rappels sur la notion de projection

Soit C , un convexe fermé d’un espace vectoriel H de

dimension finie (ou plus généralement, un espace de
Hilbert)
Soit x ∈ H. Il existe un unique élément de C noté
pC (x), appelé projection de x sur C qui résout le
problème
inf kx − y k.
y ∈C

pC (x) est caractérisé de façon unique par les

conditions :

pC (x) ∈ C et hx − pC (x), y − pC (x)i ≤ 0, ∀y ∈ C .

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 6/8

 La méthode du gradient projeté

La méthode du gradient projeté

On cherche à résoudre numériquement le problème

inf J(x) avec J : Rn → R différentiable

x∈C

et C ⊂ Rn , un ensemble de contraintes.

Exemples de projections

Exemple 1 : si C = {(x1 , ..., xn ) , ai ≤ xi ≤ bi , i ∈ {1, . . . n}}, alors pour

i ∈ {1, . . . , n},

i-ème composante de pC (x1 , . . . , xn ) = min{max{xi , ai }, bi }.

Exemple 2 : si C = {x ∈ Rn | x ∈ Bf (x0 , R)}, où Bf (x0 , R) est la boule euclidienne

fermée de centre x0 et rayon R, alors

x , si x ∈ C ;
pC (x) = x−x0 .
x0 + R kx−x 0k
, si x ∈/C

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 6/8

 La méthode du gradient projeté

La méthode du gradient projeté

On cherche à résoudre numériquement le problème

inf J(x) avec J : Rn → R différentiable

x∈C

et C ⊂ Rn , un ensemble de contraintes.

On suppose que C est un convexe fermé de Rn .

Algorithme du gradient projeté

1 Initialisation.
k = 0 : on choisit x 0 ∈ Rn et ρ0 ∈ R∗+ .
2 Itération k.
 
x k+1 = pC x k − ρk ∇J(x k ) .

pC désigne ici la projection sur C

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 6/8

 La méthode du gradient projeté

La méthode du gradient projeté

On cherche à résoudre numériquement le problème

inf J(x) avec J : Rn → R différentiable

x∈C

et C ⊂ Rn , un ensemble de contraintes.

Théorème (convergence de la méthode de gradient projeté)

On suppose que J est coercive, C 1 , de dérivée Lipschitzienne a , et qu’il existe α > 0 tel
que :
∀(x, y ) ∈ (Rn )2 , (∇J(x) − ∇J(y ), x − y ) ≥ αkx − y k2 .
Si l’on choisit le pas ρk dans un intervalle [β1 , β2 ] tel que 0 < β1 < β2 < 2α
M
, où α est
la constante de coercivité de J et M, la constante de Lipschitz de la dérivée de J, alors
la suite (x n )n≥0 d’itérés par la méthode du gradient projeté converge vers la solution du
problème de minimisation.
a. autrement dit qu’il existe M > 0 tel que
n 2
k∇J(x) − ∇J(y )k ≤ Mkx − y k ∀(x, y ) ∈ [R ] .

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 6/8

 La méthode du gradient projeté

La méthode du gradient projeté

On cherche à résoudre numériquement le problème

inf J(x) avec J : Rn → R différentiable

x∈C

et C ⊂ Rn , un ensemble de contraintes.

Un exemple numérique

On résout

inf 2x 2 + 3xy + 2y 2 ,
(x,y )∈Q

avec Q = x ≤ − 12 , y ≤ − 12 , à l’aide


d’une méthode de gradient projeté à

pas constant.
pas = 1e − 4. Le gradient converge
(erreur < 1e − 8) en 8 iterations.

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 6/8

 La méthode du gradient projeté

La méthode du gradient projeté

On cherche à résoudre numériquement le problème

inf J(x) avec J : Rn → R différentiable

x∈C

et C ⊂ Rn , un ensemble de contraintes.
Un exemple numérique

Suite des itérés (∗ sur le dessin)

obtenus par Matlab :
-0.6000 0.2000
-0.5998 -0.5000
-0.5994 -0.5000
-0.5989 -0.5000
-0.5985 -0.5000
-0.5980 -0.5000
-0.5974 -0.5000
-0.5000 -0.5000
-0.5000 -0.5000

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 6/8

 L’algorithme d’Uzawa

Sommaire

1 Algorithme de pénalisation

2 La méthode du gradient projeté

3 L’algorithme d’Uzawa

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 7/8

 L’algorithme d’Uzawa

L’algorithme d’Uzawa
On cherche à résoudre numériquement le problème
inf J(x) avec J : Rn → R différentiable
x∈C

et C = {x ∈ Rn | h(x) = 0 et g (x) ≤ 0}, l’ensemble de contraintes (avec h : Rn → Rp et

g : Rn → Rq ).

La technique proposée ici provient de la partie de l’optimisation appelée théorie de la dualité

convexe. L’idée générale est de considérer le Lagrangien L défini sur Rn × Rp × Rq par
p q
X X
L (x, λ, µ) = J (x) + λi hi (x) + µj gj (x) .
i=1 j=1

Pour mieux comprendre la théorie de la dualité, on introduit la notion de point-selle du

Lagrangien.

Définition : point-selle du Lagrangien

On appelle point-selle de L sur Rn × Rp × R+m tout triplet (x ∗ , λ∗ , µ∗ ) ∈ Rn × Rp × Rq+
vérifiant

∀ (x, λ, µ) ∈ Rn × Rp × Rq+ , L (x ∗ , λ, µ) 6 L (x ∗ , λ∗ , µ∗ ) 6 L (x, λ∗ , µ∗ )

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 8/8
 L’algorithme d’Uzawa

L’algorithme d’Uzawa
On cherche à résoudre numériquement le problème
inf J(x) avec J : Rn → R différentiable
x∈C

et C = {x ∈ Rn | h(x) = 0 et g (x) ≤ 0}, l’ensemble de contraintes (avec h : Rn → Rp et

g : Rn → Rq ).

Ce choix est motivé (au moins) par deux raisons :

La fonction Lagrangienne englobe à la fois la fonction J et les contraintes h et g .
une condition nécessaire du premier ordre pour que x ∗ soit un minimum de J avec
contraintes est que x ∗ (associé aux multiplicateurs de Lagrange) soit un point
critique de L.
On a alors le résultat suivant.

Théorème (Karush-Kuhn-Tucker)
Supposons que J, h et g soient de classe C 1 et que le triplet (x ∗ , λ∗ , µ∗ ) ∈ Rn ×Rp ×Rq+ soit
un point-selle de L sur Rn ×Rp ×Rq+ . Alors, ce triplet vérifie les conditions de Kuhn-Tucker.

Réciproque vraie sous certaines conditions (par exemple, si J est convexe).

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 8/8

 L’algorithme d’Uzawa

L’algorithme d’Uzawa
On cherche à résoudre numériquement le problème
inf J(x) avec J : Rn → R différentiable
x∈C

et C = {x ∈ Rn | h(x) = 0 et g (x) ≤ 0}, l’ensemble de contraintes (avec h : Rn → Rp et

g : Rn → Rq ).

Ce théorème indique que nous devons chercher un triplet (x ∗ , λ∗ , µ∗ ) ∈ Rn × Rp × Rq+

vérifiant les conditions de Kuhn-Tucker, autrement dit :
1 Pour (λ∗ , µ∗ ) fixés dans Rp × Rq+ , on résout le problème de minimisation sans
contrainte (sur tout Rn )
infn L (x, λ∗ , µ∗ )
x∈R

2 Pour x fixé dans R , on résout le problème de maximisation sur Rp × Rq+

∗ n

(c’est-à-dire avec des contraintes de bornes simples)

sup L (x ∗ , λ, µ)
q
(λ,µ)∈Rp ×R+

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 8/8

 L’algorithme d’Uzawa

L’algorithme d’Uzawa
On cherche à résoudre numériquement le problème
inf J(x) avec J : Rn → R différentiable
x∈C

et C = {x ∈ Rn | h(x) = 0 et g (x) ≤ 0}, l’ensemble de contraintes (avec h : Rn → Rp et

g : Rn → Rq ).

On se donne ρ > 0.

Initialisation : k = 0, choisir λ(0) ∈ Rp et µ(0) ∈ Rq+

Iteration. Tant que le critere d’arret n’est pas satisfait :
a) calculer
  x (k)∈ Rn solution
 de
P (k) inf x∈Rn L x, λ(k) , µ(k)
b) calculer λ(k+1) et µ(k+1)
  avec
 λ(k+1) = λ(k) + ρ hi x (k) , i = 1, ..., p
i i
  
 µ(k+1) = max 0, µ(k) + ρgj x (k) , j = 1, ...q
j j

Table – Algorithme d’Uzawa

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 8/8

 L’algorithme d’Uzawa

L’algorithme d’Uzawa
On cherche à résoudre numériquement le problème
inf J(x) avec J : Rn → R différentiable
x∈C

et C = {x ∈ Rn | h(x) = 0 et g (x) ≤ 0}, l’ensemble de contraintes (avec h : Rn → Rp et

g : Rn → Rq ).

Convergence de l’algorithme d’Uzawa

On suppose que J est C 1 et α-convexe a , que h est affine, g convexe de classe C 1 et que
h et g sont M-lipschitziennes.
On suppose de plus que le Lagrangien L possède un point-selle (x ∗ , λ∗ , µ∗ ) sur Rn × Rp ×
Rq+ .  
Alors, pour tout ρ ∈ 0, α/M 2 , la suite x (k)
 
générée par l’algorithme d’Uzawa
k∈N
converge vers x ∗ .
a. On rappelle que J est dite α-convexe s’il existe α > 0 tel que J − α
2k · k22 est convexe.

Y. Privat (univ. Strasbourg) Master 1 - Optimisation Résumé no 6 8/8