Lagrangien augmenté

classique
Considérons le problème de programmation mathématique suivant:
( P) Min f ( x )
Sujet à x ∈ X 1 ⊂ R n
x ∈ X 2 ⊂ Rn
x ∈ X ⊂ Rn
où f : R n → R1.
Supposons que X 1 et X 2 sont engendrés respectivement comme suit:
X 1 = { x ∈ R n : fi ( x ) ≤ 0, i = 1,… , m}
X 2 = { x ∈ R n : gi ( x ) ≤ 0, i = 1,… , q} .

Pour µ ≥ 0, définissons le problème suivant

q
( PEu ) Min f ( x ) + 1 µ pi ( x )
2 ∑ i =1
Sujet à x ∈ X 1 ⊂ R n

x ∈ X 2 ⊂ Rn
x ∈ X ⊂ Rn
2
où pi ( x ) = Max {0, gi ( x )} , i = 1,… , q.
Considérons le problème de programmation mathématique suivant:
( P) Min f ( x )
Sujet à x ∈ X 1 ⊂ R n
x ∈ X 2 ⊂ Rn
x ∈ X ⊂ Rn
où f : R n → R1.
Pour µ ≥ 0, définissons le problème suivant
q
( PEµ ) Min f ( x ) + 1 2 µ ∑i =1 pi ( x )
Sujet à x ∈ X 1 ⊂ R n
x ∈ X 2 ⊂ Rn
x ∈ X ⊂ Rn
2
où pi ( x ) = Max {0, gi ( x )} , i = 1,… , q.

Les problèmes ( P ) et ( PEµ ) pour µ ≥ 0 sont évidemment

équivalent puisqu'ils possèdent les mêmes solutions optimales.
Pour µ ≥ 0, définissons le problème suivant
q
1
( PEµ ) Min f ( x ) + 2 µ ∑i =1 pi ( x )
Sujet à x ∈ X 1 ⊂ R n
x ∈ X 2 ⊂ Rn
x ∈ X ⊂ Rn
2
où pi ( x ) = Max {0, gi ( x )} , i = 1,… , q.
Appliquons la relaxation lagrangienne au problème ( PEµ ) :
q q
( PE ) Gµ ( λ ) = Min f ( x ) + 1 µ ∑ pi ( x ) + ∑ λi gi ( x )
µλ 2 i =1 i =1

Sujet à f i ( x ) ≤ 0 i = 1,… , m
x∈ X.
 q

( P) Min f ( x ) ( PE ) Min f ( x ) + 1 µ ∑ pi ( x )
µ 2 i =1
Sujet à x ∈ X 1 ⊂ R n Sujet à x ∈ X 1 ⊂ R n
x ∈ X 2 ⊂ Rn x ∈ X 2 ⊂ Rn
x ∈ X ⊂ Rn x ∈ X ⊂ Rn

q q
( PE ) Gµ ( λ ) = Min f ( x ) + 1 µ ∑ pi ( x ) + ∑ λi gi ( x )
µλ 2 i =1 i =1 ( DE )
µ Max {Gµ ( λ )}
λ ≥0

Sujet à fi ( x ) ≤ 0 i = 1,… , m
x∈ X.

La fonction
q q q q
f ( x ) + 1 µ ∑ pi ( x ) + ∑ λi gi ( x ) = f ( x ) + ∑ λi gi ( x ) + 1 µ ∑ pi ( x )
2 i =1 i =1 i =1 2 i =1

qui est le lagrangien du problème ( PEµ ) est défini comme le

lagrangien augmenté (du factuer pénalité) de ( P ) .
 q q
f ( x ) + 1 µ ∑ pi ( x ) + ∑ λi gi ( x )
2 i =1 i =1

Notons que si λ = 0, alors

q
( PE ) Min f ( x ) + 1 µ ∑ pi ( x )
µ0 2 i =1
Sujet à f i ( x ) ≤ 0 i = 1,… , m
x∈ X

correspond au problème utilisé pour résoudre ( P ) avec la méthode

des pénalités.
Dans cette méthode, ( PEµ 0 ) est résolu pour une suite {µk }
(
divergente de valeurs croissantes i.e., µk +1 > µk et µk → ∞ .
k →∞
)
La suite des solutions correspondantes { x k } des problèmes PEµk 0 ( )
a la propriété que tout point limite x* de cette suite est une solution
optimale de ( P ) .
 q q
f ( x ) + 1 µ ∑ pi ( x ) + ∑ λi gi ( x )
2 i =1 i =1

