Workshop Memecahkan Masalah Kendali Optimal dengan Metode Langsung

Workshop – Memecahkan Masalah Kendali Optimal dengan Metode Langsung Karunia Putra Wijaya Mathematical Institute University of Koblenz–Landau Dipresentasikan di Universitas Indonesia Kampus Depok, May 11, 2017

Outline

Bagian 0: Motivasi Bagian 1: Optimasi Taklinier Dasar–dasar Teorema Karush–Kuhn–Tucker Bagian 2: Sequential Quadratic Programming Bagian 3: Masalah Kendali Optimal dengan Persamaan Di↵erensial Biasa Beberapa definisi elementer Masalah kendali optimal Metode Langsung

, UNIKO, Compact Course, August 20, 2017

2

Model dinamika nyamuk 1 [WGS2014]

u1

u1

E1

L1

Model matematika 8 > E˙1 = p↵A ( 1 + µ1 )E1 qu1 E1 > > > > > ˙ > > <E2 = (1 p)↵A ( 2 + µ2 )E2 2 ˙L1 = 1 E1 ( 3 + µ3 )L1 u1 L1 1 L1 > > > 2 > ˙ > L2 = 2 E 2 ( 4 + µ4 )L2 2 L2 > > > : ˙ A = 3 L1 + 4 L2 µ5 A u2 A.

↵ ↵

u2

A

E2

L2

I

indoor–outdoor

I

age

I

↵ constant


3

Model dinamika nyamuk 1 [WGS2014] 180

100

Uncontrolled Controlled

Uncontrolled Controlled 90

160

140

outdoor larva (individual)

indoor larva (individual)

80

70

60

50

40

30

100

Masalah kendali optimal

80

60

40

20

20

10

0

120

0

50

100

0

150

0

50

100

150

time (day)

time (day)

1

40

Temephos dissm. Fumigation

Uncontrolled Controlled

+

0.9

35

0.8

Control measures (1/day)

25

20

15

T 0

X

X

!x,i xi2

i

!u,j uj2 dt

j

30

adult (individual)

min

Z

0.7

s.t. Model and

0.6

0.5

0  uj  1, j = 1, 2.

0.4

0.3

10 0.2 5

0

0.1

0

50

100

150

0

time (day)

0

50

100

150

time (day)


4

Model dinamika nyamuk 2 [WGS2015]

E1

Model matematika 8 > >E˙1 = p↵(t)A ( 1 + µ1 )E1 qu1 E1 , > > > > ˙ > > <E2 = (1 p)↵(t)A ( 2 + µ2 )E2 , 2 L˙ 1 = 1 E1 ( 3 + µ3 )L1 u1 L1 , 1 L1 > > > 2 > ˙ > L2 = 2 E 2 ( 4 + µ4 )L2 , 2 L2 > > > : ˙ A = 3 L1 + 4 L2 µ5 A u2 A.

L1

↵(t) ↵(t)

A

E2 I

L2

↵ periodic ↵(t) := ✏ + ✏0 cos( t)


5

Model dinamika nyamuk 2 [WGS2015] 5

1

2.1

2.1

2.1

temephos ULV aerosol 0.9

4.5

2

2

4

2

2

0.8

1.9

3

1.8

1.8

1.8

1.7

1.7

1.7

2.5

control (1/day)

ε

0.7

1.9

1.9

3.5

0.6

Masalah kendali optimal

0.5

0.4

1.6

1.6

1.6

0.3

1.5

1.5

1.5

0.2

1.4

1.4

1.4

0.1

1.3

1.3

1.3

2

1.5

1

0

0.1

0.2

0

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0

50

100

150

time (day)

p

500

+

350 ind. egg out. egg ind. larv out. larv adult

450

ind. egg out. egg ind. larv out. larv adult

300

all classes (individual)

all classes (individual)

250

200

150

T 0

X

X

!x,i xi2

i

!u,j uj2 dt

s.t. Model and

250

350

Z

j

400

300

min

200

0  uj  1, j = 1, 2.

150

100

100 50 50

0

0

50

100

150

0

0

time (day)

50

100

150

time (day)


