View
214
Download
0
Category
Preview:
Citation preview
Dualité lagrangienne
Problème dual lagrangien
( )( )
Considérons le problème de programmation mathématique suivant
Min Sujet à 0 1, ,
.
Le probl
Prim
ème dual lagrangien Définition associé au p
al
.
in
f x
f x i m
x X R
≤ =∈ ⊂
…
( )
( ) ( ){ }{ }0 1
roblème primalrelativement aux contraintes 0 1, , , s'écrit
Max InDual f
i
m
i ix X i
f x i m
f x f xλ
λ∈≥ =
≤ =
+∑
…
( )
( ) ( ){ }{ }0 1
Le problème dual lagrangien associé au problème primalrelativement aux contraintes 0 1, , , s'écrit
Max
Définition
Infual
.
D
i
m
i ix X i
f x i m
f x f xλ
λ∈≥ =
≤ =
+∑
…
( ) ( ) ( ){ }{ }
1
La fonction économique du dual
Inf
est une fonction concave sur l'ensemble : 0 pour toutes fonctions et .
m
i ix X i
m
i
g f x f x
R
f f
λ λ
λ λ∈ =
= +∑
∈ ≥
( )
( ) ( ){ }
1
*
*
Soient et . Si est convexe et si pour toute valeur, , : est convexe sur , démontrer que
l'ensemble = : Sup , est convexe
et que est convexe sur .
n m
b B
A R B R Ab B h a b A B R A
A a A l a h a b
l A
∈
⊂ ⊂∈ × →
∈ = < ∞
( )( )
( )( ){ }
La du problème Min
Sujet à 0 1, ,
est le infimum de la fonction
valeur o
sur l'ensemble: 0 1, , .
ptimaPrimal
le
in
i
f x
f x i m
x X Rf x
x X f x i m
≤ =∈ ⊂
∈ ≤ =
…
…
( ) ( ){ }{ }( ) ( ) ( ){ }
{ }
0 1
1
La du problème
Max Inf
est le supremum de la fonction =
Dual
valeur
Inf
sur l'ensem
optim
ble
al
0 .
e
:
m
i ix X i
m
i ix X i
m
f x f x
g f x f x
R
λλ
λ λ
λ λ
∈≥ =
∈ =
+∑
+∑
∈ ≥
( )Par convention, le infimum (supremum) d'une fonction sur unensemble vide est égal à .∞ −∞
Quelques définitions
( )
( ) ( )
( )
( )
* *
* *
1
* *
1*
*
Une paire , de points satisfait les
pour le problème primal si
i) est un minimum global de + sur
ii)
c
onDéfinition.
0
iii) 0, 1
dition
, ,
i
s
d'optimali
v) 0
tém
i i
im
i i
i
i
i
x
x f x f x X
f x
f x i m
λ
λ
λ
λ
=
=
=
≤ =
≥
∑
∑
…
, 1, , .i m= …
Similarité avec le théorème d'optimalité basé sur les multiplicateurs de LagraNote.
nge.
( )( )
Min Sujet à 0 1, ,
.
Primal
in
f x
f x i m
x X R
≤ =∈ ⊂
…
( )
( ) ( )
( )
( )
* *
* *
1
* *
1*
*
Une paire , de points satisfait les
pour le problème primal si
i) est un minimum global de + sur
ii)
c
onDéfinition.
0
iii) 0, 1
dition
, ,
i
s
d'optimali
v) 0
tém
i i
im
i i
i
i
i
x
x f x f x X
f x
f x i m
λ
λ
λ
λ
=
=
=
≤ =
≥
∑
∑
…
, 1, , .i m= …
( )*
* * *
est dénoté un
pour le primal s'il existe un tel que le couple , sa
vecteu
tisfai
Définit
t
les co
r de multiplicateu
nditions d'optimal
r
i
s optimaux
té pour le
ion.
primal.
x x
λ
λ
( )( )
Min Sujet à 0 1, ,
.
Primal
in
f x
f x i m
x X R
≤ =∈ ⊂
…
( ) ( ) ( ){ }
La associée au problème
primal est définie sur de la façon
Définiti
suivant
fonction de pertu
e:Inf : , 1, , .
rbationon.m
i ix X
v
R
v y f x f x y i m∈
= ≤ = …
( )
( ) ( )
Le problème primal est si 0 prend une valeurfinie et s'il existe un scalaire 0 tel que pourDéfinitio
toutstabl
00
.
en. v
M y
v v yM
y
> ≠
−≤
( )( )
Min Sujet à 0 1, ,
.
Primal
in
f x
f x i m
x X R
≤ =∈ ⊂
…
( )
( ) ( )
Le problème primal est si 0 prend une valeurfinie et s'il existe un scalaire 0 tel que pourDéfinitio
toutstabl
00
.
en. v
M y
v v yM
y
> ≠
−≤
( ) Le problème primal est si 0 prendune valeur finie et si la fonction ne décoît pas très brusquement dans aucune direction de perturbatio
Définition équ
n dans le vois
iv
in
ale
age
st
d
nt
e 0; i.e.,
ab ee l. v
v
( ) ( )0
0
pour tout 0
0lim .
y
v v y
yθθ
θ
θ→>
≠
−< ∞
( ) ( ) ( ){ }
La associée au problème
primal est définie sur de la façon
Définiti
suivant
fonction de pertu
e:Inf : , 1, , .
rbationon.m
i ix X
v
R
v y f x f x y i m∈
= ≤ = …
1
1 2
1
Si les fonctions et , , sont convexes sur
alors la fonction de perturbation est aussi convexe sur .
Il faut démontrer que pour toute pDémonstration. a
Propri
ire de
été
points
1
.
, ,
mm
m
f f f X
v R
y y R
v yθ
∈
+
…
( )( ) ( ) ( ) ( )
( )( ) ( ) ( ) ( ){ }( ) ( ) ( ){ }( ) ( ) ( ){ }
2 1 2
1 2 1 2
1 1 1 1
1
2 2 2 2
2
1 .
Or
1 Inf : 1 , 1, ,
Inf : , 1, ,
Inf : , 1, ,
i i ix X
i ix X
i ix X
y v y v y
v y y f x f x y y i m
v y f x f x y i m
v y f x f x y i m
θ θ θ
θ θ θ θ∈
∈
∈
− ≤ + −
+ − = ≤ + − =
= ≤ =
= ≤ =
…
…
…
( )( ) ( ) ( ) ( ){ }1 2 1 21 Inf : 1 , 1, ,i i ix X
v y y f x f x y y i mθ θ θ θ∈
+ − = ≤ + − = …
( )( )( )( ) ( )
1 2
1 2 1 21 2,
1 :Inf
1 1 , 1, ,x x X i i i
f x x
f x x y y i m
θ θ
θ θ θ θ∈
+ − =
+ − ≤ + − = …
( ) ( ) ( )( )( ) ( )
1 2
1 2 1 21 2,
1 :Inf
1 1 , 1, ,
(puisque est convexe sur )
x x X i i i
f x f x
f x x y y i m
f X
θ θ
θ θ θ θ∈
+ − ≤
+ − ≤ + − = …
( ) ( ) ( )( ) ( ) ( ) ( )
( )( ) ( ) ( ) ( ) ( )
1 2
1 2 1 21 2,
1 2 1 2 1 2
1 :Inf
1 1 , 1, ,
(puisque est convexe sur , alors
1 1 1
x x X i i i i
i
i i i i i
f x f x
f x f x y y i m
f X
f x x f x f x y y
θ θ
θ θ θ θ
θ θ θ θ θ θ
∈
+ − ≤
+ − ≤ + − =
+ − ≤ + − ≤ + −
…
( )( ) ( ) ( ) ( ){ }1 2 1 21 Inf : 1 , 1, ,i i ix X
v y y f x f x y y i mθ θ θ θ∈
+ − = ≤ + − = …
( ) ( ) ( )( ) ( ) ( ) ( )
( )( ) ( ) ( ) ( ) ( )
1 2
1 2 1 21 2,
1 2 1 2 1 2
1 :Inf
1 1 , 1, ,
puisque est convexe sur , alors
1 1 1
x x X i i i i
i
i i i i i
f x f x
f x f x y y i m
f X
f x x f x f x y y
θ θ
θ θ θ θ
θ θ θ θ θ θ
∈
+ − ≤
+ − ≤ + − =
+ − ≤ + − ≤ + −
…
( ) ( ) ( )( ) ( )
( ) ( ){ }( ) ( ) ( ) ( ){ }
1 2
1 1 2 21 2,
1 2 1 1 2 2
1 2 1 2 1 2
1 :Inf
et , 1, ,
puisque pour 1,
, : et
, : 1 1
x x X i i i i
i i i i
i i i i
f x f x
f x y f x y i m
i m
x x X f x y f x y
x x X f x f x y y
θ θ
θ θ θ θ
∈
+ − ≤
≤ =
=
∈ ≤ ≤ ⊂
∈ + − ≤ + −
…
…
( )( ) ( ) ( ) ( ){ }1 2 1 21 Inf : 1 , 1, ,i i ix X
v y y f x f x y y i mθ θ θ θ∈
+ − = ≤ + − = …
( ) ( ) ( )( ) ( )
( ) ( ){ }( ) ( ) ( ) ( ){ }
1 2
1 1 2 21 2,
1 2 1 1 2 2
1 2 1 2 1 2
1 :Inf
et , 1, ,
puisque pour 1,
, : et
, : 1 1
x x X i i i i
i i i i
i i i i
f x f x
f x y f x y i m
i m
x x X f x y f x y
x x X f x f x y y
θ θ
θ θ θ θ
∈
+ − ≤
≤ =
=
∈ ≤ ≤ ⊂
∈ + − ≤ + −
…
…
( ) ( ){ }( ) ( ) ( ){ }
1 1 1
1
2 2
2
Inf : , 1, ,
1 Inf : , 1, ,
i ix X
i ix X
f x f x y i m
f x f x y i m
θ
θ
∈
∈
≤ ≤ = +
− ≤ =
…
…
( ) ( ) ( )1 21v y v yθ θ= + − �
( ) ( ) ( )
1
T
Soient une fonction convexe : où et un point où prend une valeur finie. Un vecteur est sous-gradieun
de à
Défn
si pout
r tout
init o
i n: n
n
X R X R
x X f R
x x X
x x x x
φ
γφ
φ φ γ
→ ⊂
∈ ∈∈
≥ + −
φ
x
( ) ( )T1
x x xφ γ+ −
( ) ( )T2
x x xφ γ+ −
( ) Aux points où est différentiable, le gardient est
l'unique sous-gradient et par conséquent l'unique éléR
memarque
ent de :
.x X
x
φ
φ
∈
∂( ) dénote l'ensemble des sous-gradients de àDéfinitio un point
.n: x
x X
φ φ∂
∈
Théorèmes de dualité
( ) ( )
( ) ( )1
Si est une solution réalisable du
primal et une solution réalisable du dual, alors .
Considérons la quantit
Théorème de dua
é .
D'une part,
Preu
lité f
aible.
e
v .m
i i
i
x
f x g
f x f x
λ λ
λ=
≥
+∑
( ) ( ) ( )
( )1
puisque 0 et 0, 1, , .
m
i i
i
i i
f x f x f x
f x i m
λ
λ=
+ ≤
≤ ≥ =
∑…
Pour le premier théorème de dualité faible, nous n'avons pasbesoin d'hypothèses particulières sur , ni sur les fonctions et , 1, , .i
X
f f i m= …
( ) ( )
( ) ( )1
Si est une solution réalisable du
primal et une solution réalisable du dual, alors .
Considérons la quantit
Théorème de dua
é .
D'une part,
Preu
lité f
aible.
e
v .m
i i
i
x
f x g
f x f x
λ λ
λ=
≥
+∑
( ) ( ) ( )
( )1
puisque 0 et 0, 1, , .
m
i i
i
i i
f x f x f x
f x i m
λ
λ=
+ ≤
≤ ≥ =
∑…
( ) ( ) ( ) ( ) ( )1 1
D'autre part,
= Inf
puisque .
m m
i i i ix X
i i
g f x f x f x f x
x X
λ λ λ∈
= =
+ ≤ +
∈
∑ ∑
( ) ( ) ( ) ( ) ( ) ( )1 1
Donc
= Inf .m m
i i i ix X
i i
g f x f x f x f x f xλ λ λ∈
= =
+ ≤ + ≤
∑ ∑ �
Pour les prochains théorèmes nous avons besoin de l'hypothèsede convexité des fonctions et , 1, , , sur convexe.if f i m X= …
Supposons que le problème primal possède une solutionoptimale, que est convexe et que et , 1, , ,sont convexes.Alorsi) il existe un vecteur de multiplicateurs optimaux pour le prima
Théorème.
iX f f i m= …
l si et seulement si le problème primal est stable;ii) est un vecteur de multiplicateurs optimaux pour le problème primal si et seulement si est un sous-gradient de la fonction de pe
λλ−
rturbation au point 0.v y =
Dans i), la stabilité joue un rôle quelque peu similaireà celui des restrictions sur les fonctions de contraintes dans les conditions d'optimalit
Remarques
é de
.
KKT
i) il existe un vecteur de multiplicateurs optimaux pour le primal si et seulement si le problème primal est stable;
Dans i), la stabilité joue un role quelque peu similaireà R
cemarquelu
es.i des restrictions sur les fonctions de contraintes dans les
conditions d'optimalité de KKT
Mais la stabilité est une condition nécessaire et suffisante pourl'existence de multiplicateurs optimaux du primal alors que lesrestrictions sur les fonctions de contraintes ne sont que suffisantes pour les conditions d'optimalité de KKT.
Les restrictions sur les fonctions de contraintes ne font pas intervenirdirectement la fonction économique alors que la stabilité est définie à partir de la fonction de perturbation qui fait intervev nir directementla fonction économique.
i) il existe un vecteur de multiplicateurs optimaux pour le primal si et seulement si le problème primal est staRemarqu
ble;es.
Certains problèmes sont stables même si les restrictions sur lesfonctions de contraintes ne sont pas satisfaites. C'est le cas pour les problèmes où la fonction économique est constante.
( )( )
{ }1
1
De même, certains problèmes sont instables même si les restrictions sur les fonctions de contraintes sont satisfaites. Par exemple, dans leproblème suivant
Min
Sujet à 0
: 0 ,
l
f x x
f x x
x X x R x
= −
= ≤
∈ = ∈ ≥
( ) ( ) ( )
es contraintes étant linéaires, les restrictions sur les fonctions de contraintes sont satisfaites. Mais le problème est instable puisque
00 1
tend vers lorsque 0 est suffisamment près d
yv v y
y y y
y
− −−= =
∞ > e 0.
Supposons que le problème primal possède une solutionoptimale, que est convexe et que et , 1, , ,sont convexes.Alorsi) il existe un vecteur de multiplicateurs optimaux pour le prima
Théorème.
iX f f i m= …
l si et seulement si le problème primal est stable;ii) est un vecteur de multiplicateurs optimaux pour le problème primal si et seulement si est un sous-gradient de la fonction de pe
λλ−
rturbation au point 0.v y =
( ) ( )( )
*
Soit un vecteur de multiplicateurs optimaux. Considérons le problème perturbé
(1) Min
ii) et analyse
Sujet à
de sen
sitivité.
1, ,.
i i
v y f x
f x y i m
x X
λ
θ
θ
=
≤ =
∈
…
ii) est un vecteur de multiplicateurs optimaux pour le problème primal si et seulement si est un sous-gradient de la fonction de perturbation au point 0.v y
λλ−=
( ) ( )( )
*
Soit un vecteur de multiplicateurs optimaux. Considérons le problème perturbé
(1) Min
ii) et analyse
Sujet à
de sen
sitivité.
1, ,.
i i
v y f x
f x y i m
x X
λ
θ
θ
=
≤ =
∈
…
( ) ( ) ( ) ( ) ( )
( )
*
T T* *
T*
Puisqu'alors est un sous-gradient de la fonction de perturbation à 0, il s'ensuit que
0 0 0 .
Ainsi, 0 est une borne inférieure sur la valeur optimal du problème (1).
v
v y v y v y
v y
λ
θ λ θ θλ
θλ
−
≥ + − − = −
−
( ) ( )( )
ii) et analyse de sensitivité (1) Min
Suje
.
t à 1, ,.
i i
v y f x
f x y i m
x X
θ
θ
=
≤ =
∈
…
( ) ( ) ( ) ( ) ( )
*
T T* *
Puisqu'alors est un sous-gradient de la fonction de perturbation à 0, il s'ensuit que
0 0 0 .
v
v y v y v y
λ
θ λ θ θλ
−
≥ + − − = −
( ) ( )
( )( ) ( ) ( )
T* *
1T*
T* *
010
Également, si >0, alors0
et ainsi est une borne inférieure sur la dérivée à droitede à =0; i.e.,
0lim
m
iii
m
iii
v y vy y
y
v y
v y v y vy y
θθ
θθ
λ λθ
λθ θ
θ θλ λ
θ θ
=
+
→=>
−≥ − = −
−
∂ −= ≥ − = −
∂
∑
∑
( ) ( )( )
ii) et analyse de sensitivité (1) Min
Suje
.
t à 1, ,.
i i
v y f x
f x y i m
x X
θ
θ
=
≤ =
∈
…
( ) ( ) ( ) ( ) ( )
*
T T* *
Puisqu'alors est un sous-gradient de la fonction de perturbation à 0, il s'ensuit que
0 0 0 .
v
v y v y v y
λ
θ λ θ θλ
−
≥ + − − = −
( ) ( ) ( ) T* *
010
*
Également, si >0, alors
0lim
Ainsi, est une borne inférieure sur le taux marginal de variationde la valeur optimal du primal relativement à une augmentation d
m
i i
i
i
v y v y vy y
θθ
θ
θ θλ λ
θ θ
λ
+
→=>
∂ −= ≥ − = −
∂
−
∑
e
la valeur du terme de droite de la contrainte.ièmei
Si le problème primal est stable, est convexe et et , 1, , ,sont convexes sur , alors
i) le problème dual possède une solution op
Théorème de dualité fort
timale;ii) la valeur optimale du
e.
iX f f i m X= …
*
*
problème primal est égale à celle du problème dual;
iii) est une solution optimale du problème dual si et seulement
si est un sous-gradient de la fonction de perturbation du probl
v
λ
λ−
( )
* *
* *
ème primal à 0;
iv) si est une solution optimale du problème dual, alors est une solution optimale du problème primal si et seulement si
, satisfait les conditions d'optimalité.
y
x
x
λ
λ
=
Interprétation géométrique
( )( )1
1
Considérons le problème primal suivant comportant une seule variable et une seule contrainte pour faciliter la présentation
Min
Sujet à 0
.
Associons à ce problème l'ensemble suivant défini
f x
f x
x R
≤
∈
( ) ( ) ( ){ }
( ) ( ){ }
2
2 11 2 1 1 2
110
dans
= , :il existe un tel que ,
Le problème dual associé au problème primal précédent prendla forme suivante:
Max Inf x R
R
z z R x R z f x z f x
f x f xλ
λ∈≥
Γ ∈ ∈ = =
+
( )
( ) ( ) ( ){ }
( ) ( ) ( ){ }
1 110
1
2 11 2 1 1 2
Primal Min Dual
Sujet à 0 Max Inf
.
= , :il existe un tel que ,
x R
f x
f x f x f x
x R
z z R x R z f x z f x
λλ
≥ ∈
≤ +
∈
Γ ∈ ∈ = =
Illustration de dans la figure suivante:Γ
Γ
1z
2z
P
( ) ( )( )
2
1
1
Pour résoudre le problème primal,il suffit de trouver le point de quiminimise la composante sujet àla contrainte que 0.
Sur la figure, le point ,
à l'intersection de la courbe et del'ax
z
z
P f x f x
Γ
≤
=
Γ
2e des est associé à la solution optimale .
z
x
•
( )
( ) ( ) ( ){ }
( ) ( ) ( ){ }
1 110
1
2 11 2 1 1 2
Primal Min Dual
Sujet à 0 Max Inf
.
= , :il existe un tel que ,
x R
f x
f x f x f x
x R
z z R x R z f x z f x
λλ
≥ ∈
≤ +
∈
Γ ∈ ∈ = =
Illustration de dans la figure suivante:Γ
Γ
1z
2z
P
( ){ }
1 2
2 1,0 1 2
Pour résoudre le problème dual,nous le formulons en termes des variables et :
Max Inf .z z
z z
z zλ
λ∈Γ≥
+
( ){ }2 1
,1 2
2 1
Considérons la minimisationinterne
Min .
Mais est la valeur del'ordonnée à l'origine de la droitede pente .
z zz z
z z
λ
λ
λ
∈Γ+
+
−
•
( )
( ) ( ) ( ){ }
( ) ( ) ( ){ }
1 110
1
2 11 2 1 1 2
Primal Min Dual
Sujet à 0 Max Inf
.
= , :il existe un tel que ,
x R
f x
f x f x f x
x R
z z R x R z f x z f x
λλ
≥ ∈
≤ +
∈
Γ ∈ ∈ = =
Illustration de dans la figure suivante:Γ
Γ
1z
2z
P
Pour résoudre le problème deminimisation interne, il suffit dedéterminer la droite de pente ayant la plus petite ordonnée àl'origine et ayant une intersectionavec l'ensemble .
λ−
Γ
( ){ }2 1
,1 2
2 1
Considérons la minimisationinterne
Min .
Mais est la valeur del'ordonnée à l'origine de la droitede pente .
z zz z
z z
λ
λ
λ
∈Γ+
+
−
λ−
•
( )
( ) ( ) ( ){ }
( ) ( ) ( ){ }
1 110
1
2 11 2 1 1 2
Primal Min Dual
Sujet à 0 Max Inf
.
= , :il existe un tel que ,
x R
f x
f x f x f x
x R
z z R x R z f x z f x
λλ
≥ ∈
≤ +
∈
Γ ∈ ∈ = =
Illustration de dans la figure suivante:Γ
Γ
1z
2z
P
Pour résoudre le problème deminimisation interne, il suffit dedéterminer la droite de pente ayant la plus petite ordonnée àl'origine et ayant une intersectionavec l'ensemble .
λ−
Γ
( ){ }2 1
,1 2
2 1
Considérons la minimisationinterne
Min .
Mais est la valeur del'ordonnée à l'origine de la droitede pente .
z zz z
z z
λ
λ
λ
∈Γ+
+
−•
( )
( ) ( ) ( ){ }
( ) ( ) ( ){ }
1 110
1
2 11 2 1 1 2
Primal Min Dual
Sujet à 0 Max Inf
.
= , :il existe un tel que ,
x R
f x
f x f x f x
x R
z z R x R z f x z f x
λλ
≥ ∈
≤ +
∈
Γ ∈ ∈ = =
Illustration de dans la figure suivante:Γ
Γ
1z
2z
P
Pour résoudre le problème deminimisation interne, il suffit dedéterminer la droite de pente ayant la plus petite ordonnée àl'origine et ayant une intersectionavec l'ensemble .
λ−
Γ
( ){ }2 1
,1 2
2 1
Considérons la minimisationinterne
Min .
Mais est la valeur del'ordonnée à l'origine de la droitede pente .
z zz z
z z
λ
λ
λ
∈Γ+
+
−P•
( )
( ) ( ) ( ){ }
( ) ( ) ( ){ }
1 110
1
2 11 2 1 1 2
Primal Min Dual
Sujet à 0 Max Inf
.
= , :il existe un tel que ,
x R
f x
f x f x f x
x R
z z R x R z f x z f x
λλ
≥ ∈
≤ +
∈
Γ ∈ ∈ = =
Illustration de dans la figure suivante:Γ
Γ
1z
2z
P( )
{ }
1 2
2 1,0 1 2
Pour résoudre le problème dual,formulé en termes des variables et :
Max Inf ,
il suffit de déterminer la valeur de 0 correspondant au
négatif de la pente de la droitetangente
z z
z z
z zλ
λ
λ λ
∈Γ≥
+
≥
à ayant le plus grand ordonné à l'origine.
Γ
λ−
•
( )
( ) ( ) ( ){ }
( ) ( ) ( ){ }
1 110
1
2 11 2 1 1 2
Primal Min Dual
Sujet à 0 Max Inf
.
= , :il existe un tel que ,
x R
f x
f x f x f x
x R
z z R x R z f x z f x
λλ
≥ ∈
≤ +
∈
Γ ∈ ∈ = =
Illustration de dans la figure suivante:Γ
Γ
1z
2z( )
( ) ( )( )
( )
( )( )
11
1 2
2
1
1 2
La fonction de perturbation est définie
Min
Sujet à
et en termes de et z Min
Sujet à , .
Donc dans cet exemple, et sont identique.
v y
v y f x
f x y
x R
z
v y z
z y
z z
v y
=
≤
∈
=
≤
∈Γ
Γ
y
( )v y
( )
( ) ( ) ( ){ }
( ) ( ) ( ){ }
1 110
1
2 11 2 1 1 2
Primal Min Dual
Sujet à 0 Max Inf
.
= , :il existe un tel que ,
x R
f x
f x f x f x
x R
z z R x R z f x z f x
λλ
≥ ∈
≤ +
∈
Γ ∈ ∈ = =
Illustration de dans la figure suivante:Γ
Γ
1z
2z( )
( ) ( )( )
( )
( )( )
11
1 2
2
1
1 2
La fonction de perturbation est définie
Min
Sujet à
et en termes de et z Min
Sujet à , .
Donc dans cet exemple, et sont identique.
v y
v y f x
f x y
x R
z
v y z
z y
z z
v y
=
≤
∈
=
≤
∈Γ
Γ
y
( )v y
( )
( ) ( ) ( ){ }
( ) ( ) ( ){ }
1 110
1
2 11 2 1 1 2
Primal Min Dual
Sujet à 0 Max Inf
.
= , :il existe un tel que ,
x R
f x
f x f x f x
x R
z z R x R z f x z f x
λλ
≥ ∈
≤ +
∈
Γ ∈ ∈ = =
Illustration de dans la figure suivante:Γ
Γ
1z
2z
( )v y ( )Le problème est stable puisquela valeur de ne décoît pastrès brusquement lorsque s'éloigne de 0.
v y
y
( )
( ) ( ) ( ){ }
( ) ( ) ( ){ }
1 110
1
2 11 2 1 1 2
Primal Min Dual
Sujet à 0 Max Inf
.
= , :il existe un tel que ,
x R
f x
f x f x f x
x R
z z R x R z f x z f x
λλ
≥ ∈
≤ +
∈
Γ ∈ ∈ = =
Illustration de dans la figure suivante:Γ
Γ
1z
2z
P
λ−
Il est facile de voir que , lapente de la tangente à (i.e., à) au point est un sous-gradient
de à 0.Le théorème de dualité fortes'applique.
v P
v
λ−Γ
•
( )
( ) ( ) ( ){ }
( ) ( ) ( ){ }
1 110
1
2 11 2 1 1 2
Primal Min Dual
Sujet à 0 Max Inf
.
= , :il existe un tel que ,
x R
f x
f x f x f x
x R
z z R x R z f x z f x
λλ
≥ ∈
≤ +
∈
Γ ∈ ∈ = =
Illustration de dans la figure suivante:Γ
Γ
1z
2z
P
( ) ( )( )( )
2
1
1
1 1
Pour résoudre le problème primal,il suffit de trouver le point de quiminimise la composante sujet àla contrainte que 0.
Sur la figure, le point ,
est tel que 0
et la valeur optimale
z
z
P f x f x
z f x
Γ
≤
=
= <
( )2
2
est indiquée sur l'axe des .
z f x
z
=
2z•
( )
( ) ( ) ( ){ }
( ) ( ) ( ){ }
1 110
1
2 11 2 1 1 2
Primal Min Dual
Sujet à 0 Max Inf
.
= , :il existe un tel que ,
x R
f x
f x f x f x
x R
z z R x R z f x z f x
λλ
≥ ∈
≤ +
∈
Γ ∈ ∈ = =
Illustration de dans la figure suivante:Γ
Γ
1z
2z
P
( ){ }
1 2
2 1,0 1 2
Pour résoudre le problème dual,formulé en termes des variables et :
Max Inf ,
il suffit de déterminer la valeur de 0 correspondant au
négatif de la pente de la droitetangente
z z
z z
z zλ
λ
λ λ
∈Γ≥
+
≥
à ayant le plus grand ordonné à l'origine.
Γ
0λ− =2z•
( )
( ) ( ) ( ){ }
( ) ( ) ( ){ }
1 110
1
2 11 2 1 1 2
Primal Min Dual
Sujet à 0 Max Inf
.
= , :il existe un tel que ,
x R
f x
f x f x f x
x R
z z R x R z f x z f x
λλ
≥ ∈
≤ +
∈
Γ ∈ ∈ = =
Illustration de dans la figure suivante:Γ
Γ
1z
2z
( )
( ) ( )( )
( )
( )
11
1 2
2
1
1 2
La fonction de perturbation est définie
Min
Sujet à
et en termes de et z Min
Sujet à , .
v y
v y f x
f x y
x R
z
v y z
z y
z z
=
≤
∈
=
≤
∈Γ
y yy y
( )v y
( )v y( )v y ( )v y
Le saut de dualité
1 1 2 2 3 3
1 1 2 2 3 3 1 1 2 2 3 3
1 2 3
Pour illustrer le saut de dualité nous utilisons le problème de programmation linéaire mixte suivant
Min Sujet à 0
0, 0, 0 ou 1.Associons à ce
c x c x c x
a x a x a x b b a x a x a x
x x x
+ +
+ + ≥ ≡ − − − ≤
≥ ≥ =
( ){ }
( )
32
1 1 2 1 2 2 1 1 2 2 3 1 1 1 2
32
2 1 2 1 2 2 1 1 2 2 1
3
1 1
2
2
en fixant 1
, : il existe , 0 tel que = + + e
problème les ensemble
en fi
s s
xant 0
, : il existe , 0 tel qu
uiv
e = + et
t
ants:
x
z z R x x z c
x
z z R x x z c
x c x z b a x
x c x c z b a
a
x a x a
=
=
Γ = ∈ ≥ = −
Γ = ∈ ≥ = − − −
−{ }2
2
1
x
Γ = Γ Γ∪
2Γ
1Γ
( )
1 1 2 2 3 3
1 1 2 2 3 3
32
1 1 2 1 2 2 1 1 2 2
1 1 2 2 3 3
1 2 3
3
Min Sujet à 0
0, 0, 0 ou 1.Associons à ce pen fixan
roblème les ensembles suivants:t 1
, : il existe , 0 tel que = + +
c x c x c x
a x a x
x
z z R x x
a x b b a
z c x
x a x a x
x x
x
x
c c
+ +
+ + ≥ ≡ − − − ≤
≥ ≥ =
=
Γ = ∈ ≥{ }
( ){ }
1 1 1 2 2
32
2 1 2 1 2 2 1 1 2 2 1 1 1 2 2
1 2
3
en fixant 0
, : il existe , 0 tel que = +
et
e
t z b a x a
x
z z R x x z c x c x z b a x a x
x a
=
Γ = ∈ ≥ = − −
Γ = Γ
= − − −
Γ∪
Γ
( ) ( )( )
2
1
1
Pour résoudre le problème primal,il suffit de trouver le point de quiminimise la composante sujet àla contrainte que 0.
Sur la figure, le point est noté, .
z
z
P f x f x
Γ
≤
=
P
1z
2z
Valeur optimaledu primal
( )
1 1 2 2 3 3
1 1 2 2 3 3
32
1 1 2 1 2 2 1 1 2 2
1 1 2 2 3 3
1 2 3
3
Min Sujet à 0
0, 0, 0 ou 1.Associons à ce pen fixan
roblème les ensembles suivants:t 1
, : il existe , 0 tel que = + +
c x c x c x
a x a x
x
z z R x x
a x b b a
z c x
x a x a x
x x
x
x
c c
+ +
+ + ≥ ≡ − − − ≤
≥ ≥ =
=
Γ = ∈ ≥{ }
( ){ }
1 1 1 2 2
32
2 1 2 1 2 2 1 1 2 2 1 1 1 2 2
1 2
3
en fixant 0
, : il existe , 0 tel que = +
et
e
t z b a x a
x
z z R x x z c x c x z b a x a x
x a
=
Γ = ∈ ≥ = − −
Γ = Γ
= − − −
Γ∪
•
Γ
1z
2z
( ){ }
1 2
2 1,0 1 2
Pour résoudre le problème dual,formulé en termes des variables et :
Max Inf ,
il suffit de déterminer la valeur de 0 correspondant au
négatif de la pente de la droitetangente
z z
z z
z zλ
λ
λ λ
∈Γ≥
+
≥
à ayant le plus grand ordonné à l'origine.
Γ
( )
1 1 2 2 3 3
1 1 2 2 3 3
32
1 1 2 1 2 2 1 1 2 2
1 1 2 2 3 3
1 2 3
3
Min Sujet à 0
0, 0, 0 ou 1.Associons à ce pen fixan
roblème les ensembles suivants:t 1
, : il existe , 0 tel que = + +
c x c x c x
a x a x
x
z z R x x
a x b b a
z c x
x a x a x
x x
x
x
c c
+ +
+ + ≥ ≡ − − − ≤
≥ ≥ =
=
Γ = ∈ ≥{ }
( ){ }
1 1 1 2 2
32
2 1 2 1 2 2 1 1 2 2 1 1 1 2 2
1 2
3
en fixant 0
, : il existe , 0 tel que = +
et
e
t z b a x a
x
z z R x x z c x c x z b a x a x
x a
=
Γ = ∈ ≥ = − −
Γ = Γ
= − − −
Γ∪
Γ( )
{ }
1 2
2 1,0 1 2
Pour résoudre le problème dual,formulé en termes des variables et :
Max Inf ,
il suffit de déterminer la valeur de 0 correspondant au
négatif de la pente de la droitetangente
z z
z z
z zλ
λ
λ λ
∈Γ≥
+
≥
à ayant le plus grand ordonné à l'origine.
Γ1z
2z
λ−
Valeur optimaledu dual
Valeur optimaledu primal
Il y a donc saut de dualité.
( )
1 1 2 2 3 3
1 1 2 2 3 3
32
1 1 2 1 2 2 1 1 2 2
1 1 2 2 3 3
1 2 3
3
Min Sujet à 0
0, 0, 0 ou 1.Associons à ce pen fixan
roblème les ensembles suivants:t 1
, : il existe , 0 tel que = + +
c x c x c x
a x a x
x
z z R x x
a x b b a
z c x
x a x a x
x x
x
x
c c
+ +
+ + ≥ ≡ − − − ≤
≥ ≥ =
=
Γ = ∈ ≥{ }
( ){ }
1 1 1 2 2
32
2 1 2 1 2 2 1 1 2 2 1 1 1 2 2
1 2
3
en fixant 0
, : il existe , 0 tel que = +
et
e
t z b a x a
x
z z R x x z c x c x z b a x a x
x a
=
Γ = ∈ ≥ = − −
Γ = Γ
= − − −
Γ∪
••
Γ
( )
( ) ( )( )
( )
( )( )
11
1 2
2
1
1 2
La fonction de perturbation est définie
Min
Sujet à
et en termes de et z Min
Sujet à , .
Donc dans cet exemple, est indiquée en vert.
v y
v y f x
f x y
x R
z
v y z
z y
z z
v y
=
≤
∈
=
≤
∈Γy
( )v y•
y
( )v y•
( )
1 1 2 2 3 3
1 1 2 2 3 3
32
1 1 2 1 2 2 1 1 2 2
1 1 2 2 3 3
1 2 3
3
Min Sujet à 0
0, 0, 0 ou 1.Associons à ce pen fixan
roblème les ensembles suivants:t 1
, : il existe , 0 tel que = + +
c x c x c x
a x a x
x
z z R x x
a x b b a
z c x
x a x a x
x x
x
x
c c
+ +
+ + ≥ ≡ − − − ≤
≥ ≥ =
=
Γ = ∈ ≥{ }
( ){ }
1 1 1 2 2
32
2 1 2 1 2 2 1 1 2 2 1 1 1 2 2
1 2
3
en fixant 0
, : il existe , 0 tel que = +
et
e
t z b a x a
x
z z R x x z c x c x z b a x a x
x a
=
Γ = ∈ ≥ = − −
Γ = Γ
= − − −
Γ∪
Γ
La fonction de perturbation n'est pas convexe. Ceci vient du fait que les hypothèses de convexité pour le problèmeprimal ne sont pas vérifiées.
( )
1 1 2 2 3 3
1 1 2 2 3 3
32
1 1 2 1 2 2 1 1 2 2
1 1 2 2 3 3
1 2 3
3
Min Sujet à 0
0, 0, 0 ou 1.Associons à ce pen fixan
roblème les ensembles suivants:t 1
, : il existe , 0 tel que = + +
c x c x c x
a x a x
x
z z R x x
a x b b a
z c x
x a x a x
x x
x
x
c c
+ +
+ + ≥ ≡ − − − ≤
≥ ≥ =
=
Γ = ∈ ≥{ }
( ){ }
1 1 1 2 2
32
2 1 2 1 2 2 1 1 2 2 1 1 1 2 2
1 2
3
en fixant 0
, : il existe , 0 tel que = +
et
e
t z b a x a
x
z z R x x z c x c x z b a x a x
x a
=
Γ = ∈ ≥ = − −
Γ = Γ
= − − −
Γ∪
Recommended