D'autre part, si µ = 0, alors ( PE0 λ ) n'est rien d'autre que la

relaxation lagrangienne ( Pλ ) de ( P ) .
Ainsi, les méthodes utilisées pour résoudre la suite des problèmes
( PEµλ ) sont souvent les mêmes que celles utilisées pour la relaxation
lagrangienne où la valeur de µ est augmentée périodiquement
pour accélérer la convergence vers une solution optimale du
dual ( DEµ ) .
Dans son livre, Bertsekas analyse diverses méthodes de
résolution et leur convergence.
Référence.

D.M. Bertsekas, "Nonlinear Programming", Athena Scientific,

Massachusetts (1995 ) .
Lagrangien augmenté
avec linéarisation
Robinson présente une forme de la relaxation lagrangienne où
les contraintes sont linéarisées dans le problème et où la
déviation entre la contrainte et sa linéarisation est pénalisée
dans la fonction économique.

Murtagh et Saunders ont modifé cette approche en ajoutant une

pénalité pour en faire une variante du lagrangien augmenté sur
laquelle repose leur logiciel MINOS/AUGMENTED.
Considérons le problème suivant:

( P) Min f ( x )
Sujet à fi ( x ) ≤ 0 i = 1,… , m
hi ( x ) = 0 i = 1,… , q
x ∈ X ⊆ Rn

où la fonctions f , fi , hi sont de classe C 1 .

 ( P) Min f ( x )
Sujet à f i ( x ) ≤ 0 i = 1,… , m
hi ( x ) = 0 i = 1,… , q
x∈ X
À l'itération ( k + 1) de la procédure de résolution, étant donné
une solution x k et des multiplicateurs µ k et ν k obtenus à
l'itération précédente k , nous considérons le problème Pxk , µ k ,ν k ( )
m q
Min f ( x ) +∑ µ  f i ( x ) − Lf i ( x , x )  + ∑ν ik  hi ( x ) − Lhi ( x k , x ) 
i
k k

i =1 i =1
Sujet à Lfi ( x , x ) ≤ 0 i = 1,… , m
k

Lhi ( x k , x ) = 0 i = 1,… , q
x∈ X
où
k T
Lfi ( x , x ) = fi ( x ) + ∇f i ( x ) ( x − x k ) i = 1,… , m
k k

k T
Lhi ( x , x ) = hi ( x ) + ∇hi ( x ) ( x − x k ) i = 1,… , q
k k
 m q
Min f ( x ) +∑ µ  f i ( x ) − Lf i ( x , x )  +∑ν ik  hi ( x ) − Lhi ( x k , x ) 
i
k k

i =1 i =1
Sujet à Lf i ( x , x ) ≤ 0 i = 1,… , m
k

Lhi ( x k , x ) = 0 i = 1,… , q
x∈ X
où
k T
Lfi ( x , x ) = fi ( x ) + ∇f i ( x ) ( x − x k ) i = 1,… , m
k k

k T
Lhi ( x , x ) = hi ( x ) + ∇hi ( x ) ( x − x k ) i = 1,… , q
k k

Lf i ( x k , x )
fi ( x )

xk
La procédure suivante permet d'identifier un point satisfaisant
les conditions d'optimalité KKT pour le problème ( P ) .
Initialisation. Soit x 0 ∈ X , µ 0 ∈ R m , µ 0 ≥ 0, et ν 0 ∈ R q .
Poser k = 0.
Étape 1. Étant donné le triplet ( x k , µ k ,ν k ) , déterminer un point
satisfaisant les conditions KKT pour le problème Pxk , µ k ,ν k ( )
m q
Min f ( x ) +∑ µ  f i ( x ) − Lf i ( x , x )  +∑ν ik  hi ( x ) − Lhi ( x k , x ) 
i
k k

i =1 i =1
Sujet à Lf i ( x , x ) ≤ 0 i = 1,… , m
k

Lhi ( x k , x ) = 0 i = 1,… , q
x∈ X
où
k T
Lfi ( x , x ) = fi ( x ) + ∇f i ( x ) ( x − x k ) i = 1,… , m
k k

k T
Lhi ( x , x ) = hi ( x ) + ∇hi ( x ) ( x − x k ) i = 1,… , q
k k
Étape 1. Étant donné le triplet ( x k , µ k ,ν k ) , déterminer un point
satisfaisant les conditions KKT pour le problème Pxk , µ k ,ν k ( )
m q
Min f ( x ) + ∑ µ  fi ( x ) − Lfi ( x , x )  + ∑ν ik  hi ( x ) − Lhi ( x k , x ) 
i
k k

