23
Combinatorial Structures in Nonlinear Programming Présentation d’un article de Stefan Scholtes April 2002

Combinatorial Structures in Nonlinear Programming

  • 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

Page 1: Combinatorial Structures in Nonlinear Programming

Combinatorial Structures in Nonlinear Programming

Présentation d’un article de Stefan Scholtes

April 2002

Page 2: Combinatorial Structures in Nonlinear Programming

Idée: Généralisation

Programme Non Linéaire (PNL)

Programme Combinatoire Non Linéaire (PCNL)

mZxg

xf

)(~

)(min

mxg

xf

)(

)(min

Page 3: Combinatorial Structures in Nonlinear Programming

Idée: Généralisation (2)

Conditions sur g, h Conditions sur Z

Ig ~

0),(

),(min2 yxyxg

yxf

}0|),{(

),(

),(min

2

vuvuZ

Zyx

yxf

Page 4: Combinatorial Structures in Nonlinear Programming

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

Page 5: Combinatorial Structures in Nonlinear Programming

Que deviennent les notions classiques?

Contraintes actives, inactives

Points réguliers

Points stationnaires

Multiplicateurs de Lagrange

Page 6: Combinatorial Structures in Nonlinear Programming

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

Page 7: Combinatorial Structures in Nonlinear Programming

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)

Page 8: Combinatorial Structures in Nonlinear Programming

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

Page 9: Combinatorial Structures in Nonlinear Programming

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

Page 10: Combinatorial Structures in Nonlinear Programming

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

Page 11: Combinatorial Structures in Nonlinear Programming

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

Page 12: Combinatorial Structures in Nonlinear Programming

Ensemble localement étoilé Exemples

z1

z2

z2

z1z2

z1

Page 13: Combinatorial Structures in Nonlinear Programming

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

Page 14: Combinatorial Structures in Nonlinear Programming

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

Page 15: Combinatorial Structures in Nonlinear Programming

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

xx

xx

zz

zz

T

Tv

Page 16: Combinatorial Structures in Nonlinear Programming

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

Page 17: Combinatorial Structures in Nonlinear Programming

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)

Page 18: Combinatorial Structures in Nonlinear Programming

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

Page 19: Combinatorial Structures in Nonlinear Programming

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

Page 20: Combinatorial Structures in Nonlinear Programming

Les notions classiques sont généralisables!

Contraintes actives, inactives Composantes

Points réguliers

Points stationnaires

Multiplicateurs de Lagrange Points Critiques

Page 21: Combinatorial Structures in Nonlinear Programming

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

Page 22: Combinatorial Structures in Nonlinear Programming

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

Page 23: Combinatorial Structures in Nonlinear Programming

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