6

Model epidemic dengue SIRUV [GABW2017] 60 raw data Fourier filtered, quarterly

Dengue Cases

50

I

40

Original model S

I

U

V

R

30 20 10 0

2010

2011

2012

2013

2014

2015

Date

I

R˙ = I

S)

M

SV , I˙ =

M

✓ UI N

µR, U˙ =

✓ V˙ = UI N

SV

( + µ)I ,

R˙ = I

I

I

R

Constant population R

Parameter estimation 1 I I DATA 2 s.t. IR–model

⇢V ,

(N

I

I

I ⇢U,

min

IR–model I˙ =

Time scale separation S

SIRUV–model S˙ = µ(N

I

I

R)

µR.

UNIKO, Compact Course, August 20, 2017

I I + ⌫N

( + µ)I ,

µ 1 65·365

1 30

2

+

! k k2 2

⌫ 0.5

, 7

Model epidemik dengue SIRUV [GABW2017] 60 raw data Fourier filtered, quarterly

Dengue Cases

50 40 30 20 10 0

2010

2011

2012

2013

2014

I

2015

Date 40

20

Monthly average Precip.

Dengue Cases

30

15

20

10

10

5

0

Jan 2010

Jul 2010

Jan 2011

Jul 2011

Jan 2012

Jul 2012

Jan 2013

Jul 2013

Jan 2014

Jul 2014

Jan 2015

Date 70 Reported Data Simulation with new β model Simulation with first β model

60

1st-step: Relate directly with precipitation

Precipitation [mm/d]

Data Simulation with Model β Simulation with βopt

= I

|

Xp + ¯ . {z }

unknows

2nd-step: correct

by

0

=(

Xp + ¯) · k1 · k2 .

Dengue Cases

50 40 30 20 10 0

Jan 2010

Jul 2010

Jan 2011

Jul 2011

Jan 2012

Jul 2012

Jan 2013

Jul 2013

Jan 2014

Jul 2014

Jan 2015

,

Date


8

Model epidemik dengue SIR [WG2017]

1200

1200

1000

1000

800

800

25 20

⌫

15

# of cases

# of cases

10

600

5 0 0.65

0.7

0.75

0.8

0.85

0.9

0.95

β

600

S

20

400

400

200

200

0

0

I

R

15 10 5

0

10

20

30

40

50

60

0

10

20

-th month

30

40

50

0 0.8

60

0.82

0.84

-th month

1200

1.4

0.86

0.88

0.9

0.92

×10 6

I

Deterministic, constant

I

Stochastic, constant

I

Deterministic, time-varying

I

Spatially uniform

1200 y1

y 2,e

1000

y2

# of cases

1.395 1000 1.39

800 600 400

1.385

800

# of cases

0.94

γ

200 0

1.38 0

10

20

30

40

50

60

0

10

20

2

30

40

50

×10 4

2 βe β

y3

400

60

-th month

-th month

600

1.5

1.5 1

1

0.5

0.5

200

0 0

10

20

30

40

50

60

0

0 0

10

20

-th month

30

-th month

40

50

60

0

10

20

30

40

50

60

-th month


9

Model epidemik dengue SIR [WG2017] 1

1

45

40

0.6

30

40

0.8

35

0.8

14

0.6

10

12

35

30

0.6 25

25

0.4

20

20

0.4

8

0.4 6

15 15

0.2

10

10

0.2 0

0

0.5

1

2

0 0

t=0

0.5

1

0

t=1

1

0.5

1

1

30

0.8

20

0.8

25

0.6

1

15

0.6

0.4

10

0.4

0.2

5

0.2

8

0.6

20

6

0.4

15

4

0.2

2

0

10

0 0

0.5

1

5

0 0

t=3

0.5

I

1

0

t=4

0.5

I I

Reaction–di↵usion optimal from the seasonal model

1

t=5

1 1

1 40

30

1

3

20

0.8

2.5

0.8

0.6

0.6

2

0.6

1.2

35

0.6

30

15

0.6

10

0.4

0.4

0.2

0.2

0.4

25

0.5

20

0.2

0.2

1

15

0

0.5

0

0 12

0

1

0

t=1

0.5

0.5

0

1

0

t=0

0.5

1

1

24

1

10

0.8

23

0.8

1

0.8

1

2.5

22

0.6

0.8

21

0.4

0.2 0.2

0.2

t=3

23

19

0 1

22

0 0

0.5

1

t=4

1.5

1 3

0.8

2.5

0.5

0.4

1

0.4

0.2

0.5

0.2

1.5 1

0.2

0

0 0

0.5

t=3 0

2

0.6

0.4

24

20

2

0.5

0.6

0.4

25

0.4

4

2

0.6

27

0.6 26

6

0.8

28

0.6

0

1

1

29

0

0.5

t=2

1.2 12

0.2

0

t=1

1 1

0.4

0.2

0

t=2

0.8

8

0.4

0.2

13

0.2

0

t=0

0.6

0.6

14

0.4

0.5

0 0

0.8

0.4 1

0.4

5

0

1

1.5

15

0.2

1.6 1.4

0.8

0.6

16

0.8

25

0.4

1

0.8 40

0.8

35

0.6

1

1

45

0.8

R

t=2

10

0.8

S

4

0.2

5

5

0

⌫

1 16

45

0.8

1

0.5

0 0

0.5

t=4

1

0

0.5

1

t=5

1

t=5


10

The basic reproductive number: motivasi

Apa yang terjadi dalam jangka waktu yang cukup lama?


11

Outline



12

Norm Definisi Misal X adalah sebuah ruang vektor atas lapangan riil R. Pemetaan k·k : X ! R dikatakan sebagai norm jika memenuhi 3 kondisi: 1. kxk > 0 untuk setiap x 2 X , x 6= 0

2. k↵xk = |a| kxk untuk setiap ↵ 2 C dan x 2 X 3. kx + y k  kxk + ky k untuk setiap x, y 2 X .

Beberapa contoh I

l p –norm kxkp :=

I

l 1 –norm kxk1 := lim

p!1

n X i=1

n X i=1

|xi |

|xi |

p

p

!1/p

!1/p

= max |xi | . i


13

Norm matriks Norm ”Terinduksi” Untuk A 2 Rn⇥m , norm terinduksi dari A didefinisikan sebagai kAkp := maxm x2R

kAxkp kxkp

= max kAxkp . kxkp =1

Beberapa contoh I

I I

⇣P ⌘> P kAk1 = maxkxk1 =1 kAxk1 = maxkxk1 =1 = j A1j xj , · · · , j Anj xj ⇣P ⌘ P P P P P maxkxk1 =1 i j Aij xj  maxkxk1 =1 j |xj | i |Aij |  maxj i |Aij | j |xj | . P P Pilih k sehingga i |Aik | = maxj i |Aij | dan xk = 1 dan xj = 0 untuk j 6= k. P P P P Maka kAxk1 = maxkxk1 =1 i j Aij xj = i |Aik | = maxj i |Aij |. P kAk1 = maxi j |Aij |. p > kAk2 = max (A A) =: max (A). Kepositifan?


14

Bola dan persekitaran

Bola Sebuah bola dengan radius ✏ > 0 dan pusat x 2 Rn disimbolkan B✏ (x) ⇢ Rn (buka) atau B✏ (x) ⇢ Rn (tutup) didefinisikan sebagai B✏ (x) := {y 2 Rn : kx n

B✏ (x) := {y 2 R : kx

y k < ✏} y k  ✏} .

Persekitaran Sebuah himpunan U(x) dikatakan sebagai persekitaran dari x 2 Rn jika terdapat ✏ > 0 sehingga x 2 B✏ (x) ✓ U(x).


15

Gradien, Hessian, O ”big–oh”, o ”small–oh” Gradien dan Hessian Misal f : D ! R dimana D ⇢ Rn terbuka dan f 2 C 2 (D). I

Gradien dan Hessian dari f di x 2 D didefinisikan sebagai ✓ ◆ @f @f rf (x) := (x), · · · , (x) @x1 @xn 0 @2f 2 f (x) · · · @x@1 @x (x) ✓ 2 ◆ @x1 @x1 n B @ f (x) .. . 2 . B .. .. r f (x) := = . @xi @xj i,j @ @2f @2f (x) · · · @xn @xn (x). @xn @x1

1 C C A

O dan o Misal f , g : Rn ! Rm dan x0 2 Rn . I I

Kita katakan f = O(g ) saat x ! x0 jhj terdapat C > 0 dan UC (x0 ) sehingga f (x)  Cg (x) untuk setiap x 2 UC (x0 ). Kita katakan f = o(g ) jhj limx!0 f (x)/g (x) = 0.


16

Kecepatan konvergensi Definisi Misal (zk )k sebuah barisan dimana limk!1 zk = z ⇤ . Maka kita katakan I

(zk )k konvergen linier ke z ⇤ jika terdapat M 2 (0, 1) sehingga kzk+1

I

z ⇤k

(zk )k konvergen kuadrat ke z ⇤ jika terdapat M > 0 sehingga kzk+1

I

z ⇤ k  M kzk z ⇤ k  M kzk

z ⇤k

2

(zk )k konvergen superlinier ke z ⇤ dengan order ↵ > 1 jika terdapat M > 0 sehingga ↵ kzk+1 z ⇤ k  M kzk z ⇤ k

untuk k yang cukup besar.

Konvergen lokal (zk )k dikatakan konvergen lokal ke z ⇤ jika terdapat ✏ > 0 sehingga limk!1 zk = z ⇤ jhj z1 2 B✏ (z ⇤ ).


17

Keminimalan

Definisi Misal f : D ! R dimana D ✓ Rn . Sebuah titik x ⇤ 2 D dikatakan sebagai I

minimum lokal, jika terdapat persekitaran U(x ⇤ ) sehingga f (x ⇤ )  f (x),

I

minimum lokal ketat, jika f (x ⇤ ) < f (x),

I

8x 2 D \ U(x ⇤ )

minimum global, jika

8x 2 (D \ U(x ⇤ )) \ {x ⇤ }

f (x ⇤ )  f (x),

8x 2 D.


18

Syarat perlu dan syarat cukup (EXERCISE 1)

Theorem (Syarat perlu) Misal f 2 C 2 (D) dimana D ✓ Rn buka. Jika x ⇤ 2 D minimum lokal, maka sudah pasti rf (x ⇤ ) = 0

(syarat perlu pertama)

r2 f (x ⇤ ) semidefinit positif.

(syarat perlu kedua)

Theorem (Syarat cukup) Misal f 2 C 2 (D) dimana D ✓ Rn buka dan x ⇤ 2 D sebarang titik. Jika rf (x ⇤ ) = 0 dan

r2 f (x ⇤ ) definit positif, maka x ⇤ adalah minimum lokal ketat dari f di D.


19

Kecembungan/konveksitas I

Sebuah himpunan D ⇢ Rn dikatakan konveks, jika 8x, y 2 D dan 8 2 (0, 1), x + (1

I

Sebuah fungsi f : D ! R dimana D ⇢ R konveks dikatakan sebagai fungsi konveks, jika 8x, y 2 D dan 8 2 (0, 1), f (x + (1

I

)y 2 D.

n

)y )  f (x) + (1

)f (y ).

)y ) < f (x) + (1

)f (y ).