i =1 i =1
Sujet à Lf i ( x , x ) ≤ 0 i = 1,… , m
k

Lhi ( x k , x ) = 0 i = 1,… , q
x∈ X
où
k T
Lfi ( x , x ) = fi ( x ) + ∇fi ( x ) ( x − x k ) i = 1,… , m
k k

k T
Lhi ( x , x ) = hi ( x ) + ∇hi ( x ) ( x − x k ) i = 1,… , q
k k

Soit ( x k +1 , µ k +1 ,ν k +1 ) le triplet ainsi obtenu. Dans le cas où plus

d'un point de KKT existent, alors nous retenons celui le plus
proche de ( x k , µ k ,ν k ) .
Etape 2. Si le triplet ( x k +1 , µ k +1 ,ν k +1 ) satisfait le critère d'arrêt
assurant la convergence, alors terminer la procédure.
Autrement, poser k = ( k + 1) et reprendre l'étape 1.
 m q
Min f ( x ) +∑ µi  f i ( x ) − Lf i ( x , x )  + ∑ν i  hi ( x ) − Lhi ( x , x ) 
(P) Min f ( x ) i =1
Sujet à Lf i ( x , x ) ≤ 0 i = 1,… , m
i =1

Sujet à f i ( x ) ≤ 0 i = 1,… , m
Lhi ( x , x ) = 0 i = 1,… , q
hi ( x ) = 0 i = 1,… , q x∈ X
x∈ X où
T
Lf i ( x , x ) = f i ( x ) + ∇f i ( x ) ( x − x ) i = 1,… , m
T
Lhi ( x , x ) = hi ( x ) + ∇hi ( x ) ( x − x ) i = 1,… , q

Théorème 1. Soient f , f i , hi ∈ C 1. Alors les énoncés suivants

sont équivalents.
i ) Il existe un µ ∈ R m , µ ≥ 0, et un ν ∈ R q tel que ( x , µ ,ν )
satisfait les conditions KKT pour ( Px , µ ,ν ) .
ii ) Le triplet ( x , µ ,ν ) satisfait les conditions KKT pour ( P ) .
iii ) Pour tout µ ∈ R m , µ ≥ 0, et ν ∈ R q , ( x , µ ,ν ) satisfait les
conditions KKT pour ( Px , µ ,ν ) .
Preuve. Ces équivalences découlent directement des conditions
KKT pour les problèmes ( Px , µ ,ν ) et ( P ) .
Il est trivial que iii ) implique i ).
 m q
Min f ( x ) +∑ µi  f i ( x ) − Lf i ( x , x )  + ∑ν i  hi ( x ) − Lhi ( x , x ) 
i =1 i =1
(P) Min f ( x ) Sujet à Lf i ( x , x ) ≤ 0 i = 1,… , m
Sujet à f i ( x ) ≤ 0 i = 1,… , m Lhi ( x , x ) = 0 i = 1,… , q
hi ( x ) = 0 i = 1,… , q x∈ X
x∈ X où
T
Lf i ( x , x ) = f i ( x ) + ∇f i ( x ) ( x − x ) i = 1,… , m
T
Lhi ( x , x ) = hi ( x ) + ∇hi ( x ) ( x − x ) i = 1,… , q
Conditions KKT pour ( Px , µ ,ν ) :
Il existe xɶ ∈ R n , µɶ ∈ R m , µɶ ≥ 0,νɶ ∈ R q tels que
m q
∇f ( xɶ ) + ∑ µi ∇fi ( xɶ ) − ∇fi ( x )  + ∑ν i ∇hi ( xɶ ) − ∇hi ( x ) 
i =1 i =1
m q
+ ∑ µɶ i ∇f i ( x ) + ∑νɶi ∇hi ( x ) = 0
i =1 i =1

µɶ i Lfi ( x , xɶ ) = µɶ i  fi ( x ) + ∇fi ( x ) ( xɶ − x ) = 0

T
i = 1,… , m.

Conditions KKT pour ( P ) :

Il existe xˆ ∈ R n , µˆ ∈ R m , µˆ ≥ 0,νˆ ∈ R q tels que
m q
∇f ( xˆ ) + ∑ µˆ i ∇fi ( xˆ ) + ∑νˆi ∇hi ( xˆ ) = 0
i =1 i =1

