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

=

Γ = ∈ ≥ = − −

Γ = Γ

= − − −

Γ∪