f dikatakan sebagai fungsi konveks ketat, jika 8x, y 2 D dan 8 2 (0, 1), f (x + (1 Bagaimana melihat ini secara geometri?

Beberapa sifat fungsi konveks: (A1) Jika fi : D ! R konveks dan ↵i (A2) Level set dari f : D ! R, konveks di Rn .

c

0 (i = 1, · · · , m), maka n

P

i

↵i fi juga konveks.

:= {x 2 R : f (x)  c} merupakan himpunan

(A3) Setiap minimum lokal dari f : D ! R adalah minimum global dari f di D dan himpunan dari semua minimum global dari f adalah konveks.


20

Kecembungan/konveksitas

f (x) + (1

f (y )

)f (y )

f (x) f ( x + (1

x

)y )

y


21

Kecembungan/Konveksitas

(A4) Jika f : D ! R konveks ketat, maka terdapat satu saja minimum global dari f di D. (A5) Jika f 2 C 1 (Rn ), maka f konveks di sebuah himpunan konveks D ⇢ Rn jhj f (y )

f (x) + rf (x)> (y

untuk setiap x, y 2 D. 2

✓

x) x

y

n

(A6) Jika f 2 C (R ), maka f konveks di sebuah himpunan konveks D ⇢ Rn jhj r2 f (x) semidefinit positif untuk setiap x 2 D.

f (y ) y

tan(✓)

tan(

f (x) x

f 0 (x)

)


22

Kombinasi linier, kerucut dan konveks Kombinasi linier, kerucut dan konveks Sebuah vektor x 2 Rn dikatakan sebagai I I I

kombinasi linier dari v1 , · · · , vm 2 Rn , jika terdapat { i }m i=1 ⇢ R sehingga P x = i i vi

m kombinasi kerucut dari v1 , · · · , vm 2 Rn , jika P terdapat { i }i=1 ⇢ R dimana untuk setiap i = 1, · · · , m sehingga x = i i vi

i

0

n kombinasi konveks dari v1 , · · · , vm 2 RP , jika terdapat { i }m i=1 ⇢ PR dimana 0 untuk setiap i = 1, · · · , m dan i i = 1 sehingga x = i i vi . i

Selimut linier, kerucut dan konveks Misal V = {v1 , · · · , vm } ⇢ Rn . Maka kita mendefinisikan 8 9 lin(V ) linier < = n cone(V ) := x 2 R : x kombinasi kerucut dari v1 , · · · , vm : ; conv(V ) konveks sebagai selimut linier, selimut kerucut, dan selimut konveks dari V .


23

Kerucut-kerucut Kerucut, Kerucut Polar Misal K , V ✓ Rn . I

Himpunan K dikatakan sebagai kerucut, jika x 2 K untuk setiap x 2 K dan 0.

I

Kerucut polar dari V adalah n o V p := w : v > w  0, 8v 2 V .

Beberapa sifat kerucut polar: V , V1 , V2 ✓ Rn (B1) V p adalah kerucut konveks tertutup. (B2) Jika V1 ✓ V2 maka V1p ◆ V2p . (B3) Jika V 6= ; maka (V p )p = cone(V ). (B4) (V p )p = V jhj V adalah kerucut konveks tertutup

(B5)

⇣

cone(V )

⌘p

= V p.

(B6) Jika V adalah subruang linier di Rn , i.e. v 2 V =) v 2 V , maka V p = V ? := w : v > w = 0, 8v 2 V .


24

Outline



25

Masalah Optimasi Berkendala Masalah Optimasi I

I

Masalah utama yang kita perhatikan dalam compact course ini adalah 8 > <min f (x) (P) s.t. g (x)  0 > : h(x) = 0 dimana f , g , h : Rn ! R, Rp , Rq adalah kontinu Lipschitz lokal. Untuk mempersingkat penulisan biasanya kita menotasikan S := {x 2 Rn : g (x)  0, h(x) = 0} sebagai himpunan semua kendala feasible.

Kendala Aktif Dari semua fungsi kendala ketaksamaan g1 , · · · , gp , kita katakan gi aktif di x ⇤ jika gi (x ⇤ ) = 0. Himpunan semua indeks i sehingga gi aktif di x ⇤ kita notasikan sebagai A(x ⇤ ) := {i : gi (x ⇤ ) = 0}.


26

Arah Feasible dan Arah Penurunan Diberikan x 2 S ✓ Rn dan f : Rn ! R. I I I

Kita katakan d 2 Rn sebagai arah feasible dari x di S, jika terdapat sehingga x + td 2 S untuk setiap t 2 [0, ]. Kita katakan d 2 Rn sebagai arah penurunan f di x, jika terdapat f (x + td) < f (x) untuk setiap t 2 [0, ].

>0 > 0 sehingga

Untuk selanjutnya, himpunan semua arah penurunan f di x dinotasikan sebagai F (x) := {d 2 Rn : 9 > 0, f (x + td) < f (x), 8t 2 [0, ]} .

Lemma Misal f 2 C 2 (Rn ). Maka I I

rf (x)> d  0 untuk setiap d 2 F (x)

jika d 2 Rn memenuhi rf (x)> d < 0, maka d 2 F (x).


27

2 Himpunan Penting ...

Kita definisikan n o D(x) := d 2 Rn : rgi (x)> d  0, rhj (x)> d = 0, i 2 A(x), j = 1, · · · , q dan

C (x) :=

Lemma

8 q <X :

j=1

j hj (x)

+

X

i2A(x)

µi rgi (x) : µi

0, i 2 A(x)

9 = ;

.

Untuk setiap x 2 S, C (x) adalah kerucut konveks tertutup.


28

2 Himpunan Penting ...

Theorem Untuk setiap x 2 S, C (x) = D(x)p .

Proof. I

Cukup buktikan bahwa D(x) = C (x)p .

I

(✓) Berikan c 2 C (x), maka P d 2 D(x) danP d > c = j j d > rhj (x) + i2A(x) µi d > rgi (x)  0. |{z} | {z } | {z } 0

=0

I

p

>

0

(◆) Berikan d 2 C (x) sehingga d c  0 untuk setiap c 2 C (x). Perhatikan !

bahwa rhj dan rhj ada di C (x), sehingga d > rhj = 0. Karena rgi 2 C (x) untuk i 2 A(x), maka d > rgi (x)  0.


29

Kerucut Tangent (tangential cone)

Definisi Sebuah vektor d 2 Rn dikatakan sebagai arah tangent S dari x 2 S, jika d = 0 atau 9(xk )k 2 S sehingga xk ! x dan

xk kxk

x d ! . xk kdk

HImpunan dari semua arah tangent S dari x dinotasikan sebagai T (x) Untuk setiap x 2 S,

(C1) T (x) adalah sebuah kerucut (C2) T (x) tertutup (C3) T (x) dan D(x) adalah 2 aproksimasi linier dari S di x (C4) Jika x ⇤ 2 S adalah lokal minimum dari f di S, maka rf (x ⇤ )> d

0,

8d 2 T (x ⇤ ).


30

Kerucut Tangent (tangential cone) Theorem Untuk setiap x 2 S, T (x) ⇢ D(x).

Proof. I

I

Pilih sebarang d 2 T (x), d 6= 0. Maka terdapat (xk )k ⇢ S dimana xk ! x dan xk x d ! kdk . kxk xk Karena xk , x 2 S dan i 2 A(x), maka hj (xk ) = hj (x) = 0 dan gi (x) = 0 tetapi gi (xk )  0. Dengan kata lain rhj (x)> rgi (x)>

xk kxk

xk kxk

O kxk x + xk kxk

O kxk x + xk kxk

Bagaimana dengan konversnya?

xk2 d k!1 = 0 ! rhj (x)> =0 xk kdk

xk2 d k!1  0 ! rgi (x)>  0. xk kdk

tidak harus berlaku!


31

Teorema Karush–Kuhn–Tucker Theorem Misal x ⇤ adalah minimum lokal dari f di S. Jika T (x ⇤ )p = D(x ⇤ )p , maka terdapat 2 Rq dan µ 2 Rp+ sehingga rf (x ⇤ ) =

q X j=1

µi gi (x ⇤ ) = 0,

j rhj (x

⇤

)+

p X i=1

i = 1, · · · , p.

µi rgi (x ⇤ )

(Lagrange) (Complementary slackness)

Proof. I

x ⇤ minimum lokal, maka

I

⇤ p ⇤ p ⇤ rf (x ⇤ ) 2 T P(x ) = D(x ) =PC (x ) atau rf (x ⇤ ) = qj=1 j rhj (x ⇤ ) + i2A(x ⇤ ) µi rgi (x ⇤ ) ( µi untuk i 2 A(x ⇤ ) Definisikan µi = sehingga 0 untuk i lainnya P P rf (x ⇤ ) = qj=1 j rhj (x ⇤ ) + pi=1 µi rgi (x ⇤ ) dan µi gi (x ⇤ ) = 0, i = 1, · · · , p.

I

!

rf (x ⇤ )> d  0 untuk setiap d 2 T (x ⇤ ).


32

Teorema Karush–Kuhn–Tucker

Kualifikasi kendala (KK) T (x)p = D(x)p secara umum sangat sulit untuk dilihat! + Cari kualifikasi kendala lain yang lebih mudah untuk dilihat, tapi mengakibatkan T (x)p = D(x)p .


33

Beberapa kualifikasi kendala KK1: Quasiregularitas I I I

Didefinisikan dengan ketika T (x) = D(x). maka otomatis T (x)p = D(x)p . Apakah konversnya T (x)p = D(x)p =) T (x) = D(x) berlaku? Contoh: h(x) = x1 x2 dan g (x) = x1 x2 .

tidak harus!.

KK2: Ketentuan Slater I

Didefinisikan dengan ketika g konveks, h linier dan terdapat x¯ 2 S sehingga h(¯ x ) = 0 dan g (¯ x ) < 0.

Theorem (EXERCISE 2) Jika x 2 S memenuhi KK2 (ketentuan Slater), maka x juga memenuhi KK1 (quasiregularitas).


34

Beberapa kualifikasi kendala KK3: Kebebasan linier I

Didefinisikan dengan ketika semua rhj (x) (j = 1, · · · , q) dan rgi (x) (i 2 A(x)) adalah bebas linier.

I

Terlalu kuat!

I

Perhatikan min f (x) = x2 s.t. g1 (x) =

x12 + x2  0, g2 (x) =

x2  0.

KK4: Ketentuan Mangasarian–Fromovitz I

Didefinisikan dengan ketika I I

rh1 (x), · · · , rhq (x) bebas linear 9d 2 Rn sehingga rhj (x)> d = 0 dan rgi (x)> d < 0, i 2 A(x) dan j = 1, · · · , q.

Theorem (EXERCISE 3) Jika x 2 S memenuhi KK3 (kebebasan linear), maka x juga memenuhi KK4 (ketentuan Mangasarian–Fromovitz). Konvers tidak berlaku! Contoh: g1 (x) = (x1 1)2 + (x2 1)2 2, g2 (x) = (x1 1)2 + (x2 + 1)2 2, g3 (x) = x1 dimana x ⇤ = (0, 0) dan d = (1, 0).


35

Beberapa kualifikasi kendala

Theorem (EXERCISE 4) Jika x 2 S memenuhi KK4 (ketentuan Mangasarian–Fromovitz), maka x juga memenuhi KK1 (quasiregularitas).


36

SQP: simple but brilliant ... I

Perhatikan kembali ( (P)

I

minx2S f (x) dimana S = {x 2 Rn : g (x)  0, h(x) = 0} .

Untuk x ⇤ 2 S lokal minimum dan T (x ⇤ )p = D(x ⇤ )p , maka terdapat µ 2 Rp+ sehingga rL(x ⇤ , µ, ) := rf (x ⇤ ) +

q X j=1

j rhj (x

⇤

)+

p X i=1

2 Rq dan

µi rgi (x ⇤ ) = 0 µi gi (x ⇤ ) = 0,

i = 1, · · · , p.

Ide SQP Cari solusi dari

0

1 rL(x, µ, ) (x, µ, ) := @ diag(µ) g (x) A = 0. h(x)


37

Menuju SQP ...

I

Metode Newton

I

nonsingular! Dengan demikian perlu I

perlu r

0

r2xx L = @ diag(µ) rg (x) rh(x)>

r2xµ L> diag(g (x)) 0

1 r2x L> A 0 0

x memenuhi KK3 – kebebasan linear dari kolom-kolom G (x) := rh1 (x), · · · , rhq (x), rgi1 (x), · · · , rgis (x) | {z } ij 2A(x)

I

r2xx L definit positif di ruang nul G > , yakni dr2xx Ld > 0,

8d 6= 0 sehingga G > d = 0.

I

Bukti?

I

Ada kalanya dalam iterasi Newton, x terlalu dekat dengan singularitas r kalkulasi r2xx L menjadi ”sangat mahal”.

I

SQP

jangan kalkulasi r2xx L, ganti dengan B.


38

Langkah–langkah SQP I I

Definisikan x (k) := x (k+1) x (k) , µ(k) := µ(k+1) dan r (x, µ, ) = r (x, µ, , B).

µ(k) ,

(k)

:=

(k+1)

(k)

Metode Newton

r (x (k) , µ(k) ,

(k)

, Bk )>

⇣

x (k) ,

µ(k) ,

(k)

⇣

x (k) ,

µ(k) ,

(k)

Sequential Quadratic Programming r (x (k) , µ(k+1) ,

(k+1)

, B k )>

⌘>

=

(x (k) , µ(k) ,

(k)

⌘>

=

(x (k) , µ(k) ,

(k)

)

)

dimana harus terpenuhi ⇣

⌘

⇣

⌘

⇣

g x (k+1) ⇡ g x (k) + rg x (k)

⌘>

µ(k+1)

0

x (k)  0

)

(D1)


39

Langkah–langkah SQP I

I

I

Dengan merombak SQP, kita mendapatkan ⇣ ⌘ ⇣ ⌘ P (k+1) rf x (k) + Bk x (k) + pi=1 i rgi x (k) = 0 ⇣ ⌘ ⇣ ⌘ ⇣ ⌘> diag µ(k+1) g x (k) + rg x (k) x (k) = 0 ⇣ ⌘ ⇣ ⌘> h x (k) + rh x (k) x (k) = 0

9 > > > = > > > ;

(D2)

Lihat bahwa (D1) dan (D2) adalah kondisi Karush–Kuhn–Tucker untuk masalah optimasi kuadrat ⇣ ⌘ 8 (k) > y + y > Bk y s.t. >miny 2Rn rf x > < ⇣ ⌘ ⇣ ⌘> (Qk ) g x (k) + rg x (k) y 0 > ⇣ ⌘ ⇣ ⌘ > > :h x (k) + rh x (k) > y = 0. Update Bk dengan quasi–Newton: ⇣ ⌘ ⇣ Bk+1 x (k+1) x (k) = rL x (k+1) , µ(k+1) , | {z } | x (k) =:v


(k+1)

⌘

{z

=:w

⇣ rL x (k) , µ(k+1) ,

(k+1)

⌘

.

} 40

,

Langkah–langkah SQP I I

Kita formulasikan Bk+1 = Bk + Uk dimana Uk adalah matrix dengan rank 1 atau 2 sehingga jika Bk definit positif, maka Bk+1 juga definit positif. 3 kemungkinan solusi untuk Uk UkPSB :=

(w

Bk v )v > + v (w v >v

ww > Bk vv > Bk > v w v > Bk v (w Bk v )w > + w (w := w >v

Bk v )>

(w

B k v )> v > vv (v > v )2

UkBFGS := UkDFP I I I

B k v )>

(w

B k v )> v ww > . (w > v )2

PSB–update tidak menjamin Bk+1 definit positif. Jika v > w > 0 dan Bk positif definit, maka DFP– dan BFGS–update menghasilkan Bk+1 positif definit. Jika r2xx L tidak positif definit, maka kondisi v > w > 0 tidak terpenuhi.

Theorem Jika asumsi-asumsi untuk non-singularitas r terpenuhi, maka SQP dengan BFGS–update akan konvergen lokal dengan kecepatan superlinier.


41

SQP: Algorithm

Step 0 Choose x (0) and (µ(0) , (0) ) where µ(0) > 0; a symmetric matrix B0 ⇡ r2x L(x (0) , µ(0) , (0) ); error tolerance ✏ > 0 and = ✏ + 1; k = 0. Step 1 While ✏ (1.a) (1.b) (1.c) (1.d)

Solve Qk to obtain ( x, µ, ) Set x (k+1) = x (k) + x and (µ(k+1) , Compute Bk+1 Set := k xk (or := f (x (k+1) )

(k+1) )

= (µ, )

f (x (k) ) )


42

Workshop Memecahkan Masalah Kendali Optimal dengan Metode Langsung

Recommend Documents