Upload
tass
View
30
Download
1
Embed Size (px)
DESCRIPTION
Combinatorial Structures in Nonlinear Programming. Pr ésentation d’un article de Stefan Scholtes April 2002. Id ée: Généralisation. Programme Non Linéaire (PNL) Programme Combinatoire Non Linéaire (PCNL). Id ée: Généralisation (2). Conditions sur g, h Conditions sur Z. - PowerPoint PPT Presentation
Citation preview
Combinatorial Structures in Nonlinear Programming
Présentation d’un article de Stefan Scholtes
April 2002
Idée: Généralisation
Programme Non Linéaire (PNL)
Programme Combinatoire Non Linéaire (PCNL)
mZxg
xf
)(~
)(min
mxg
xf
)(
)(min
Idée: Généralisation (2)
Conditions sur g, h Conditions sur Z
Ig ~
0),(
),(min2 yxyxg
yxf
}0|),{(
),(
),(min
2
vuvuZ
Zyx
yxf
Idée: Généralisation (3)
Biniveau vs PCNL
0)(
0,,
min
221
21
22
221
2211),,( 21
bxAAx
xx
dA
bxAAx
xcxcxx
}0|),{(),(
),(
0
min
2
221
22
221
2211),,,( 21
xyyx
xx
dA
bxAAx
xcxcxx
Que deviennent les notions classiques?
Contraintes actives, inactives
Points réguliers
Points stationnaires
Multiplicateurs de Lagrange
Activité des contraintes/composantes
Définition
.)(en (inactive) activeest
si point un en (inactive) active diteest contrainte
Une.en inactives ditessont scomposante autres Les
si que tel)( si
point un en inactive appeléeest composante Une
Zxgz
zxg
z
Zz"Zz'
i,j",z') et zzV(z', z"zV
Zzz
ii
jj
i
Activité - Illustration
y
xp z1
z2
z1
x
y
z2 z2
z1
x y
x: z1 (i), z2 (a)
y: z1 (a), z2 (i)
p: z1 (a), z2 (a)
x: z1 (a), z2 (a)
y: z1 (a), z2 (a)
x: z1 (i), z2 (a)
y: z1 (a), z2 (a)
Régularité et Stationnarité
Régularité
Stationnarité
Dans le cas classique
0 localesolution pour a
)()(
)(min
si PCNLdu restationnaipoint un est
d
Zdxgxg
dxf
x
d
mZ
ts.indépendennt linéairemesont en actives scontrainte
des gradients les si en régulièressont scontrainte les quedit On
x
x
Stationnarité
PNL
PCNL
Il faut introduire une condition supplémentaire
itéstationnar régulier et local min. x
itéstationnar régulier et local min. x
Condition supplémentaire: Exemple
}0|),{(
2min
22121
221
),( 21
zzzzZ
xxZxx
Z
f
0
min
)0,0(en Or,
)}0,0{(
22
1
2)d,(d
*
21
-dd
d
X
Ensemble localement étoilé
Définition
PCNL
)zV(Zzz)zV(Zz
) zV(z
Z
)1(
],1,0[ que, tel si réalisable point
unen étoilé localementdit est ensembleUn
)(en étoilé localement
itéstationnar et
régulier.et local min.
xgzZ
x
Ensemble localement étoilé Exemples
z1
z2
z2
z1z2
z1
Multiplicateurs de Lagrange
Définition
xg
g(x) λf(x) L(x,
xcritique
g(x) f(x) ) L(x,
i
Tx
T
en inactiveest si ;0
0)
que tel si point un diraon l'et
est PCNLau associé lagrangien Le
i
Multiplicateurs de Lagrange (2)
Proposition
PNL
PCNL
critique restationnai xx
)0( KKT restationnai :régulier iλxxx
Zv)xg(
vλargmax0 Tv
& )( critique restationnai
:régulier
λxx
x
Multiplicateurs de Lagrange (3) Exemple (Utilisations des nouvelles notions)
}0|{
])1()1[(2
1min
21
22
21
zzzZx
xx
Z
)0,0(0&
0où max au 0
00 :critique
0,
maxarg0
:itéStationnar
101
101
:critiquept de Conditions
sinon. inactiveset
0
si actives et Remarque
21
2121
2222
1111
21
21
xxxexe
evv
vvxxx
Zv x
vλ
xx
xx
zz
zz
T
Tv
Multiplicateurs de Lagrange (4)
Complémentarité stricte
Zv)x(g
vλ maxarg0
AA
AT
Av
AAA
A
V
V
x
)(~
que tel)( si stricte aritécomplément
la aOn re.stationnaiet critique régulier, Soit
PNL - Sequential Quadratic Programming (SQP)
. à
0),(),(
Raphson-Newton Appliquons
0 )(
)()(),(:),(
de local minimumet régulier
0)(
)(min
1
1
(1)
(1)
kk
kkkkkk
xKKT
xxxFxF
xh
xhxfxLxF
(P)x
xh
xf(P)
PNL - Sequential Quadratic Programming (SQP)
4.3.3)-4.3.2 (Prop. descente. dedirection uneest obtenuedirection la
quedémontrer )pas!surtout veut neon (maispourrait on l'et
0)()(
),()( min
programmeun en précédent système leformer peut transOn
0)()(
0)(),()(
donc aon ,posant en
0 )(
)( ),(),(
trouvonsfaire, cePour
2
d
12
1
2
dxhxh
dxLddxf
dxhxh
dλxhdxLddxf
xxd
xh
xhxLxF
kk
kkxx
k
kk
kkkkxx
k
kk
k
kkkxxkk
PNL - Sequential Quadratic Programming (SQP) (2)
Algorithme SQP
positive. définie symétriqueest où
)()(
2
1)(min
desolution est et négatifnon pasun est où
),(
1
k
Tkk
kTTkd
kk
kkkk
H
dxgxg
cHddxf
d
dxx
Les notions classiques sont généralisables!
Contraintes actives, inactives Composantes
Points réguliers
Points stationnaires
Multiplicateurs de Lagrange Points Critiques
PCNL - Sequential Quadratic Programming (SQP généralisé)
Algorithme SQP généralisé
Zdxgxg
dxLddxf
d
dxx
Tkk
xxTTk
d
kk
kkkk
)()(
),(2
1)(min
desolution est et négatifnon pasun est où
2),(
1
PCNL - SQP généralisé (2)
Convergence en
.en active contrainte pour toute
0 avec 0pour tout 0),( -
en stricte aritécomplément la aOn -
teur multiplica de restationnaiet régulier est -
)(en étoilé localementest -
2
*
*
**
*i
*i
**xx
xg
)d(xgdxL
x
x
xgzZ
*x
PCNL - SQP généralisé (3)
critiques.
points des doncsont originel' de près restationnai points seuls Les ion.Contradict
.petit 0, s.t. ,)]([maxarg0et )( entraîne qui
ce , s.t. ,maxarg0 Ainsi, étoilé).t (localemen ],[ donc ,
sconsidéron ,pour effet,En origine.l' de près restationnai points seuls lessont Ce
))(
), mult. avec resstationnai ), maxarg0
stricte aritécomplément ,Pour ).,),, implicites Fonctions
.), donnéétant (CQP)nt solutionne et 0)( critique
***
*
***
Zu zuzzμzz
Zw zμwZzz)V(zz
zz
,λV(xx,Zv z
z(x,zd(x,v
)V(λμz(x,zd(x,
),z,λ (xz(x,dx
u
w
*
*
***
**
v
*
***
CP CQP