µˆ i f i ( xˆ ) = 0 i = 1,… , m.
Conditions KKT pour ( Px µν ) : Théorème 1. Soient f , f i , hi ∈ C1 . Alors les énoncés suivants
Il existe xɶ ∈ R n , µɶ ∈ R m , µɶ ≥ 0,νɶ ∈ R q tels que sont équivalents.
i ) Il existe un µ ∈ R m , µ ≥ 0, et un ν ∈ R q tel que ( x , µ ,ν )
m q satisfait les conditions KKT pour ( Px , µ ,ν ) .
∇f ( x ) + ∑ µi ∇f i ( x ) − ∇f i ( x )  + ∑ν i ∇hi ( xɶ ) − ∇hi ( x ) 
ɶ ɶ ii) Le triplet ( x , µ ,ν ) satisfait les conditions KKT pour ( P ) .
i =1 i =1 iii ) Pour tout µ ∈ R m , µ ≥ 0, et ν ∈ R q , ( x , µ ,ν ) satisfait les
m q conditions KKT pour ( Px , µ ,ν ) .
+ ∑ µɶ i ∇f i ( x ) + ∑νɶi ∇hi ( x ) = 0
i =1 i =1

µɶ i Lf i ( x , xɶ ) = µɶ i  f i ( x ) + ∇f i ( x ) ( xɶ − x )  = 0
T
i = 1,… , m.

i ) ⇒ ii ) Si ( x , µ ,ν ) satisfait les conditions KKT pour ( P µ ν ) : x, ,

m q
∇f ( x ) + ∑ µi ∇f i ( x ) − ∇f i ( x )  + ∑ν i ∇hi ( x ) − ∇hi ( x ) 
i =1 i =1
m q
+ ∑ µi ∇f i ( x ) + ∑ν i ∇hi ( x ) = 0
i =1 i =1

µi Lf i ( x , x ) = µi  f i ( x ) + ∇f i ( x ) ( x − x )  = 0
 T
i = 1,… , m.

Par conséquent, ( x , µ ,ν ) Conditions KKT pour ( P ) :

satisfait les conditions Il existe xˆ ∈ R n , µˆ ∈ R m , µˆ ≥ 0,νˆ ∈ R q tels que
q
KKT pour ( P ) .
m
∇f ( xˆ ) + ∑ µˆ i ∇f i ( xˆ ) + ∑νˆi ∇hi ( xˆ ) = 0
i =1 i =1

µˆ i fi ( xˆ ) = 0 i = 1,… , m.
Conditions KKT pour ( P ) :
Théorème 1. Soient f , f i , hi ∈ C1 . Alors les énoncés suivants
Il existe xˆ ∈ R n , µˆ ∈ R m , µˆ ≥ 0,νˆ ∈ R q tels que sont équivalents.
i ) Il existe un µ ∈ R m , µ ≥ 0, et un ν ∈ R q tel que ( x , µ ,ν )
m q
∇f ( x ) + ∑ µi ∇f i ( x ) + ∑νˆi ∇hi ( xˆ ) = 0
ˆ ˆ ˆ satisfait les conditions KKT pour ( Px , µ ,ν ) .
ii ) Le triplet ( x , µ ,ν ) satisfait les conditions KKT pour ( P ) .
i =1 i =1
iii ) Pour tout µ ∈ R m , µ ≥ 0, et ν ∈ R q , ( x , µ ,ν ) satisfait les
µˆ i fi ( xˆ ) = 0 i = 1,… , m. conditions KKT pour ( Px , µ ,ν ) .

ii ) ⇒ iii ) Si ( x , µ ,ν ) satisfait les conditions KKT pour ( P ) :

m q
∇f ( x ) + ∑ µi ∇fi ( x ) − ∇fi ( x )  + ∑ν i ∇hi ( x ) − ∇hi ( x ) 
i =1 i =1
m q
+ ∑ µi ∇fi ( x ) + ∑ν i ∇hi ( x ) = 0
i =1 i =1

µi Lf i ( x , x ) = µi  f i ( x ) + ∇f i ( x ) ( x − x )  = 0
 T
i = 1,… , m.

Conditions KKT pour ( Px µν ) :

Par conséquent,
Il existe xɶ ∈ R n , µɶ ∈ R m , µɶ ≥ 0,νɶ ∈ R q tels que
( x , µ ,ν ) satisfait m q
∇f ( xɶ ) + ∑ µi ∇f i ( xɶ ) − ∇f i ( x )  + ∑ν i ∇hi ( xɶ ) − ∇hi ( x ) 
les conditions i =1
m
i =1
q

