Embed Size (px)
Citation preview
Conditions d’optimalité
en
optimisation avec contraintes
Multiplicateurs de Lagrange
( )( )
1 1
Considérons le problème de programmation mathématique suivantMin
Sujet à 0 1, , (5.1)
où et les fonctions : , : , 1, ,
lagrangi
.
Le associéen au problème (5.1) est obtenu c
i
n
i
f x
f x i m
x X
X R f X R f X R i m
= =
∈
⊂ → → =
…
…
( ) ( ) ( )1
omme suit en associantun à chaque fonction de contrainte :
, .
Sans faire d'hypothèse particulière sur ou sur les fonctions et , nous pouvons obte
multiplicateur de lagrang
n
e
i
i i
m
i i
i
i
f
L x f x f x
X f f
λ
λ λ=
= +∑
r des conditions suffisantes très générales pour qu'un point * soit une solution optimale globale du problème (5.1).
x
( )( )
( ) ( ) ( )1
Th
Con
éor
sidéro
ème 5.
ns le problème de programmation mathématique suivantMin
Sujet à 0 1, , (5.1)
Supposons que le lagrangien associé au problème (5.1)
,
possède un mi
1:
ni
i
m
i i
i
f x
f x i m
x X
L x f x f xλ λ=
= =
∈
= +∑
…
( )
*
* * *
mum global sur lorsque le vecteur de multiplicateurs
. Si =0 pour tout 1, , , alors e
Pre
st une solution optimale
globale de (5.1).
La preuve se fait par contradiction en supposuve. ant
i
x X
f x i m xλ λ= = …
( )( ) ( )
*
*
que n'est pas unesolution optimale de (5.1). Alors il existe un tel que 0 pour tout
1, , , et .i
x
x f x
i m f x f x
=
= <…
( ) ( ) ( )
( )
1*
* *
Supposons que le lagrangien associé au problème (5.1)
,
possède un minimum global sur lorsque le vecteur de multiplicateurs
. Si =0 pour tout 1, , , al
Théorème 5
ors
. :
1m
i i
i
i
L x f x f x
x X
f x i m x
λ λ
λ λ
=
= +
= =
∑
…
( )
*
*
est une solution optimale
globale de (5.1).
La preuve se fait par contradiction en supposant que n'est pas unesolution optimale de (5.1). Alors il existe un tel que =0 pour tPreuv
oute.
1, , ,i
x
x f x
i m= … ( ) ( )
( ) ( )
( ) ( ) ( ) ( )
*
*
1 1
* *
1 1* *
et .
Par conséquent, pour tout
0
et ainsi
.
En prenant la relation précédente contredit le fait que est un minimum global du lagrangien
m m
i i i i
i i
m m
i i i i
i i
f x f x
f x f x
f x f x f x f x
x
λ
λ λ
λ λ
λ λ
= =
= =
<
= =
+ < +
=
∑ ∑
∑ ∑
* sur lorsque . X λ λ= �
( )( )
( ) ( ) ( )
( ) ( )
( )
2 2
1
2 2
,
,
Min , 2
Sujet à , 0.
, , 2
convexe en , .Donc minimum atteint lorsque , , 0
2 0 2, ,
4
Exempl :
0 4
e
x y
x y
f x y x y
f x y x y b
L x y x y x y b
L x y L x y
x xL x y
y y
λ λ
λ
λ λλ
λ λ
= +
= + − =
= + + + −
∇ =
+ = − ∇ = = ⇔ + = −
2
2 3 03
2Donc 2
34
23
x y
bx y b y y b y b y
bx y
bxλ
⇔ =
+ − = + − = − = ⇔ =
= =
= − = −
( )( )
( ) ( ) ( )1
Considérons maintenant le problème de programmation mathématique suivantMin
Sujet à 0 1, , (5.2)
Supposons que le lagrangien associé au problème (5Th .2éorè )
,
p
me
s
5. :
o
2
s
i
m
i i
i
f x
f x i m
x X
L x f x f xλ λ=
≤ =
∈
= +∑
…
( ) ( )
*
* * * * * *
ède un minimum global sur lorsque le vecteur de multiplicateurs
. Si 0 , 0
Preuv
et 0 pour tout 1, , , alors est
une solution optimale glo
e
b
.
ale de (5.2).
La preuve se fait
i ii i
x X
f x f x i m xλ λ λ λ= ≤ ≥ = = …
( )( ) ( )
*
*
par contradiction en supposant que n'est pas unesolution optimale de (5.2). Alors il existe un tel que 0 pour tout
1, , , et .i
x
x f x
i m f x f x
≤
= <…
( ) ( ) ( )
( ) ( )
1*
* * * * *
Supposons que le lagrangien associé au problème (5.2)
,
possède un minimum global sur lorsque le vecteur de multiplicateurs
. Si 0 , 0 et 0 po
Théorème 5.2:
ur t
m
i i
i
i ii i
L x f x f x
x X
f x f x
λ λ
λ λ λ λ
=
= +
= ≤ ≥ =
∑
( )
*
*
out 1, , , alors est
une solution optimale globale de (5.2).
La preuve se fait par contradiction en supposant que n'est pas unesolution optimale de (5.2). Alors il existe un P
tel que reuve.
i
i m x
x
x f x
= …
( ) ( )
( ) ( )
( ) ( ) ( ) ( )
*
*
* *
1 1
* * * *
1 1*
0 pour tout
1, , , et .
Par conséquent, pour 0
0 et 0
et ainsi
.
La relation précédente contredit le fait que est un mini
m m
i i ii
i i
m m
i ii i
i i
i m f x f x
f x f x
f x f x f x f x
x
λ λ
λ λ
λ λ
∗
= =
= =
≤
= <
= ≥
≤ =
+ < +
∑ ∑
∑ ∑
…
*
mum global du lagrangien sur lorsque .X λ λ= �
( )( )
( ) ( )
( ) ( )
( )
2
1
2
Min
Sujet à 2 5 0.
, 2 5
convexe en .Donc minimum atteint lorsque , 0
, 2
Exemp
2 0
52 5 2 5 0
2
5Don
le:
c2
x
x
f x x
f x x
L x x x
L x L x
L x x x
x
x
λ λ
λ
λ λ λ
λ λ
λ
=
= + ≤
= + +
∇ =
∇ = + = ⇔ = −
+ = − + = ⇔ =
= − = −
( )
50
22 5 0 2 5 0x x
λ
λ
= ≥
+ = ⇒ + =
Conditions d’optimalite de
Karush-Kuhn-Tucker (KKT) de premier ordre
Pour obtenir des conditions plus facilement vérifiables, il faut poser des hypothèses sur et sur les fonctions et .iX f f
( )( )
( ) ( ) ( )1
Si est convexe, si et sont différentiables et convexes dans le problème (5.2)
Min
Sujet à 0 1, , (5.2)
alors le lagrangien ,
est aussi une fonction convexe sur si
i
i
m
i i
i
X f f
f x
f x i m
x X
L x f x f x
X
λ λ=
≤ =
∈
= +∑
…
( ) ( )
( ) ( )
i
1
0 puisque 0 et convexe convexe
somme de fonctions convexes.
i i i
m
i i
i
f x f x
f x f x
λ
λ λ
λ=
≥
≥ ⇒
+∑
( ) ( ) ( )1
*
Si et sont differentiables et convexes et si 0, alors le lagrangien
, est une fonction différentiable et convexe en ,
et il s'ensuit qu'il possède un minimum global en sur
im
i i
i
f f
L x f x f x x
x X
λ
λ λ=
≥
= +∑
( ) ( ) ( )
( ) ( ) ( )
*
* *
1
1*
lorsque si
, 0.
Alors le Théorème 5.2 peut s'écrire: Supposons que
le lagrangien associé au problème (5.2)
,
possède un
Théorème
minimum global sur
o
.
l
5 2:
m
x ii
i
m
i i
i
L x f x f x
L x f x f x
x X
λ λ
λ λ
λ λ
=
=
=
∇ = ∇ + ∇ =
= +
∑
∑
( ) ( )
*
* * * *
*
rsque le vecteur de multiplicateur .
Si 0 , 0 et 0
pour tout 1, , , alors est une solution optimale globale de (5.2).
i ii if x f x
i m
x
λ
λ λ≤ ≥ =
= …
( ) ( ) ( )
( )( )
*
* * * * *
1* *
*
*
S'il existe un tel que
, 0
0 1, ,
0 1, ,
0 1, ,
m
x ii
i
i i
i
i
L x f x f x
f x i n
f x i n
i n
λ
λ λ
λ
λ
=
∇ = ∇ + ∇ =
= =
≤ =
≥ =
∑…
…
…
K-K-T
2 2
1 1 2 2 1 2
2 2 2 2
1 2 1 2 1
1 2 1 2 2
Exemple. Min 2 2 10 10
Sujet à 5 5 03 6 3 6 0
x x x x x x
x x x xx x x x
λλ
+ + − −
+ ≤ ⇔ + − ≤+ ≤ ⇔ + − ≤
( ) ( ) ( )
( )( )
*
* * * * *
1* *
*
*
S'il existe un tel que
, 0
0 1, ,
0 1, ,
0 1, ,
m
x ii
i
i i
i
i
L x f x f x
f x i n
f x i n
i n
λ
λ λ
λ
λ
=
∇ = ∇ + ∇ =
= =
≤ =
≥ =
∑…
…
…
1 2 11 2
1 2 2
4 2 10 2 3 02 2 10 2 1x x xx x x
λ λ+ − + + =+ −
( )( )
2 2
1 1 2
2 1 2
5 03 6 0x x
x x
λλ
+ − =
+ − =
2 2
1 2
1 2
5 03 6 0x xx x
+ − ≤+ − ≤
1 2, 0λ λ ≥
2 2
1 1 2 2 1 22 2 2 2
1 2 1 2 1
1 2 1 2 2
Exemple. Min 2 2 10 10 Sujet à 5 5 0
3 6 3 6 0
x x x x x xx x x xx x x x
λλ
+ + − −+ ≤ ⇔ + − ≤+ ≤ ⇔ + − ≤
1 2 11 2
1 2 2
4 2 10 2 3 02 2 10 2 1x x xx x x
λ λ+ − + + =+ −
( )( )
2 2
1 1 2
2 1 2
5 03 6 0x x
x x
λλ
+ − =
+ − =
2 2
1 2
1 2
5 03 6 0x xx x
+ − ≤+ − ≤
1 2, 0λ λ ≥
1 2 1 2
Nous pouvons faire différentes hypothèses sur quelle contrainte est active dans le but d'identifier des valeurs de , , , satisfaisant les conditions KKT.
x x λ λ
2 2
1 2
1 2 2
Supposons que la première est active et que la seconde ne l'est pas:
5 03 6 0 0.x xx x λ
+ − =+ − < ⇒ =
2 2
1 1 2 2 1 22 2 2 2
1 2 1 2 1
1 2 1 2 2
Exemple. Min 2 2 10 10 Sujet à 5 5 0
3 6 3 6 0
x x x x x xx x x xx x x x
λλ
+ + − −+ ≤ ⇔ + − ≤+ ≤ ⇔ + − ≤
1 2 11 2
1 2 2
4 2 10 2 3 02 2 10 2 1x x xx x x
λ λ+ − + + =+ −
( )( )
2 2
1 1 2
2 1 2
5 03 6 0x x
x x
λλ
+ − =
+ − =
2 2
1 2
1 2
5 03 6 0x xx x
+ − ≤+ − ≤
1 2, 0λ λ ≥
2 2
1 2
1 2 2
Supposons que la première est active et que la seconde ne l'est pas:
5 03 6 0 0.x xx x λ
+ − =+ − < ⇒ =
1 2 1 1
1 2 1 22 2
1 2
Nous retrouvons alors le systèmeavec 3 équations et 3 inconnus suivant:
4 2 10 2 02 2 10 2 0
5
x x xx x x
x x
λλ
+ − + =+ − + =
+ =
1 2 1
Nous pouvons vérifier que 1, 2, 1satisfont le système précédent.
x x λ= = =1 2 1 2
Donc 1, 2, 1, 0
satisfont les conditions KKT.
x x λ λ= = = =
Conditions K-K-T suffisantes
En utilisant le Théorème 5.2 nous venons de démontrer que les conditionsK-K-T sont suffisantes sous les hypothèses supplémentaires que estconvexe et que les fonctions et sont convexes sur .i
X
f f X
Nous pouvons démontrer ce résultat en utilisant plutôt l'inégalité du gradient.
Supposons que est convexe et que les fonctions et sont différentiables et convexes.T
Si les conditihéo
orème 5.3:
niX f f
( )
*
*
*
s de K-K-T sont vérifiées à , alors est un minimum global du problème 5.2 .
. Le lagrangien étant convexe si 0 (démontrer précédemment), alors par l'inégalité du gradient il s'ensuPreuve
it que po
x
x
λ ≥
( ) ( ) ( ) ( ) ( ) ( ) ( )T
* * * * * * * *
1 1 1
ur tout m m m
i i ii i i
i i i
x X
f x f x f x f x f x f x x xλ λ λ= = =
∈
+ ≥ + + ∇ + ∇ −
∑ ∑ ∑
( )
*
*
Supposons que est convexe et que les fonctions et sont différentiables et convexes. Si les conditions de K-K-T sont vérifiées à , alors est un minimum glob
Th
al
éorème 5.3
du problè
:
me 5.2 .
iX f f
x
x
( ) ( ) ( ) ( ) ( ) ( )
*
T
* * * * * * *
1 1 1
Preuve. Le lagrangien étant convexe si 0 (démontrer précédemment), alors par l'inégalité du gradient il s'ensuit que pour tout
m m m
i i ii i i
i i i
x X
f x f x f x f x f x f x
λ
λ λ λ= = =
≥∈
+ ≥ + + ∇ + ∇
∑ ∑ ∑
������� �
( )*
0 0
x x−
������������
( ) ( ) ( )
( )( )
* * * * *
1* *
*
*
*
, 0
0 1, ,
0 1, ,
0 1
K-K-T
, ,
m
x ii
i
i i
i
i
L x f x f x
f x i n
f x i n
i n
x X
λ λ
λ
λ
=
∇ = ∇ + ∇ =
= =
≤ =
≥ =
∈
∑…
…
…
( ) ( ) ( )
( ) ( )
* *
1
*
Alors, pour tout
0
et
.
m
ii
i
x X
f x f x f x
f x f x
λ=
∈
− ≤ ≤
≤
∑
�
Conditions K-K-T nécessaires
L'analyse de la nécessité des conditions K-K-T est plus complexe et requiertl'introduction de notions et de résultats préliminaires reliés aux théorème
Définitio
sd'alternatives.
L' hyperpla spécns.
n ifié
( ) { }( )
[ ] { }[ ] { }
T
T
T
par le point et le scalaire est l'ensemble de
, : .
Les (fermés) associés a l'hyperplan , sont les ensembles
suivants de :
demis espace
Not
s
, :
, :
e.
.
I
n n
n
n
n
n
a R R
H a x R a x
H a
R
H a x R a x
H a x R a x
β
β β
β
β β
β β
+
−
∈
= ∈ =
= ∈ ≥
= ∈ ≤
l est facile de vérifier que tous ces ensembles sont convexes.
( ),H a β[ ],H a β+
[ ],H a β−
11 1 2 2 2 1
2 2
aa x a x x x
a a
ββ+ = ⇔ = − +
( )[ ]( )[ ]( )
T
T
L'hyperlan , sépare deux ensembles non vides et si
pour tout i.e.,
Hyperplan d
,
po
Définitio
ur tout i.e., , .
La est si les in
e séparation.
séparation égstric e
.
t
n
al
H a X Y
a x x X X H a
a y y Y Y H a
β
β β
β β
+
−
≥ ∈ ⊂
≤ ∈ ⊂
ités dans les relations précédentessont strictes.
X
Y
( )11,H a β
( )22,H a β
( )( )
11
22
, hyperplan de séparation
, hyperplan de séparation stricte
H a
H a
β
β
( )
( )
[ ] [ ]( )
support Étant donné un ensemble non vide l'hyperplan ,
est un de si, et
, ou ,
où dénote la de l'ense
Définition.
mble
fermet .ure
nX R H a
X
H a X
X H a X H a
X X
β
β
β β+ −
⊂
≠ Φ
⊂ ⊂
∩
X
( ), supportH a β
( )( )( )
( )( ) ( )( )( )( ) ( )( )
T T
T T T
T T T
T T T
Soient les vecteurs , , . Si , alors pour tout0,1 ,
1 .
1 1 .
1
Preuve
Théorème 5
1
.4:
.
.
nx y a R a y a x
a y a x y a x
a x y a x x a x
a x y a y y a y
θ
θ θ
θ θ θ θ
θ θ θ θ
∈ <
∈
< + − <
+ − < + − =
+ − > + − = �
0
0
( ) Si est un ensemble convexe non vide et si , alors il existe un hyperplan qui sépare (stricteme
Théorème 5.5
nt) et .Preuve. Il existe un point tel que
mi
: Théorème de séparatio
n
n nX R
y X
X y
x X
x y
⊂
∉
∈
− =
( )
( ) [ ]
( )( )
T
0
0 0
où dénote la norme euclédienne de .
Il est facile de vérifier que est un ensemble convexe, et par conséquent le
segment de droite , pour tout . Donc pour tout 0,1
1
x Xx y
z z z z
X
x x X x X
x y x x
θ
θ θ
∈−
=
ℑ ⊂ ∈ ∈
− ≤ + −
[ ]
( ) ( ) ( )( )( ) ( )( )( )( ) ( ) ( ) ( )( ) ( ) ( )( )( ) ( ) ( ) ( ) ( ) ( )
( ) ( )
TT0 0 0 0
TT0 0 0 0 0 0
T T T0 0 0 0 0 0
T2 0 0
.
Ainsi pour tout 0,1
1 1
2
y
x y x y x x y x x y
x y x y x y x x x y x x
x y x y x y x y x x x y
x x x x
θ
θ θ θ θ
θ θ
θ
θ
−
∈
− − ≤ + − − + − −
− − ≤ − + − − + −
− − ≤ − − + − − +
− −
•
XX y
0x
•
Nous allons construire un hyperplan de séparation stricte
x•
( ) ( ) 2α β α β αα αβ ββ+ + = + +
[ ]
( ) ( ) ( )( )( ) ( )( )( )( ) ( ) ( ) ( )( ) ( ) ( )( )( ) ( ) ( ) ( ) ( ) ( )
( ) ( )[ ]
( ) ( ) ( ) ( )
TT0 0 0 0
TT0 0 0 0 0 0
T T T0 0 0 0 0 0
T2 0 0
T T0 0 2 0 0
Ainsi pour tout 0,1
1 1
2
.
Par consequent pour tout 0,1
2 0.
Mais alors ceci i
x y x y x x y x x y
x y x y x y x x x y x x
x y x y x y x y x x x y
x x x x
x x x y x x x x
θ
θ θ θ θ
θ θ
θ
θ
θ
θ θ
∈
− − ≤ + − − + − −
− − ≤ − + − − + −
− − ≤ − − + − − +
− −
∈
− − + − − ≥
( ) ( )( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
T0 0
T0 0
T T0 0 2 0 0
T T0 0 2 0 0
T T0 0 2 0 0
mplique que 0. En effet si
0, alors pour >0 suffisemment petit
2
2
et alors nous aurions que
2 0.
x x x y
x x x y
x x x y x x x x
x x x y x x x x
x x x y x x x x
θ
θ θ
θ θ
θ θ
− − ≥
− − <
− − > − −
− − − > − −
− − + − − <
�
� �
� �
� �
( ) ( )( ) ( ) ( )
( ) ( )( ) ( ) ( )
( )
T0 0
0T 0 T 0
2 T0 0 0
T 0 0T 0
0
0
Nous avons donc que 0 ou encore
. 5.3
Puisque , 0, ou encore
. 5.4
Alors en appliquant le Théorème 5.4 avec les vecteurs ,
, ,
x x x y
x x y x x y
y X x y x y x y
y x y x x y
x y
x y
− − ≥
− ≤ −
∉ − = − − >
− < −
−
( )
( ) ( )( ) ( ) ( )( )
( ) ( ) ( ) ( ) ( )
TT 0 0 0 0T 0
TT 0 0 0 0T 0 T 0
et utilisant la relation 5.4
1 .
En utilisant maintenant la relation 5.3 ,
1.
2
y x y x y x y x x y
y x y x y x y x x y x x y
θ θ− < + − − < −
− < + − < − ≤ −
( )( )( )
T T
T T T
Si , alors pour tout0,1 ,
1 .
a y a x
a y a x y a x
θ
θ θ
<
∈
< + − <
( ) ( )( ) ( ) ( )
( ) ( )( ) ( ) ( )
( )
T0 0
0T 0 T 0
2 T0 0 0
T 0 0T 0
0
0
Nous avons donc que 0 ou encore
. 5.3
Puisque , 0, ou encore
. 5.4
Alors en appliquant le Théorème 5.4 avec les vecteurs ,
1, , et avec = , et u
2
x x x y
x x y x x y
y X x y x y x y
y x y x x y
x y
x y θ
− − ≥
− ≤ −
∉ − = − − >
− < −
−
( )
( ) ( ) ( ) ( )( )
( ) ( ) ( ) ( ) ( )
TT 0 0 0 0T 0
TT 0 0 0 0T 0 T 0
tilisant la relation 5.4
1.
2En utilisant maintenant la relation 5.3 ,
1.
2
y x y x y x y x x y
y x y x y x y x x y x x y
− < + − < −
− < + − < − ≤ −
( )( )( )
T T
T T T
Si , alors pour tout0,1 ,
1 .
a y a x
a y a x y a x
θ
θ θ
<
∈
< + − <
( )
( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
TT 0 0 0 0T 0 T 0
TT 0 0 0 T 0
En utilisant maintenant la relation 5.3 ,
1.
2Par conséquent nous avons que
1.
2Puisque cette relation est valable pour tout , il s'ensuit
que l'hype
y x y x y x y x x y x x y
y x y x y x y x x y
x X
− < + − < − ≤ −
− < + − < −
∈
( ) ( )
( ) ( )
0
T0 0
rplan , où et
1= sépare (strictement) et .
2
H a a x y
x y x y X y
β
β
= −
+ − �
yX
y
X
Dans le Théorème 5.5, la convexité de est une condition
suffisante pour assurer l'existence d'un hyperplan le séparant
(strictement) de .
X
y X∉
1
( ) Étant donné les vecteurs
, , et , une condition suffisante pour que
s'exprime comme une combinaison linéaire non néga
Théorème 5.6: Théorème de
tive des
(i.e., une condition
Farka
suffisa
sn m
j
a a b R b
a
∈…
11 1
T
T
nte pour qu'il existe des scalaires non
négatifs , , tels que ) est que tout
tel que 0 pour tout 1, , , vérifie
nécessairement la relation 0.
Il faut démontrer qPreuve.
nn n
m j
x x b a x a x
y R y a j n
y b
= + +
∈ ≥ =
≥
… …
…
1T1
1T
ue
pour tout , , , 0 tels que
si 0 pour tout 1, , ,
alors nécessairement 0
m
nj
nn
y Rx x
y a j nb a x a x
y b
∈∃ ≥
≥ = ⇒ = + +
≥
……
…
1T1
1T
Il faut démontrer que
pour tout , , , 0 tels que
si 0 pour tout 1, , ,
alors nécessairement 0
Nous allons plutôt d
Preuve
émontrer la contr
.
ap
m
nj
nn
y Rx x
y a j nb a x a x
y b
∈∃ ≥
≥ = ⇒ = + +
≥
……
…
1T1
1T
1
11
osé de l'implication:
pour tout , , , 0 tels que
si 0 pour tout 1, , ,
alors nécessairement 0
c'est-à-dire
, , 0 tels que
m
nj
nn
n
nn
y Rx x
y a j nb a x a x
y b
x x
b a x a x
∈∃ ≥
¬ ≥ = ⇐ ¬ = + +
≥
∃ ≥
= + +
……
…
…
…
T
T
, tel que
0 pour tout 1, , ,
et 0
m
j
y R
y a j n
y b
∃ ∈
⇒ ≥ =
<
…
{ }
1 T1
1 T
11 1
Pour démontrer que
, tel que, , 0 tels que
0 pour tout 1, , ,
et 0
considérons l'ensemble
: , , 0 tel que .
Il est fac
m
n j
nn
m nn n
y Rx x
y a j nb a x a x
y b
Z z R x x z a x a x
∃ ∈∃ ≥
⇒ ≥ = = + +
<
= ∈ ∃ ≥ = + +
……
…
… …
( )
( ) ( ) ( )
1 1
1 1 1 1 2 1 2 2
1 2 1 1 2 1 21 1
ile de démontrer que est convexe. Il est aussi possible
de démontrer que est un ensemble fermé i.e. .
1 1 1
et alors
n n
n n
nn n
Z
Z Z Z
z a x a x z a x a x
z z a x x a x xθ θ θ θ θ θ
θ
=
= + + = + +
+ − = + − + + + −
… …
…
( )1 21z z Zθ+ − ∈
{ }
1 T1
1 T
11 1
Pour démontrer que
, tel que, , 0 tels que
0 pour tout 1, , ,
et 0
considérons l'ensemble
: , , 0 tel que .
Il est fac
m
n j
nn
m nn n
y Rx x
y a j nb a x a x
y b
Z z R x x z a x a x
∃ ∈∃ ≥
⇒ ≥ = = + +
<
= ∈ ∃ ≥ = + +
……
…
… …
( )ile de démontrer que est convexe. Il est aussi possible
de démontrer que est un ensemble fermé i.e. .
Puisque par hypothèse de la contraposé , alors
par le théorème 5.5 il existe un hyperpla
Z
Z Z Z
b Z Z
=
∉ =
T T
n ( , ) qui sépare
strictement et :
pour tout . (5.5)
H p
Z b
p b p z z Z
β
β< < ∈
{ }11 1
T T
: , , 0 tel que .
Puisque par hypothèse de la contraposé , alors
par le théorème 5.5 il existe un hyperplan ( , ) qui sépare
strictement et :
pour tout . (5.5)
O
m nn nZ z R x x z a x a x
b Z Z
H p
Z b
p b p z z Z
β
β
= ∈ ∃ ≥ = + +
∉ =
< < ∈
… …
T
T
T
r 0 ,ce qui implique que 0 et par conséquent que
.
Également, 0 pour tout . En effet, s'il existait un
tel que 0, alors puisque est un cône (i.e., si alors
pour
0
tout
Z
p z z Z z Z
p z Z z Z
z Z
p b
β
λ λ
∈ <
≥ ∈ ∈
< ∈
<
∈
�
�
( )T0), nous aurions que
contredisant (5.5).
p zλ
λ→∞
≥ → − ∞�
T
T
, tel que
0 pour tout 1, , ,
et 0
m
j
y R
y a j n
y b
∃ ∈
≥ =
<
…
T
T
T
Or 0 ,ce qui implique que 0 et par conséquent que
.
Également, 0 pour tout . En effet, s'il existait un
tel que 0, alors puisque est un cône (i.e., si alors
pou
0
r tout
p b
Z
p z z Z z Z
p z z Z
z Z
β
λ λ
∈ <
≥ ∈ ∈
< ∈
∈
<
�
�
( )
{ }1
T
11
T
0) nous aurions que
contredisant (5.5).
Comme il est facile de vérif
: , ,
ier que , 1, , ,
il s'ensuit que
Nou
0, 1,
s avons donc démo
0 tel que
ntré
.
la
,
m nn n
j
j
Z z R
p a j n
x x z
p z
a Z j n
a x a x
λλ
→∞
= ∈
≥ → − ∞
∃ ≥
∈
=
≥
+
=
+
= …
…
�
…
…
T T
contraposé puisque est
tel 0, 1,que et ., 0
m
j
p R
p a j n p b
∈
≥ = <… �T
T
, tel que
0 pour tout 1, , ,
et 0
m
j
y R
y a j n
y b
∃ ∈
≥ =
<
…
T
( ) Soit une matrice
. Exactement une des deux alternatives suivantes est vérifiée:
I Le système , 0 possède une solution
II Le système
Corollaire 5.7: Théorème d'alternatives
0,
n
A
m n
Ax b x x R
A y
×
= ≥ ∈
≥ T
T T T
0 possède une solution .
Il est facile de vérifier que les deux alternatives ne
peuvent tenir en même temps, car autrement la relation
suivante serait satisfaite:
0 0
une contra
Preuve.
mb y y R
b y x A y
< ∈
> = ≥
diction.
ième
T T
Dénotons par , 1, , , la colonne de .
Considérant l' alternative II, celle-ci est vérifée ou elle ne l'est pas.
Dans le cas où elle ne l'est pas, il s'ensuit que le système
0, 0 ne
ja j n j A
A y b y
• =
≥ <
…
T T
T T
possède pas de solution ;
i.e., le système 0, 1, , , 0 ne possède pas
de solution . Ainsi pour tout ,
si 0, 1, , , alors nécessairement 0.
Donc par le Théorème 5.6,
m
j
m m
j
y R
a y j n b y
y R y R
a y j n b y
•
•
∈
≥ = <
∈ ∈
≥ = ≥
…
…
1 1
il existe un vecteur , 0 tel
que , et l'alternative I tient.
n
n n
x R x
Ax a x a x b• •
∈ ≥
= + + =… �
T T
I Le système , 0 possède une solution
II Le système 0, 0 possède une solution .
n
m
Ax b x x R
A y b y y R
= ≥ ∈
≥ < ∈
Illustration du cas où le système , 0 possède une solution.Ax b x= ≥
1a•
2a•
b
T1 0a y• ≥
T2 0a y• ≥
etT 0b y <
T TLe système 0, 0ne possède pas de solution
A y b y≥ <
1 1a x•
2 2a x•
T cosc d c d θ=
Illustration du cas où le système , 0 ne possède pas de solution.Ax b x= ≥
1a•
2a•
b
T1 0a y• ≥
T2 0a y• ≥
etT 0b y <
b
T 0b y <T TLe système 0, 0
possède une solution A y b y≥ <
( ) ( ) ( )
( ) ( ) ( )
1*
*
* * * * *
1
Le lagrangien , étant une fonction différentiable
et convexe en , il s'ensuit qu'il possède un minimum global en sur lorsque 0 si
, 0.
Alors le Théor
m
i i
i
m
x ii
i
L x f x f x
x x X
L x f x f x
λ λ
λ λ
λ λ
=
=
= +
= ≥
∇ = ∇ + ∇ =
∑
∑
( ) ( ) ( )
( )
1*
*
* *
ème 5.2 peut s'écrire: Supposons que
le lagrangien associé au problème (5.2)
,
possède un minimum global sur lorsque le vect
Théorème
eur de multiplicateur .
Si
5.2:
0 , 0
m
i i
i
i i
L x f x f x
x X
f x
λ λ
λ
λ
=
= +
≤ ≥
∑
( )* *
*
et 0
pour tout 1, , , alors est une solution optimale globale de (5.2).
i if x
i m
x
λ =
= …
( ) ( ) ( )
( )( )
*
* * * * *
1* *
*
*
*
S'il existe un tel que
, 0
0 1, ,
0 1, ,
0 1, ,
m
x ii
i
i i
i
i
L x f x f x
f x i n
f x i n
i n
x X
λ
λ λ
λ
λ
=
∇ = ∇ + ∇ =
= =
≤ =
≥ =
∈
∑…
…
…
K-K-T
( )( )
Considérons maintenant le problème de programmation mathématique suivantMin
Sujet à 0 1, , (5.2)i
f x
f x i m
x X
≤ =
∈
…
sous les hypothèses supplémentaires que estconvexe et que les fonctions et sont convexes sur .i
X
f f X
( ) ( ) ( )
( )( )
* * * * *
1* *
*
*
*
, 0
0 1, ,
0 1, ,
0 1
K-K-T
, ,
m
x ii
i
i i
i
i
L x f x f x
f x i n
f x i n
i n
x X
λ λ
λ
λ
=
∇ = ∇ + ∇ =
= =
≤ =
≥ =
∈
∑…
…
…
( )( )
Min
Sujet à 0 1, , (5.2)i
f x
f x i m
x X
≤ =
∈
…
convexité ⇑ conditions...⇓
1
( ) Étant donné les vecteurs
, , et , une condition suffisante pour que
s'exprime comme une combinaison linéaire non néga
Théorème 5.6: Théorème de
tive des
(i.e., une condition
Farka
suffisa
sn m
j
a a b R b
a
∈…
11 1
T
T
nte pour qu'il existe des scalaires non
négatifs , , tels que ) est que tout
tel que 0 pour tout 1, , , vérifie
nécessairement la relation 0.
Il faut démontrer qPreuve.
nn n
m j
x x b a x a x
y R y a j m
y b
= + +
∈ ≥ =
≥
… …
…
1T1
1T
ue
pour tout , , , 0 tels que
si 0 pour tout 1, , ,
alors nécessairement 0
m
nj
nn
y Rx x
y a j mb a x a x
y b
∈∃ ≥
≥ = ⇒ = + +
≥
……
…
T
( ) Soit une matrice
. Exactement une des deux alternatives suivantes est vérifiée:
I Le système , 0 possède une solution
II Le système
Corollaire 5.7: Théorème d'alternatives
0,
n
A
m n
Ax b x x R
A y
×
= ≥ ∈
≥ T
T T T
0 possède une solution .
Il est facile de vérifier que les deux alternatives ne
peuvent tenir en même temps, car autrement la relation
suivante serait satisfaite:
0 0
une contra
Preuve.
mb y y R
b y x A y
< ∈
> = ≥
diction.
( )( )
* *
Revenons à l'analyse de la nécessité des conditions K-K-T en exploitant leCorollaire 5.7.
Supposons que , 0, 1, , , est une solution locale du
pr
Notation
oblème 5.2 .
Dénotons l'ensem: ble con des
ix X f x i m∈ ≤ = …
( ) ( ){ } { } { }
( ) ( ) ( )
( )
* *1
T* *
T*
: 0 , , 1, , .
: Supposons que nous pouvons démontrer qu'il n'existe pas d
traintes active
e vecteuHYPOTHÈS
r tel que
0 5
E À VÉRIFI
s
.
ER
6
0
i k
n
i
A x i f x i i m
d R
f x d i A x
f x d
= = = ⊂
∈
∇ ≤ ∈
∇ <
… …
( )( )
Min
Sujet à 0 1, , (5.2)i
f x
f x i m
x X
≤ =
∈
…
( ) ( )( )
( ) ( ) ( )
T* *
T*
T T* * *
1
: Supposons que nous pouvons démontrer qu'il n'existe pas de vecteur tel queHYPOTHÈ
0
0.
Ainsi le système
,
SE À VÉRIFIER
, 0, 0
ne possède pas de solution.
n
i
i ik
d R
f x d i A x
f x d
f x f x d f x d
∈
∇ ≤ ∈
∇ <
∇ ∇ ≤ ∇ <
…
( ) ( ) ( ){ }
( ) ( ) ( ){ }
T T* * *
1
* * * * * * *
1 1
Appliquons maintenant le Corollaire 5.7:
II : , , 0, 0 n'as pas de solution
implique que
I: , , = , = , , 0 possède une solution
n
i ik
i i i ik k
f x f x d f x d d R
f x f x f xλ λ λ λ
− ∇ ∇ ≥ ∇ < ∈
− ∇ ∇ ∇ ≥
…
� �… …
T
( ) Soit une matrice
. Exactement une des deux alternatives suivantes est vérifiée:
I Le système , 0 possède une solution
II Le système
Corollaire 5.7: Théorème d'alternatives
0,
n
A
m n
Ax b x x R
A y
×
= ≥ ∈
≥ T 0 possède une solution .mb y y R< ∈
( )
( )
T*
1
T*
0
0
i
ik
f x d
f x d
∇ ≤
∇ ≤
( )
( )
T*
1
T*
0i
ik
f x
d
f x
∇
≤ ∇
( ) ( ) ( ){ }
( ) ( ) ( ){ }
T T* * *
1
* * * * * * *
1 1
Appliquons maintenant le Corollaire 5.7:
II : , , 0, 0 n'as pas de solution
implique que
I: , , = , = , , 0 possède une solution .
Ceci s'é
n
i ik
i i i ik k
f x f x d f x d d R
f x f x f xλ λ λ λ
− ∇ ∇ ≥ ∇ < ∈
− ∇ ∇ ∇ ≥
…
� �… …
( )( ) ( )
( )
( )( )
( ) ( )
* * * * * *
1*
* *
* *
*
* * *
crit également sous la forme
I: = , = , , 0 possède une solution
Posons 0 pour tout . Alors
0
0 pour tout .
i i i ik
i A x
i
i i
i A x
i i
f x f x
i A x
f x
f x i A x
λ λ λ λ
λ
λ
λ
∈
∉
− ∇ ∇ ≥
= ∉
∇ =
= ∉
∑
∑
� …
( )( ) ( )
( )
( )( )
( ) ( )
* * * * * *
1*
* *
* *
*
* * *
Ceci s'écrit également sous la forme
I: = , = , , 0 possède une solution
Posons 0 pour tout . Alors
0
0 pour tout .
Par conséq
i i i ik
i A x
i
i i
i A x
i i
f x f x
i A x
f x
f x i A x
λ λ λ λ
λ
λ
λ
∈
∉
− ∇ ∇ ≥
= ∉
∇ =
= ∉
∑
∑
� …
( ) ( )
( )( )
* * *
1* *
*
*
uent
0
0 1, ,
0 1, ,
0 1
nous retrouvons les condit
, ,
ions K-K-Tm
ii
i
i i
i
i
f x f x
f x i n
f x i n
i n
λ
λ
λ
=
∇ + ∇ =
= =
≤ =
≥ =
∑…
…
…
( ) ( ) ( )
( )
T* *
T*
*
Malheureusement
: Supposons que nous pouvons démontrer
qu'il n'existe pas de vecteur tel que
0 5.6
0
ne l'est pas nécessair
HYPOTHÈSE À V
ement pour to
ÉRIFI
ute solution locale d
ERn
i
d R
f x d i A x
f x d
x
∈
∇ ≤ ∈
∇ <
e tout
problème tel que l'illustre l'exemple suivant..
( )
( ) ( )
( )
( )
1 2 1
31 1 2 1 2
2 1 2 1
3 1 2 2
Min ,
Sujet à , 1 0
, 0
, 0.
L'ensemble des solutions réalisables de ce problème est
représenté par la region en-dessous de l
f x x x
f x x x x
f x x x
f x x x
= −
= − + ≤
= − ≤
= − ≤
( )1 1 2
1 2
a courbe de ,
au-dessus de l'axe des et à droite de l'axe des .
f x x
x x
1x
2x
( )
( ) ( )
( )
( )
1 2 1
31 1 2 1 2
2 1 2 1
3 1 2 2
Min ,
Sujet à , 1 0
, 0
, 0.
L'ensemble des solutions réalisables de ce problème est
représentée par la region en-dessous de
f x x x
f x x x x
f x x x
f x x x
= −
= − + ≤
= − ≤
= − ≤
( )1 1 2
1 2
la courbe de ,
au-dessus de l'axe des et à droite de l'axe des .
f x x
x x
[ ]
( ) { }
T*
*
Il est facile de vérifier que
1,0 est une solution
optimale globale de ce problème.
De plus = 1,3 .
x
A x
=
1x
2x
*x
•
( )
( ) ( )
( )
( )
1 2 1
31 1 2 1 2
2 1 2 1
3 1 2 2
Min ,
Sujet à , 1 0
, 0
, 0.
f x x x
f x x x x
f x x x
f x x x
= −
= − + ≤
= − ≤
= − ≤
1x
2x
*x
( ) [ ]
( ) ( ) ( ) [ ]
( ) [ ]
T*
T2 T*1 1 1
T*3
Or 1,0 ,
3 1 ,1 et 0,1
0, 1
f x
f x x f x
f x
∇ = −
∇ = − ∇ =
∇ = −
•
1x
2x
*x
( ) [ ]
( ) ( ) ( ) [ ]
( ) [ ]
T*
2 T*1 1 1
T*3
Or 1,0 ,
3 1 ,1 et 0,1
0, 1
f x
f x x f x
f x
∇ = −
∇ = − ∇ =
∇ = −
( )
( )
( )[ ]
T*1
T*1 2
T*3 2
On aimerait que le système
Mais le système
0
0
0
ne possède pas une solution 1,0 .
f x d d
f x d d
f x d d
d
∇ = − <
∇ = ≤
∇ = − ≤
=
•
1x
2x
*x
( )
( )
( )[ ]
T*1
T*1 2
T*3 2
Ainsi le système
0
0
0
possède une solution 1,0 .
f x d d
f x d d
f x d d
d
∇ = − <
∇ = ≤
∇ = − ≤
=
[ ]*Notons qu'au point la direction 1,0
pointe directement à l'extérieur du domaine réalisable.
x d =
d
Nous allons donc imposer certaines
restrictions sur les contraintes des
problèmes considérés pour éliminer
de telles situations.•
Restrictions sur les fonctions de contraintes de
Kuhn-Tucker
( )( ){ }
1Définition.
dénote le domaine réalisable du problème 5.2
: ,1 , tel que 0 .
Étant restrictions
sur les fonct
Nota
donné un point , , , satisfont le
tion:
ions de contrai
s
ntes
i
m
R
R x R i i m f x
x R f f
δ
δ
= ∈ ∃ ≤ ≤ =
∈
�
� �
� …
( ) ( )[ ] ( ) ( )
T
ˆau point si pour tout vecteur solution du
système 0, , il existe une fonction différentiableˆ: 0,1 tel que 0 et 0 , 0.
i
x d
f x d i A x
R x dα α α σ σ
∇ ≤ ∈
′→ = = >�
1x
2x
*x
d
( )( ){ }
1Définition.
dénote le domaine réalisable du problème 5.2
: ,1 , tel que 0 .
Étant restrictions
sur les fonct
Nota
donné un point , , , satisfont le
tion:
ions de contrai
s
ntes
i
m
R
R x R i i m f x
x R f f
δ
δ
= ∈ ∃ ≤ ≤ =
∈
�
� �
� …
( ) ( )[ ] ( ) ( )
T
ˆau point si pour tout vecteur solution du
système 0, , il existe une fonction différentiableˆ: 0,1 tel que 0 et 0 , 0.
i
x d
f x d i A x
R x dα α α σ σ
∇ ≤ ∈
′→ = = >�
1 2 3
*
Dans l'exemple précédent, les contraintes , ,ne satisfont pas les restrictions sur les fonctions de contraintes au point .
f f f
x Rδ∈ �
En effet, il n'existe pas de fonctiondifférentiable prenant ses valeursdans dont la pente à 0 est unmultiple positif de , puisque pointeà l'extérieur de .
R
d d
R
α�
�•
( ) ( )
1
T
restrictions
sur les fonctions de con
Étant donné un point , , , satisfont les ˆ au point si pour tout vecteur solution du
système
traintes
Déf
0, , il existe une f
init
nc
i
t
.
o
on m
i
x R f f
x d
f x d i A x
δ∈
∇ ≤ ∈
� …
[ ] ( ) ( )
ion différentiableˆ: 0,1 tel que 0 et
Interprétation géométriqu
0 , 0
e.
.R x dα α α σ σ′→ = = >�
( )1 0f x =( )2 0f x =
x
ˆx dσ+
( )( )( )
ˆ
0ˆ0
x d
x
d
α λ λσ
α
α σ
= +
=
′ =
( )T
1ˆ 0f x d∇ ≤
( )T
2ˆ 0f x d∇ ≤
1x
2x
•
( )1f x∇
( )2f x∇
( ) ( )
1
T
restrictions
sur les fonctions de con
Étant donné un point , , , satisfont les ˆ au point si pour tout vecteur solution du
système
traintes
Déf
0, , il existe une f
init
nc
i
t
.
o
on m
i
x R f f
x d
f x d i A x
δ∈
∇ ≤ ∈
� …
[ ] ( ) ( )
( )( )
T
ion différentiableˆ: 0,1 tel que 0 et 0 , 0.
Se référant à la notion de direction de descente, lorque 0,alors pour
un faible déplacement
Interprétati
0 dans la direction
on
, i
i
R x d
f x d
d f x d f
α α α σ σ
τ τ
′→ = = >
∇ <
> + <
�
( ) 0. Ainsi, ce déplacement nous garde dans le domaine réalisable par rapport à cette contrainte.Les restrictions sur les fonctions de contraintes prolongent en quelque sorte cette
propriété même si
i x =
∇ ( )T
0 puisque la fonction prend ses valeurs dans le
domaine réalisable .if x d
R
α=�
*
*1
( ) Soit une solutionoptimale locale du problème (5.2) où est ouvert. Supposons de plus quesi
Thé
, alors , , satisfont les restrictions sur
orème 5.8: Nécessité des conditions K-K-T
lm
x X
X
x R f fδ
∈
∈ � …
( ) ( )
( )
*
* * *1
* * *
1* *
*
es fonctions de contraintes au point . Alors il existe un vecteur de multiplicateurs
= , , 0 tel que
0
0 1, , .
Si est un point intérieur du domaine rPreuve.
m
m
i i
i
i i
x
f x f x
f x i m
x
λ λ λ
λ
λ=
≥
∇ + ∇ =
= =
∑
…
…
( )
( )( )
*
*
*
*
éalisable (i.e., 0
pour tout ), il suffit de prendre 0 pour tout 1, , . En effet dans ce
cas si prenait une valeur différente de 0, il suffirait de considérer la
direction qui
i
i
R f x
i i m
f x
d f x
λ
<
= =
∇
= −∇
�
…
( ) ( )( ) ( )
*
* *
* *
serait une direction de descente de à . Ainsi,
il existerait un >0 suffisemment petit pour que avec
, une contradiction.
f x
x d B x R
f x d f x
ετ τ
τ
+ ∈
+ <
�∩
( ) ( ) ( )
( )
*
T* *
T*
Soit . Démontrons alors que : Supposons que nous pouvons démontrer
qu'il nHYPOTHÈSE À VÉRIFIER
'existe pas de vecteur tel que
0 5.6
0
est effectivement vérifiée sous les hypo
n
i
x R
d R
f x d i A x
f x d
δ∈
∈
∇ ≤ ∈
∇ <
�
1*
thèses du théorème. En effet, pour ˆfin de contradiction, supposons qu'un tel vecteur existerait. Puisque
, , satisfont les restrictions sur les fonctions de contraintes au point
, alors il exim
d
f f
x
…
[ ] ( )( )
( )( ) ( )( ) ( ) ( )
[ ] ( ) ( )
( )( )
*
*T T* *
0
*
ste une fontion différentiable : 0,1 telle que 0ˆet 0 , 0. Mais ainsi,
ˆlim 0 0,
ˆ ˆce qui implique l'existence d'un 0,1 assez petit pour que
ˆtel que
R x
d
f f xf x f x d
B x
f f
θ
ε
α α
α σ σ
α θα σ
θ
θ α θ
α θ
→
→ =
′ = >
−′= ∇ = ∇ <
∈ ∈
<
�
( ) ( )* ˆ, une contradiction puisque .
Le reste de la preuve se fait comme précédemment lorsque nous supposions quel'hypothèse était vérifiée.
x Rα θ ∈ �
( ) ( )( )
T
0lim
f x d f xf x d
θ
θ
θ→
+ −= ∇
Conditions K-K-T pour la programmation linéaire
Conditions K-K-T résultats de dualité et d'écarts complémentaires.Pour la programmation linéaire,
conditions K-K-T sont suffisantes puisque les fonctions linéaires sont convexes.
conditions K-K-T
↔
−
−
1
sont nécessaires puisque les fonctions linéaires satisfont toujours les restrictions sur les fonctions de contraintes.
Soit le problème de programmation linéaire suivant:
Min
Sujet à
n
j j
j
ij
c x
a x
=
∑
1
1, ,
0 1, , .
n
j i
j
j
b i m
x j n=
≥ =
≥ =
∑ …
…
1
1
1
1
Soit le problème de programmation linéaire suivant:
Min
Sujet à 1, ,
0 1, , .Ce problème s'écrit également
Min
Sujet à 0 1, ,
0 1, , .
n
j j
j
n
ij j i
j
j
n
j j
j
n
ij j i
j
i
j
c x
a x b i m
x j n
c x
a x b i m
x j n
λ
=
=
=
=
≥ =
≥ =
− + ≤ =
− ≤ =
∑
∑
∑
∑
…
…
…
…
Associons un multiplicateur à chacune des premières contraintes et unmultiplicateur à chacune des dernières contraintes.
m j
i
m j
m
n
λ
λλ
+
+
1
1
Min
Sujet à 0 1, ,
0 1, , .Associons un multiplicateur à chacune des m premières contraintes et unmultiplicateur à chacune des n dernières contraintes.
i
m j
i
m
n
j j
j
n
ij j i
j
j
j
c x
a x b i m
x j n
λ
λ
λλ
=
+
=
+
− + ≤ =
− ≤ =
∑
∑ …
…
( ) ( ) ( )
( )
1 1 1
1
1
Les conditions K-K-T s'écrivent comme suit:
0 1, ,
0 1, ,
0 1, ,
0 1, ,
0 1, ,0
m m n mi i
i i j i ij m j
j j ji i m i
n
i ij j i
j
m j j
n
ij j i
j
j
j
f x f x f xc a j n
x x x
a x b i m
x j n
a x b i m
x j n
j
λ λ λ λ
λ
λ
λ
+
+
= = + =
=
+
=
∂ ∂ ∂+ + = − − = =
∂ ∂ ∂
− + = =
− = =
− + ≤ =
− ≤ =
≥
∑ ∑ ∑
∑
∑
…
…
…
…
…
1, , .m n= +…
( ) ( )* * *
1
0m
ii
i
f x f xλ=
∇ + ∇ =∑
1 1
1 1
1
Considérons maintenant le problème dual:
Min Max
Sujet à 1, , Sujet à 1, ,
0 1, , 0 1, ,
Dua
.Conditions K-K
Pr a
T
l l
-
imn m
j j i i
j i
n m
ij j i ij i j
j i
j i
m
j i ij m j
i
c x b y
a x b i m a y c j n
x j n y i m
c aλ λ
= =
= =
+
=
≥ = ≤ =
≥ = ≥ =
− − =
∑ ∑
∑ ∑
∑
… …
… …
( )1
1
0 1, ,
0 1, ,
0 1, ,
0 1, ,
0 1, ,0 1, ,
n
i ij j i
j
m j j
n
ij j i
j
j
i
j n
a x b i m
x j n
a x b i m
x j n
i m n
λ
λ
λ
=
+
=
=
− + = =
− = =
− + ≤ =
− ≤ =
≥ = +
∑
∑
…
…
…
…
…
…
1 1
1 1
1
Considérons maintenant le problème dual:
Min Max
Sujet à 1, , Sujet à 1, ,
0 1, , 0 1, , .Conditions K-K-
Prim Dal
T
ual
m
j i i
n m
j j i i
j i
n m
ij j i ij i j
j i
j i
j m j
i
c x b y
a x b i m a y c j n
x j n y
c a
i m
λ λ
= =
= =
+
=
− −
≥ = ≤ =
≥ = ≥ =
=
∑ ∑
∑
∑
∑ … …
… …
( )1
1
0 1, ,
0 1, ,
0 1, ,
0
0 1, ,
1, ,
0 1, ,
n
i ij j i
j
m j j
n
ij j i
j
j
i
a x b i m
x j n
a
j n
x b i
m n
m
x j
i
n
λ
λ
λ
=
+
=
− + = =
=
≥
− = =
− + ≤
= +
=
− ≤ =
∑
∑
…
…
…
…
…
…
1
1
1
1
Le vecteur , , est solution réalisable pour le dual: pour 1, ,
0
0
De plus0 1, , .
m
m
j i ij m j
im
j i ij m j
i
m
i ij j
i
i
j n
c a
c a
a c
i m
λ λ
λ λ
λ λ
λ
λ
+
=
+
=
=
=
− − =
− = ≥
≤
≥ =
∑
∑
∑
…
…
…
1 1
1 1
1
Considérons maintenant le problème dual:
Min Max
Sujet à 1, , Sujet à 1, ,
0 1, , 0 1, ,
Dua
.Conditions K-K
Pr a
T
l l
-
imn m
j j i i
j i
n m
ij j i ij i j
j i
j i
m
j i ij m j
i
c x b y
a x b i m a y c j n
x j n y i m
c aλ λ
= =
= =
+
=
≥ = ≤ =
≥ = ≥ =
− − =
∑ ∑
∑ ∑
∑
… …
… …
( )1
1
0 1, ,
0 1, ,
0 1, ,
0 1, ,
0 1, ,0 1, ,
n
i ij j i
j
m j j
n
ij j i
j
j
i
j n
a x b i m
x j n
a x b i m
x j n
i m n
λ
λ
λ
=
+
=
=
− + = =
− = =
− + ≤ =
− ≤ =
≥ = +
∑
∑
…
…
…
…
…
…
1 1
1 1
1
Considérons maintenant le problème dual:
Min Max
Sujet à 1, , Sujet à 1, ,
0 1, , 0 1, , .Conditions K-K-
Prim Dal
T
ual
m
j i i
n m
j j i i
j i
n m
ij j i ij i j
j i
j i
j m j
i
c x b y
a x b i m a y c j n
x j n y
c a
i m
λ λ
= =
= =
+
=
− −
≥ = ≤ =
≥ = ≥ =
=
∑ ∑
∑
∑
∑ … …
… …
( )1
1
0 1, ,
0 1
0 1, ,
0 1, ,
0 1, ,0 1, ,
, ,
n
i ij j i
j
n
ij j i
j
j
j
m j j
j n
x j n
a x b i m
a x b i m
x j n
j m nλ
λ
λ=
+
=
− + = =
− + ≤ =
=
− = =
− ≤ =
≥ = +
∑
∑
…
…
…
…
…
…
1
1
1
1 1 1
Le vecteur , , est solution optimale pour le dual: pour 1, ,
0
0
m
m
j j i ij m j
i
m
j j i ij j m j j
i
n n m
j j i ij j
j j i
j n
x c a
c x a x x
c x a x
λ λ
λ λ
λ λ
λ
+
=
+
=
= = =
=
− − =
− = =
=
∑
∑
∑ ∑∑
…
…
1 1
1 1
1
Considérons maintenant le problème dual:
Min Max
Sujet à 1, , Sujet à 1, ,
0 1, , 0 1, ,
Dua
.Conditions K-K
Pr a
T
l l
-
imn m
j j i i
j i
n m
ij j i ij i j
j i
j i
m
j i ij m j
i
c x b y
a x b i m a y c j n
x j n y i m
c aλ λ
= =
= =
+
=
≥ = ≤ =
≥ = ≥ =
− − =
∑ ∑
∑ ∑
∑
… …
… …
( )1
1
0 1, ,
0 1, ,
0 1, ,
0 1, ,0 1,
1
,
0 , ,
m j j
n
ij j i
j
j
j j
j
n
i i i
j
j n
x j n
a x b i
a x b i m
x j n
j m
m
n
λ
λ
λ
+
=
=
− + = =
=
− = =
− + ≤ =
− ≤ =
≥ = +
∑
∑
…
…
…
…
…
…
1
1 1 1
1
1
1 1 1
Le vecteur , , est solution optimale pour le dual:
Pour 1, ,
0
m
n n m
j j i ij j
j j i
n
i ij j i
j
n
i i i ij j
j
m m n
i i i ij j
i i j
c x a x
i m
a x b
b a x
b a x
λ λ
λ
λ
λ λ
λ λ
= = =
=
=
= = =
=
=
− + =
=
=
∑ ∑∑
∑
∑
∑ ∑∑
…
…
1 1
1 1
1
Considérons maintenant le problème dual:
Min Max
Sujet à 1, , Sujet à 1, ,
0 1, , 0 1, ,
Dua
.Conditions K-K
Pr a
T
l l
-
imn m
j j i i
j i
n m
ij j i ij i j
j i
j i
m
j i ij m j
i
c x b y
a x b i m a y c j n
x j n y i m
c aλ λ
= =
= =
+
=
≥ = ≤ =
≥ = ≥ =
− − =
∑ ∑
∑ ∑
∑
… …
… …
( )1
1
0 1, ,
0 1, ,
0 1, ,
0 1, ,
0 1, ,0 1, ,
n
i ij j i
j
m j j
n
ij j i
j
j
j
j n
a x b i m
x j n
a x b i m
x j n
j m n
λ
λ
λ
=
+
=
=
− + = =
− = =
− + ≤ =
− ≤ =
≥ = +
∑
∑
…
…
…
…
…
…
1
1 1 1
1 1 1
1 1
Le vecteur , , est solution optimale pour le dual:
Par conséquent
et le résultat découle du théorème de dualité faible.
m
n n m
j j i ij j
j j i
m m n
i i i ij j
i i j
n m
j j i
j i
c x a x
b a x
c x b
λ λ
λ
λ λ
λ
= = =
= = =
= =
=
=
=
∑ ∑∑
∑ ∑∑
∑ ∑
…
1 1
1 1
1
Considérons maintenant le problème dual:
Min Max
Sujet à 1, , Sujet à 1, ,
0 1, , 0 1, ,
Dua
.Conditions K-K
Pr a
T
l l
-
imn m
j j i i
j i
n m
ij j i ij i j
j i
j i
m
j i ij m j
i
c x b y
a x b i m a y c j n
x j n y i m
c aλ λ
= =
= =
+
=
≥ = ≤ =
≥ = ≥ =
− − =
∑ ∑
∑ ∑
∑
… …
… …
( )1
1
0 1, ,
0 1, ,
0 1, ,
0 1, ,
0 1, ,0 1, ,
n
i ij j i
j
m j j
n
ij j i
j
j
i
j n
a x b i m
x j n
a x b i m
x j n
i m n
λ
λ
λ
=
+
=
=
− + = =
− = =
− + ≤ =
− ≤ =
≥ = +
∑
∑
…
…
…
…
…
…
1 1
1 1
1
Considérons maintenant le problème dual:
Min Max
Sujet à 1, , Sujet à 1, ,
0 1, , 0 1, , .Conditions K-K-
Prim Dal
T
ual
m
j i i
n m
j j i i
j i
n m
ij j i ij i j
j i
j i
j m j
i
c x b y
a x b i m a y c j n
x j n y
c a
i m
λ λ
= =
= =
+
=
− −
≥ = ≤ =
≥ = ≥ =
=
∑ ∑
∑
∑
∑ … …
… …
( )1
1
0 1, ,
0 1, ,
0 1
0 1, ,
0 1, ,0 1, ,
, ,n
ij j i
j
j
n
i ij j i
j
j
j
m j
a
j n
a x b i m
x b i m
x j n
j m n
x j n
λ
λ
λ
=
+
=
=
− + ≤ =
− ≤ =
− + = =
+
−
≥ =
= =
∑
∑ …
…
…
…
…
…
1
1
1
1
Pour 1, ,
0
0
0.
Pour 1, ,
0.
m
j i ij m j
i
m
j j i ij m j
i
m
j j i ij j m j
i
n
i ij j i
j
j n
c a
x c a
x c a x
i m
a x b
λ λ
λ λ
λ λ
λ
+
=
+
=
+
=
=
=
− − =
− − =
− = =
=
− + =
∑
∑
∑
∑
…
…