KKT pour ( Px , µ ,ν ) . + ∑ µɶ i ∇f i ( x ) + ∑νɶi ∇hi ( x ) = 0

i =1 i =1

µɶ i Lf i ( x , xɶ ) = µɶ i  f i ( x ) + ∇f i ( x ) ( xɶ − x )  = 0
T
i = 1,… , m.
Corollaire 2. Soit f , f i , hi ∈ C 1. Soit la suite {( x , µ ,ν )} telle
k k k

que ( x k +1 , µ k +1 ,ν k +1 ) satisfait les conditions KKT pour Pxk , µ k ,ν k . ( )

{ }
Si la suite ( x k , µ k ,ν k ) converge vers le point ( x* , µ * ,ν * ) ,
alors ce dernier satisfait les conditions KKT pour ( P ) .

{ }
Preuve. Puisque ( x k , µ k ,ν k ) → ( x* , µ * ,ν * ) , alors par la
continuité des fonctions, il s'ensuit que ( x* , µ * ,ν * ) satisfait les
(
conditions KKT pour Px* , µ* ,ν * . )
( x k +1
, µ k +1
,ν k +1
(
) satisfait les conditions KKT pour Pxk ,µ k ,ν k )
lim ( x k +1 , µ k +1 ,ν k +1 ) satisfait les conditions KKT pour lim Pxk , µ k ,ν k
k →∞ k →∞
( )
( x *
, µ *
,ν *
(
) satisfait les conditions KKT pour Px* ,µ* ,ν * )
Corollaire 2. Soit f , f i , hi ∈ C 1. Soit la suite {( x , µ ,ν )} telle
k k k

que ( x k +1 , µ k +1 ,ν k +1 ) satisfait les conditions KKT pour Pxk , µ k ,ν k . ( )

{ }
Si la suite ( x k , µ k ,ν k ) converge vers le point ( x* , µ * ,ν * ) ,
alors ce dernier satisfait les conditions KKT pour ( P ) .

{ }
Preuve. Puisque ( x k , µ k ,ν k ) → ( x* , µ * ,ν * ) , alors par la
continuité des fonctions, il s'ensuit que ( x* , µ * ,ν * ) satisfait les
(
conditions KKT pour Px* , µ* ,ν * . )
Par le théorème 1, puisque i ) il existe un µ * ∈ R m , µ * ≥ 0, et un
ν * ∈ R q , tel que ( x* , µ * ,ν * ) satisfait les conditions KKT pour
( )
Px* , µ* ,ν * , alors ii ) ( x* , µ * ,ν * ) satisfait les conditions KKT
pour ( P ) . Théorème 1. Soient f , f i , hi ∈ C 1 . Alors les énoncés suivants
sont équivalents.
□
i ) Il existe un µ ∈ R m , µ ≥ 0, et un ν ∈ R q tel que ( x , µ ,ν )
satisfait les conditions KKT pour ( Px , µ ,ν ) .
ii ) Le triplet ( x , µ ,ν ) satisfait les conditions KKT pour ( P ) .
iii ) Pour tout µ ∈ R m , µ ≥ 0, et ν ∈ R q , ( x , µ ,ν ) satisfait les
conditions KKT pour ( Px , µ ,ν ) .
Voici maintenant des conditions suffisantes assurant l'existence
{ }
et la convergence de la suite ( x k , µ k ,ν k ) .
Théorème 3. Soit ( x* , µ * ,ν * ) un point satisfait les conditions KKT
pour ( P ) , et satisfaisant également les conditions d'optimalité de
deuxième ordre, les conditions d'écarts complémentaires strictes, et
d'indépendance linéaire des gradients des contraintes actives.
Supposons que f , f i , hi sont continuement différentiable dans un
voisinage Bε ( x* ) de x* . Alors il existe un scalaire δ > 0 tel que
si la procédure est initialisée au point ( x 0 , µ 0 ,ν 0 ) où
( x 0
, µ 0
,ν 0
) (
− x *
, µ *
,ν *
) <δ
{ }
alors la suite ( x k , µ k ,ν k ) existe et converge vers ( x* , µ * ,ν * )
de façon R − quadratique; i.e., il existe une constante K telle
que pour tout k ≥ 0
2i 2k
∞  1  1
( x , µ ,ν ) − ( x , µ ,ν ) ≤ K i∑=k  2  ≤ Q  2 
k k k * * *

i
   
2
∞  1
où Q = 2 K ∑   .
i =0  2 
Dans leur article, Murtagh et Saunders introduisent un terme
pénalité dans la fonction économique pour retrouver un problème
qui s'apparente à un lagrangien augmenté.

Ceci permet de contourner la difficulté d'amorcer la procédure

dans le voisinage d'un point satisfaisant les conditions KKT pour
le problème ( P ) .

La procédure résultante est à la base de leur logiciel

MINOS/AUGMENTED pour résoudre des problèmes de
programmation mathématique.
 Pour simplifier, considerons le problème avec des contraintes
d'égalité
( PE ) Min f ( x )
Sujet à hi ( x ) = 0 i = 1,… , q
x∈ X
À l'itération ( k + 1) de la procédure de résolution, étant donné
une solution x k et des multiplicateurs ν k obtenus à
l'itération précédente k , nous considérons le problème PExk ,ν k ( )
q q 2
Min f ( x ) +∑ν  hi ( x ) − Lhi ( x , x )  + 1 ρ ∑  hi ( x ) − Lhi ( x , x ) 
k k k

i =1
i
2 i =1
Sujet à Lhi ( x k , x ) = 0 i = 1,… , q
x∈ X

où
T
Lhi ( x , x ) = hi ( x ) + ∇hi ( x
k k k
) (x − x )
k
i = 1,… , q
Théorème 4. Soit la paire ( x k ,ν k ) . Soit ( xˆ ,νˆ ) un point satisfaisant
( )
les conditions KKT pour PE k k . Si (ν k −νˆ ) = ε 1 et
T
x ,ν

 h1 ( xˆ ) ,… , hq ( xˆ )  = ε 2 , alors ( xˆ ,νˆ ) est aussi un point satisfaisant

les conditions KKT pour le problème perturbé
q
( PEε ) Min f ( x ) + ∑ (ε i1 + ρε i2 )  hi ( x ) − Lhi ( x k , x )
i =1

2
Sujet à hi ( x ) = 0 i i = 1,… , q
ε
x∈ X

Preuve. Ceci découle directement des conditions KKT pour

( )
les problèmes PExk ,ν k et ( PEε ) .
 q q 2
Min f ( x ) +∑ν  hi ( x ) − Lhi ( x k , x )  + 1 ρ ∑  hi ( x ) − Lhi ( x k , x ) 
k
q i
2 i =1
Min f ( x ) + ∑ ( ε i1 + ρε i2 )  hi ( x ) − Lhi ( x k , x )  i =1
Sujet à Lhi ( x , x ) = 0 i = 1,… , q
k
i =1
x∈ X
Sujet à hi ( x ) = ε i2 i = 1,… , q
x∈ X où
T
Lhi ( x k , x ) = hi ( x k ) + ∇hi ( x k ) (x − x )
k
i = 1,… , q

Soit ( xˆ ,νˆ ) un point satisfaisant les conditions KKT pour PExk ,ν k :

q
( )
∇f ( xˆ ) + ∑ν ik ∇hi ( xˆ ) − ∇hi ( x k ) 
i =1
q q
+ ρ ∑  hi ( xˆ ) − Lhi ( x , xˆ )  ∇hi ( xˆ ) − ∇hi ( x )  + ∑νˆi ∇hi ( x k ) = 0
k k

i =1 i =1

Puisque Lhi ( x k , xˆ ) = 0, alors

q
∇f ( xˆ ) + ∑ν ik ∇hi ( xˆ ) − ∇hi ( x k ) 
i =1
q q
+ ρ ∑ hi ( xˆ ) ∇hi ( xˆ ) − ∇hi ( x )  + ∑νˆi ∇hi ( x k ) = 0
k

i =1 i =1
Puisque Lhi ( x k , xˆ ) = 0, alors
q
∇f ( xˆ ) + ∑ν ik ∇hi ( xˆ ) − ∇hi ( x k ) 
i =1
q q
+ ρ ∑ hi ( xˆ ) ∇hi ( xˆ ) − ∇hi ( x )  + ∑νˆi ∇hi ( x k ) = 0
k

i =1 i =1

q
Additionnons et soustrayons la quantité ∑νˆi ∇hi ( xˆ )
i =1
q q q
∇f ( xˆ ) + ∑ν i ∇hi ( xˆ ) − ∇hi ( x )  − ∑νˆi ∇hi ( xˆ ) + ∑νˆi ∇hi ( xˆ )
k k

i =1 i =1 i =1
q q
+ ρ ∑ hi ( xˆ ) ∇hi ( xˆ ) − ∇hi ( x k )  + ∑νˆi ∇hi ( x k ) = 0
i =1 i =1

Alors nous obtenons

q
( )
∇f ( xˆ ) + ∑ ν ik −νˆi ∇hi ( xˆ ) − ∇hi ( x k ) 
i =1
q q
+ ρ ∑ hi ( xˆ ) ∇hi ( xˆ ) − ∇hi ( x )  + ∑νˆi ∇hi ( xˆ ) = 0
k

i =1 i =1
Alors nous obtenons
q
( )
∇f ( xˆ ) + ∑ ν ik −νˆi ∇hi ( xˆ ) − ∇hi ( x k ) 
i =1
q q
+ ρ ∑ hi ( xˆ ) ∇hi ( xˆ ) − ∇hi ( x )  + ∑νˆi ∇hi ( xˆ ) = 0.
k

i =1 i =1

Mais par définition

T
(ν k
− νˆ ) = ε 1
et  h
 1 ( ˆ
x ) , … , hq ( ˆ
x ) 
 = ε 2
,
et ainsi nous retrouvons
q q
∇f ( xˆ ) + ∑ ( ε i + ρε i ) ∇hi ( xˆ ) − ∇hi ( x )  + ∑νˆi ∇hi ( xˆ ) = 0.
1 2 k

i =1 i =1

Par conséquent ( xˆ ,νˆ ) est un point satisfaisant les conditions

KKT pour le problème ( PEε ) . □
q
Min f ( x ) + ∑ ( ε i1 + ρε i2 )  hi ( x ) − Lhi ( x k , x ) 
i =1

Sujet à hi ( x ) = ε i2 i = 1,… , q
x∈ X
Conséquence. Ce théorème indique que si ε 1 et ε 2 sont
suffisemment petits, alors ( xˆ ,νˆ ) est un point satisfaisant les
conditions KKT pour un problème ( PEε ) très rapproché du
problème original ( PE ) .
q
Min f ( x ) + ∑ ( ε i1 + ρε i2 )  hi ( x ) − Lhi ( x k , x ) 
i =1

Sujet à hi ( x ) = ε i2 i = 1,… , q
x∈ X

Par conséquent le point ( xˆ ,νˆ ) se trouve dans un voisinage

suffisemment petit autour d'un point satisfaisant les conditions
KKT pour le problème original ( PE ) .

Ainsi, lorsqu'un point ( xˆ ,νˆ ) satisfait les conditions du théorème 4

où ε 1 et ε 2 sont suffisemment petits, alors à partir de l'itération
suivante ( k + 1) , la valeur de ρ peut être ramenée à 0 tout en
étant assuré de la convergence de la procédure en se référant
au théorème 3.
MINOS/AUGMENTED
Le problème générique résolu avec cette méthode est le suivant:

( PM ) Min f ( x ) + c T x + d T y
Sujet à H ( x ) + A1 y = b1
A2 x + A3 y = b 2
l ≤ x  ≤ u
 y 
T
où H ( x ) =  h1 ( x ) ,… , hq ( x )  .

x sont dites variables non linéaires et y, variables linéaires.

Hypothèses:
i ) f ( x ) , h1 ( x ) ,… , hq ( x ) sont de classe C 2
ii ) ∇ 2 f ( x ) , ∇ 2 h1 ( x ) ,… , ∇ 2 hq ( x ) ont leurs éléments bornés
iii ) il existe un minimum local x* qui avec un vecteur de
multiplicateurs λ * satisfait les conditions KKT de premier
et de second ordre.
Étant donné une paire ( x k , λ k ) , considérons le sous-problème
avec contraintes linéaires suivant:

( PM xk ,λ k ) Min f ( x ) + c x + d y − λ
T T kT
 H ( x ) − LH ( x k , x ) 
T
+ 1 ρ  H ( x ) − LH ( x , x )   H ( x ) − LH ( x k , x ) 
k
2
Sujet à LH ( x k , x ) + A1 y = b1
A2 x + A3 y = b 2
l ≤ x  ≤ u
 y 
T
où LH ( x , x ) =  Lh1 ( x , x ) ,… , Lhq ( x , x )  et
k k k

T
Lhi ( x , x ) = hi ( x ) + ∇hi ( x
k k k
) (x − x ) k
i = 1,… , q
Procédure de résolution.

Initialisation. Soit ( x 0 y 0 ) ∈ R n et λ 0 ∈ R q . Spécifions une valeur

du paramètre ρ ≥ 0 et un niveau de tolérance ε t > 0.
Posons k = 0.
Étape 1. Résoudre le problème PM xk ,λ k . ( )
Soit ( x k +1 , y k +1 ) une solution de ce problème.
Déterminer le vecteur de multiplicateurs optimaux λ k +1 .
( PM xk ,λ k ) T
Min f ( x ) + c T x + d T y − λ k  H ( x ) − LH ( x k , x ) 
T
+ 1 ρ  H ( x ) − LH ( x k , x )   H ( x ) − LH ( x k , x ) 
2
Sujet à LH ( x k , x ) + A1 y = b1
A2 x + A3 y = b 2
l ≤ x  ≤ u
 y 

Étape 2. Si x k +1 satisfait le critère d'arrêt assurant la convergence,

alors terminer la procédure.
Initialisation. Soit ( x 0 y 0 ) ∈ R n et λ 0 ∈ R q . Spécifions une valeur
du paramètre ρ ≥ 0 et un niveau de tolérance ε t > 0.
Posons k = 0.
Étape 1. Résoudre le problème PM xk ,λ k . ( )
Soit ( x k +1 , y k +1 ) une solution de ce problème.
Déterminer le vecteur de multiplicateurs optimaux λ k +1.
Étape 2. Si x k +1 satisfait le critère d'arrêt assurant la convergence,
alors terminer la procédure.
T
Si  h1 ( xˆ ) ,… , hq ( xˆ )  = ε 2
H (x k +1
)+ A y −b 1
k +1 1

Étape 3. Si ≤ εt
1+ (x , y )
k +1 k +1
et (ν k −νˆ ) = ε 1
λ k +1 − λ k
et si ≤ ε t, ( PM ) Min f ( x ) + c T x + d T y
1 + λ k +1 Sujet à H ( x ) + A1 y = b1
alors ramener ρ à 0. A2 x + A3 y = b 2
l ≤ x  ≤ u
 y 
Initialisation. Soit ( x 0 y 0 ) ∈ R n et λ 0 ∈ R q . Spécifions une valeur
du paramètre ρ ≥ 0 et un niveau de tolérance ε t > 0.
Posons k = 0.
Étape 1. Résoudre le problème PM xk ,λ k . ( )
Soit ( x k +1 , y k +1 ) une solution de ce problème.
Déterminer le vecteur de multiplicateurs optimaux λ k +1 .
Étape 2. Si x k +1 satisfait le critère d'arrêt assurant la convergence,
alors terminer la procédure.
H ( x k +1 ) + A1 y k +1 − b1
Étape 3. Si ≤ εt
1+ ( x , y k +1 k +1
)
λ k +1 − λ k
et si ≤ ε t,
1+ λ k +1

alors ramener ρ à 0.
( )
Étape 4. Définir le problème PM xk +1 ,λ k +1 , poser k = ( k + 1)
et reprendre l'étape 1.
Remarques.

i ) Lorsque ρ = 0 nous retrouvons la procédure de Robinson.

ii ) L'addition d'un terme de pénalité a plusieurs effets bénifiques.

Il a en quelque sorte un effet de "convexification" de la fonction

économique entrainant une situation pour laquelle nous pouvons
espérer que la procédure converge.

De plus ce terme a également pour effet de réduire le niveau de

différence accepté entre les valeurs des fonctions et celles de
leurs linéarisations. Ceci permet d'éviter de trop modifier la
valeur de x dans une région où la non linéarité des fonctions est
forte et où, par conséquent, l'approximation linéaire n'est valable
que dans un voisinage restreint de x k .

iii ) La procédure comporte également un mécanisme pour

augmenter la valeur de ρ lorsque les valeurs des multiplicateurs
λ k et λ k +1 sont très différentes.
Question.
Pourquoi conserver les contraintes linéarisées plutôt que de
procéder comme dans l'approche du lagrangien augmenté
classique où il n'y a pas de contraintes?

Principalement parce que Murtagh et Saunders avait développer

antérieurement le logiciel MINOS pour traiter des problèmes
de programmation mathématique avec des contraintes linéaires.
Ils disposaient donc d'une procédure efficace pour résoudre les
( )
sous-problèmes PM xk ,λ k .
Le logiciel MINOS est une implémentation de la méthode
du gradient réduit.
Références.

B.A. Murtagh, M.A. Saunders, "A Projected Lagrangean Algorithm

and its Implementation for Sparse Nonlinear Constraints,"
Mathematical Programming Study 16 (1982), 84 - 117.
S.M. Robinson, "A Quadratically-convergent Algorithm for General
Nonlinear Programming Problem," Mathematical Programming
3(1972), 145 - 156.