ANALISIS PERSOALAN OPTIMISASI KONVEKS DUA TAHAP (TWO-LEVEL)

ANALISIS PERSOALAN OPTIMISASI KONVEKS DUA TAHAP (TWO-LEVEL)

TESIS

Oleh

LASKER PANGARAPAN SINAGA 077021005/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009

Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

ANALISIS PERSOALAN OPTIMISASI KONVEKS DUA TAHAP (TWO-LEVEL)

TESIS

Diajukan Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

LASKER PANGARAPAN SINAGA 077021005/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009


Judul Tesis

: ANALISIS PERSOALAN OPTIMISASI KONVEKS DUA TAHAP (TWO-LEVEL) Nama Mahasiswa : Lasker Pangarapan Sinaga Nomor Pokok : 077021005 Program Studi : Matematika

Menyetujui, Komisi Pembimbing

(Dr. Tulus, M.Si) Ketua

(Prof. Dr. Herman Mawengkang) Anggota

Ketua Program Studi,

Direktur,

(Prof. Dr. Herman Mawengkang)

(Prof. Dr. Ir. T.Chairun Nisa. B, M.Sc)

Tanggal lulus: Juni 2009


Telah diuji pada Tanggal Juni 2009

PANITIA PENGUJI TESIS Ketua

: Dr. Tulus, M.Si

Anggota

: 1. Prof. Dr. Herman Mawengkang 2. Dr. Sutarman, M.Sc 3. Drs. Marwan Harahap, M.Eng


ABSTRAK Persoalan program konveks dua tahap merupakan alat yang bermanfaat untuk memecahkan permasalahan keputusan yang hirarkis. Program ini menggunakan persoalan optimisasi dengan dua level yang hirarkis, dimana pengambil keputusan pada level lebih tinggi (upper) dan level lebih rendah (lower) masingmasing mempunyai kendala dan fungsi tujuan berupa fungsi konveks. Pembuat keputusan pada level lower harus mengoptimalkan fungsi tujuan di bawah parameter yang diberikan oleh level upper. Tesis ini menunjukkan bahwa persoalan di atas dapat dipecahkan dengan menggunakan kombinasi dari Metode Proyeksi Gradien dan Metode Penalty, dengan membuat level lower berfungsi sebagai fungsi penalty dari himpunan yang layak, untuk menunjukkan regulerisasi. Proses regulerisasi ini dibutuhkan untuk menunjukkan analisis konvergensi barisan solusi terbatas yang dibangkitkan metode tersebut. Kata kunci : Optimisasi konveks, metode proyeksi gradien, metode penalty.

i Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

ABSTRACT The two level convex programming problems are useful tools for solving the hierarchy decision problems. This programming problems are nested optimization problems with two levels in a hierarchy, the upper level and lower level decision makers who have their own objective functions and constraints are convex function. The decision maker at the lower level has to optimize its own objective function under the given parameters from the decision maker at the upper level. This paper will show that the above problem can be solved by using combination of Gradient Projection Method and Penalty Method, corresponding to taking the lower level function as penalty function of feasible set, for showing regularization. Some regularity process is needed for showing convergence analysis of generated bounded sequence of solutions of that methods. Keywords : Convex optimization, gradient projection method, penalty method.

ii Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

KATA PENGANTAR

Tesis ini berjudul Analisis Persoalan Optimisasi Konveks Dua Tahap (Analysis of Two Level Convex Optimization Problems). Tesis

ini

disusun

sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Program Studi Magister Matematika, Sekolah Pascasarjana, Universitas Sumatera Utara. Penelitian ini diharapkan dapat bermanfaat dalam membantu menyelesaikan berbagai persoalan optimisasi dua tahap bersifat konveks dengan memperlihatkan proses penganalisisan kekonvergenan solusinya. Penulis sangat sadar bahwa tesis ini masih jauh dari sempurna, namun besar harapan bahwa tesis ini bermanfaat bagi para pembaca dan pada pengembangan penelitian di bidang Operasi Riset.

Medan,

Juni 2009

Penulis,

Lasker Pangarapan Sinaga

iii Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

UCAPAN TERIMA KASIH

Pertama penulis panjatkan puji dan syukur kepada Tuhan Yang Maha Esa, karena atas berkat, kasih dan karunia-Nya yang telah diberikan kepada penulis, sehingga penulis dapat menyelesaikan tesis ini tepat pada waktunya. Tesis ini berjudul ”Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level)”. Tesis ini merupakan persyaratan tugas akhir pada Program Studi Matematika Sekolah Pascasarjana Universitas Sumatera Utara. Pada kesempatan ini, penulis menyampaikan ucapan terima kasih dan penghargaan yang sebesar-besarnya kepada: Prof. dr. Chairuddin P. Lubis, DTM&H, Sp.A(K) selaku Rektor Universitas Sumatera Utara. Prof. Dr. Ir. T. Chairun Nisa B, M.Sc selaku Direktur Sekolah Pascasarjana Universitas Sumatera Utara yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana, Universitas Sumatera Utara. Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister Matematika, Sekolah Pascasarjana, Universitas Sumatera Utara; Dr. Saib Suwilo, M.Sc selaku Sekretaris Program Studi Magister Matematika, Sekolah Pascasarjana, Universitas Sumatera Utara, yang telah banyak membantu dalam penulisan tesis ini. Dr. Tulus, M.Si selaku Ketua Komisi Pembimbing yang sangat banyak membantu penulis dengan banyak memberikan ilmu dalam penulisan tesis ini.

iv Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

Dosen-dosen Magister Matematika, Sekolah Pascasarjana, Universitas Sumatera Utara : Prof. Dr.

Dr.

Herman Mawengkang, Dr.

Tulus, M.Si, Prof.

Saib Suwilo, M.Sc,

Opim Salim S, M.Sc, Phd, Drs. Marwan

Harahap, M.Eng, Dr. Sutarman, M.Sc, Drs. Open Darnius, M.Sc, Drs. Sawaluddin, MIT, Dra. Mardiningsih, M.Si, Dra. Esther Nababan, M.Sc, yang telah banyak memberikan masukan ilmu pengetahuan dalam konsentrasi Matematika Operasi Riset (OR). Seluruh rekan mahasiswa angkatan ke-6 (2007-2008) Program Studi Magister Matematika, Sekolah Pascasarjana USU, atas kebersamaanya selama perkuliahan. Seluruh pegawai Sekolah Pascasarjana Universitas Sumatera Utara, secara khusus kepada Misiani, S.Si, selaku staf administrasi Program Studi Magister Matematika, yang banyak membantu penulis dalam berbagai urusan administrasi selama perkuliahan. Pimpinan SSC-Medan, Ronald Backer Simanjuntak, yang memberikan waktu bagi penulis untuk melanjutkan perkuliahan, dan juga kepada seluruh rekan pengajar dan pegawai SSC-Medan atas kerjasamanya selama ini. Secara khusus, kepada orang tua penulis: Edison Sinaga dan Relianna Saragih Sumbayak, dan kepada mertua: Budiman Damanik dan Pittauli Purba, serta kedua saudara penulis (Nenny D Sinaga dan David Saragih, Aditia Irving Saragih) dan Selpiani Sinaga, S.E. yang memberikan dukungan doa kepada penulis.

v Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

Teristimewa kepada istri tercinta Fitri Yanti Damanik, S.E. yang banyak memberikan pengertian dan dukungan sepanjang waktu. Ucapan terima kasih kepada seluruh keluarga dan rekan-rekan yang tidak dapat penulis sebutkan namanya satu persatu pada kesempatan ini, atas dukungan doa yang diberikan sehingga penulis dapat menyelesaikan pendidikan ini. Akhirnya penulis berharap semoga tesis ini dapat bermanfaat bagi pembaca dan pihak-pihak lain yang memerlukannya.

Medan,

Juni 2009

Penulis,

Lasker Pangarapan Sinaga

vi Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

RIWAYAT HIDUP

Lasker Pangarapan Sinaga dilahirkan di Merek Raya (Simalungun) pada tanggal 02 Agustus 1979 dan merupakan anak ke-2 dari 3 orang bersaudara dari Ayah Edison Sinaga dan Ibu Relianna Saragih Sumbayak. Menamatkan Sekolah Dasar (SD) Inpres Sihubu di Merek Raya pada tahun 1992, Sekolah Menengah Pertama (SMP) Negeri 3 Merek Raya pada tahun 1995 dan Sekolah Menengah Umum (SMU) Negeri 1 (Plus Partuha Maujana Simalungun Angkatan I) pada tahun 1998. Tahun 1998 memasuki Perguruan Tinggi Negeri Universitas Sumatera Utara, Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA), Jurusan Matematika dan memperoleh gelar sarjana pada tahun 2003. Pada Tahun 2003 bekerja sebagai tenaga pengajar Matematika SSC Medan. Tahun 2007 mengikuti pendidikan Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara. Tahun 2008 menikah dengan Fitri Yanti Damanik, S.E.

vii Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .

iii

UCAPAN TERIMA KASIH . . . . . . . . . . . . . . . . . . . . . .

iv

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

viii

DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . .

x

DAFTAR SIMBOL . . . . . . . . . . . . . . . . . . . . . . . . . .

xi

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Rumusan Masalah . . . . . . . . . . . . . . . . . . . . .

4

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .

4

1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . .

5

1.5 Metode Penelitian . . . . . . . . . . . . . . . . . . . . .

5

BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .

7

BAB 3 KONTINUITAS DAN KONVEKSITAS . . . . . . . . . . . .

11

3.1 Analisis Matematika . . . . . . . . . . . . . . . . . . . .

11

3.1.1 Fungsi Kontinu dan Fungsi Lipschitz . . . . . . . . .

11

3.1.2 Barisan (Sequence) . . . . . . . . . . . . . . . . .

13

3.2 Konveksitas Himpunan dan Fungsi . . . . . . . . . . . . .

14

3.2.1 Himpunan Konveks . . . . . . . . . . . . . . . . .

15

viii Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

3.2.2 Fungsi Konveks . . . . . . . . . . . . . . . . . . .

17

BAB 4 OPTIMISASI KONVEKS DAN OPTIMISASI DUA TAHAP SERTA METODE PROYEKSI GRADIEN . . . . . . . . . . .

21

4.1 Optimisasi Konveks . . . . . . . . . . . . . . . . . . . .

22

4.2 Optimisasi Dua Tahap . . . . . . . . . . . . . . . . . . .

24

4.3 Metode Steepest Descent

26

. . . . . . . . . . . . . . . . .

4.4 Algoritma Proyeksi Gradien (Gradient Projection Algorithms)

27

4.5 Analisis kekonvergenan Metode Proyeksi Gradien . . . . . .

31

BAB 5 PEMBAHASAN

. . . . . . . . . . . . . . . . . . . . . . .

36

5.1 Formulasi Optimisasi Konveks Dua Tahap . . . . . . . . .

36

5.2 Regulerisasi Optimisasi Konveks Dua Tahap . . . . . . . .

37

5.3 Kondisi Optimal dari Solusi . . . . . . . . . . . . . . . .

42

5.4 Algoritma Proyeksi Gradien dan Analisis Kekonvergenan Solusi Optimisasi Konveks Dua Tahap . . . . . . . . . . . .

43

BAB 6 KESIMPULAN DAN SARAN . . . . . . . . . . . . . . . . .

52

6.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . .

52

6.2 Saran . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .

53

ix Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

DAFTAR GAMBAR

Nomor

Judul

Halaman

3.1

Implementasi secara geometri fungsi kontinu . . . . . . . . .

12

3.2

Konveks dan tidak konveks . . . . . . . . . . . . . . . . .

15

3.3

Polihedron P dengan irisan dari lima buah halfspaces dengan vektor normal a1, . . . , a5 . . . . . . . . . . . . . . . . . . .

15

Sebuah convex cone: untuk setiap titik x1 , x2 ∈ C dan untuk setiap 0 ≤ θ ≤ 1 maka θx1 + (1 − θ)x2 ∈ C . . . . . . . . . .

16

3.5

Sebuah hyperlane dengan dua halfspaces . . . . . . . . . . .

16

3.6

Sebuah ellipsoid dalam R2 . . . . . . . . . . . . . . . . . .

16

3.7

Fungsi Konveks dan Fungsi Tidak Konveks . . . . . . . . . .

17

3.8

Jika f fungsi terdifferensialkan dan x , y ∈ dom f, maka f (y) ≥ f (x) + ∇f (x)T (y − x) . . . . . . . . . . . . . . . .

18

4.1

Ilustrasi solusi global dan lokal . . . . . . . . . . . . . . . .

23

4.2

Contoh ilustrasi metode proyeksi gradien . . . . . . . . . . .

30

5.1

Himpunan solusi upper atau solusi optimisasi Su adalah bagian dari solusi lower Sl . . . . . . . . . . . . . . . . . . . . .

37

Ilustrasi sederhana minimisasi Fσ (xu , xl ) dengan domain Su pada optimisasi konveks dua tahap . . . . . . . . . . . . . . . .

40

5.3

Interpretasi kondisi optimal . . . . . . . . . . . . . . . . .

42

5.4

Ilustrasi solusi optimal pada Optimisasi Konveks Dua Tahap .

49

3.4

5.2

x Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

DAFTAR SIMBOL

∅

: Himpunan kosong

f

: Fungsi

C

: Himpunan konveks

fu

: Fungsi objektif level upper

K

: Konstanta Lipschitz

fl

: Fungsi objektif level lower

R

: Bilangan Riel

gu

: Fungsi kendala level upper

N

: Bilangan Asli

gl

: Fungsi kendala level lower

Rn

: Ruang Euklidis n

Su

: Himpunan solusi level upper

∀

: Untuk setiap

Sl

: Himpunan solusi level lower

∃

: Terdapat/beberapa

x ¯

: Titik kumpul (cluster point)

→

: Mendekati/menuju

k.k

: Norm(2)

⊆

: Subset

h·, ·i

: Inner product

⊂

: Proper subset

aT

: Transpose a

{xk }

: Barisan solusi x

Df(x) : Differensial f (x)

Min

: Minimize

f 0 (x)

Max

: Maksimum

∇f (x) : Gradien

Inf

: Infimum

PC (x)

: Proyeksi orthogonal pada C

Dist

: Distance

Fσ (x)

: Regulerisasi F (x)

Dom

: Domain

f¯u

: inf{fu (x)}

Lim

: Limit

f¯l

: min{fl (x)}

xu

: Variabel level upper

Arg

: argumen

xl

: Variabel level lower

L(c)

: Fungsi level

: Differensial f (x)

xi Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

BAB 1 PENDAHULUAN

1.1 Latar Belakang Masalah selalu dihadapi terus menerus di dalam kehidupan, sehingga setiap orang dituntut untuk mencari solusi yang tepat dan cepat untuk menyelesaikan setiap masalah tersebut. Setiap solusi yang diambil merupakan keputusan akhir yang harus diambil seseorang dengan atau tanpa pertimbangan. Setiap pertimbangan seharusnya benar-benar dipikirkan oleh pengambil keputusan. Hal ini dilakukan demi mengurangi risiko yang akan terjadi akibat keputusan yang diambil tersebut. Ini bukanlah sebuah permasalahan yang mudah untuk diselesaikan, karena keputusan yang tepat harus secepat mungkin diputuskan. Tentu jelas sekali bahwa pengambil keputusan harus dapat menentukan keputusan terbaik untuk mengatasi masalah yang sedang dihadapi secepat mungkin dengan tanpa menimbulkan masalah yang lain akibat keputusan tersebut. Ilmu matematika, secara khusus konsentrasi operasi riset (Research Operation) telah menanggapi dan berperan aktif dalam mengatasi masalah pengambilan keputusan seperti permasalahan pengambil keputusan di atas. Persoalan pengambilan keputusan sering diformulasikan sebagai persoalan optimisasi. Optimisasi matematika akan memodelkan berbagai kasus masalah dan mencari cara atau metode yang tepat dan cepat untuk menyelesaikannya. Optimisasi matematika ditujukan pada metode untuk mendapatkan suatu solusi yang optimal. Pusat permasalahannya adalah mendapatkan solusi yang memaksimumkan suatu fungsi tujuan atau meminimumkan risiko. 1 Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

2 Secara matematis, permasalahan optimisasi adalah sebuah abstraksi masalah untuk mengambil sebuah pilihan vektor terbaik di Rn dari sekumpulan pilihan vektor yang ada. Vektor terbaik berarti vektor yang dapat menjadi solusi dari permasalahan optimisasi yang diberikan, yaitu solusi optimal yang memenuhi fungsi tujuan dan kendala dari permasalahan optimisasi tersebut. Boyd dan Vandenberghe (2004). Penelitian lebih lanjut menyatakan bahwa keputusan yang telah diambil memang diharapkan dapat menyelesaikan persoalan yang sedang dihadapi tetapi sering tidak terpikirkan bahwa keputusan tersebut dapat menyebabkan masalah dibagian yang lain. Keputusan yang baik adalah keputusan yang dapat menyelesaikan permasalahan bersangkutan pada saat ini dan tidak menyebabkan permasalahan berikutnya di bagian yang lain. Kejadian seperti ini menstimulus munculnya bentuk optimisasi multi tahap. Optimisasi ini diharapkan dapat membantu si pembuat keputusan dalam mengambil keputusan yang terbaik dalam berbagai kasus berbentuk optimisasi dua tahap dalam kehidupan sehari-hari. Bard, Plummer dan Sourie (1998). Optimisasi dua tahap (Two Level Optimization) adalah bentuk optimisasi multitahap dengan dua tahap. Sebuah himpunan yang memuat variabel yang menjadi solusi awal dari masalah optimisasi ini akan menjadi parameter untuk variabel lainnya. Hal ini berarti ada proses dua tahap (Level Upper dan Level Lower) yang dilakukan yaitu dengan setiap keputusan pada level upper atau outer problem maka ditentukan keputusan pada lower problem atau inner problem. Ye (1999).


3 Secara umum, optimisasi dua tahap dituliskan dengan bentuk: (Level upper) Minimizexu ,xl fu (xu , xl)

(1.1)

s. t.

(1.2)

gu (xu ) ≤ 0

(Level lower) Minimizexl fl (xu , ·)

(1.3)

s.t.

gl (xu , ·) ≤ 0

(1.4)

xu , xl ≥ 0

(1.5)

dengan xu ∈ Rn , xl ∈ Rn ; fu , fl : Rn × Rn → R

(1.6)

gu : Rn → R ; gl : Rn × Rn → R

(1.7)

Vicente (1997) dan lihat juga Wang, Wan dan Lv (2008). Jika untuk setiap nilai dari variabel upper maka didefinisikan himpunan solusi yang meminimumkan kendala pada level lower yang bergantung pada solusi level upper. Misalkan Su adalah himpunan solusi level upper dan Sl adalah himpunan solusi level lower maka solusi dari bentuk optimisasi dua tahap di atas dapat diformulasikan dengan himpunan solusi berikut: S(xu , xl) ∈ Rn × Rn = {(xu , xl)|Su ∩ Sl )} Chio (2004) dan Audet, Haddad dan Savard (2006).


(1.8)

4 Seorang matematikawan, Chris Fricke dari Departemen Matematika dan Statistika, Universitas Melbourne menjelaskan tentang optimisasi dua tahap tersebut. Dia menerangkan bahwa perhitungan secara manual terhadap beberapa kasus optimisasi dua tahap tidak menjamin keoptimalan solusi. Dengan demikian perlu dilakukan penganalisisan yang lebih lanjut terhadap kasus ini untuk menunjukkan keoptimalan solusi dengan konvergensi barisan solusi oleh suatu algoritma dan metode penalty.

1.2 Rumusan Masalah Misalkan domain dan fungsi tujuan serta kendala pada bentuk optimisasi dua tahap (1.1-1.7) dibatasi dengan bersifat konveks untuk masing masing level, maka diperoleh kelas optimisasi yang lebih khusus yaitu optimisasi konveks dua tahap (Two Level Convex Optimization). Permasalahannya adalah bagaimana memformulasi atau memodelkan optimisasi konveks dua tahap tersebut ke bentuk yang sederhana dengan regulerisasi dan menunjukkan penganalisisan kekonvergenan solusi dari barisan solusi layak yang dibangkitkan oleh sebuah algoritma untuk menunjukkan keoptimalan solusi. Proses ini memerlukan definisi, sifat dan teorema yang mendukung.

1.3 Tujuan Penelitian Optimisasi konveks dua tahap mempunyai dua himpunan solusi yaitu himpunan solusi level lower dan himpunan solusi level upper. Kedua himpunan solusi tersebut adalah terbatas dan mempunyai titik kluster. Tujuan penelitian


5 ini adalah menunjukkan keoptimalan solusi optimisasi konveks dua tahap dengan memperlihatkan bahwa apakah kedua titik kumpul pada kedua himpunan solusi tersebut adalah titik yang sama atau berbeda.

1.4 Kontribusi Penelitian Penelitian ini memberikan teori tentang penganalisaan optimisasi konveks multitahap dengan pembatasan masalah pada dua tahap dan menyelesaikannya dengan sebuah metode serta memberikan jaminan teori dalam memperlihatkan keoptimalan solusi layak dengan suatu regulerisasi dan analisis kekonvergenan solusi, sehingga sangat diharapkan dapat berguna untuk membantu dalam menyelesaikan berbagai kasus optimisasi pada lingkungan operasi riset atau teknik.

1.5 Metode Penelitian Penelitian ini dikerjakan dengan metode literatur dengan tahapan pelaksanaannya sebagai berikut: 1. Menjelaskan secara teori tentang konveksitas himpunan dan fungsi. 2. Menunjukkan bentuk optimisasi konveks dan optimisasi dua tahap. 3. Memformulasi bentuk optimisasi konveks dua tahap dan melakukan regulerisasi fungsi dengan regulerisasi Tikhonov serta fungsi penalty. 4. Menganalisis konveksitas fungsi terregulerisasi dan eksistensi solusi dengan menggunakan algoritma proyeksi gradien serta melakukan penganalisisan kekonvergenannya pada kedua level (upper dan lower).


6 5. Menganalisis titik kluster pada kedua level dan menunjukkan apakah kedua titik kluster tersebut sama atau berbeda.


BAB 2 TINJAUAN PUSTAKA

Optimisasi konveks adalah sebuah kelas optimisasi yang mempunyai domain fungsi dan fungsi objektif serta fungsi kendala yang bersifat konveks. Dilihat dari segi modelnya maka optimisasi konveks jelas bersifat lebih umum daripada optimisasi linear. Hal ini dijelaskan oleh Boyd dan Vandenberghe (2004). Kemudian, jika ditinjau dari segi analisis kekontinuan fungsi tujuan dan kendalanya maka jika f merupakan fungsi konveks maka f adalah Lipschitz lokal sekitar titik elemen domainnya jika dan hanya jika terbatas pada lingkungan titik tersebut. Hal ini telah dijelaskan oleh Borwein dan Lewis (1999). Suatu masalah optimisasi dengan kasus minimisasi tidak berkendala dengan fungsi objektif bersifat konveks, maka metoda steepest descent akan mempunyai sifat kekonvergenan yang lebih kuat daripada masalah minimisasi dengan fungsi tujuan yang bersifat nonkonveks. Konveksitas domain fungsi pada optimisasi membuat proyeksi orthogonal sangat memungkinkan digunakan dalam menunjukkan arah yang layak dan descent, yaitu arah pergerakan gradien disetiap iterasi, oleh Iusem (2003). Hal ini terjadi karena metode proyeksi gradien meminimisasi sebuah fungsi terdifferensialkan dan kontinu f : Rn → R atas himpunan konveks tak kosong dan tertutup C ⊂ Rn yang telah dijelaskan sebelumnya oleh Calamai dan More (1987). Algoritma atau metode pendekatan adalah cara terbaik untuk menyelesaikan kasus optimisasi nonlinear. Berbagai algoritma untuk mendapatkan solusi opti-

7 Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

8 misasi yang berkaitan dengan proyeksi telah dikembangkan, yaitu metode proyeksi gradien oleh Rosen dapat dilihat pada Iusem (2006) dan metode proyeksi gradien konjugasi, metode proyeksi gradien Quasi-Newton dan metode proyeksi gradien Rosen-ParTan (Parallel Tangents) oleh Chio (2004). Metode proyeksi gradien adalah sebuah generalisasi dari metode descent, dimana gradien negatif diproyeksikan pada daerah terbatas dan mencari solusi di sepanjang kurva. Luenberger (1974). Metode proyeksi gradien ini diperkenalkan pertama sekali oleh Rosen (1960) dan digunakan untuk menyelesaikan program nonlinear (Nonlinear Programming). Metode ini bekerja dengan membangkitkan sebuah barisan solusi-solusi layak yang konvergen ke solusi optimal, oleh Zhu dan Zhang (2006). Bentuk analisis kekonvergenan metode ini juga telah dijelaskan oleh Calamai (1987). Selain metode proyeksi gradien, ada sebuah metode lain yang digunakan untuk menyelesaikan program nonlinear yaitu metode fungsi penalty. Metode ini digunakan dengan prosedur descent orde pertama yaitu steepest descent, Luenberger (1974). Kedua metode ini selalu digunakan sebagai kombinasi yang serasi karena metode proyeksi gradien mempunyai proses kekonvergenan yang cukup lambat, sehingga dengan kombinasi tersebut, proses kekonvergenan dapat dicapai dengan cepat, oleh Zhu dan Zhang (2006). Dengan demikian, tujuan dari setiap algoritma jelas untuk mendapatkan bentuk kekonvergenan solusi dengan lebih cepat. Sebagai contoh, proses minimisasi yang berhubungan dengan masalah gradien yang dijelaskan oleh Polak, Sargent dan Sebastian (1974).


9 Sehubungan dengan masalah kekonvergenan dari metode iteratif di atas maka pendekatan regulerisasi (Tikhonov Regulerization) pada fungsi tujuan sangat perlu dilakukan untuk menunjukkan kekonvergenan barisan solusi yang dibangkitkan algoritma pada optimisasi konveks, hal ini dijelaskan oleh Ali (2005). Dari uraian diatas, perkembangan ilmu matematika berbanding lurus dengan perkembangan masalah optimisasi serta metode-metode penyelesaiannya. Sebagai contoh adalah kelas optimisasi dua tahap. Metode proyeksi gradien juga digunakan dalam menyelesaikan optimisasi dua tahap (Bilevel Optimization) oleh Solodov (2007). Kelas optimisasi dua tahap ini menampilkan aksi Leader-Follower dalam membantu mengambil keputusan (Decision Making), oleh Bard, Plummer dan Sourie (1998) dan Ye (1999). Masalah program dua tahap adalah suatu masalah optimisasi dimana kendala secara implisit ditentukan oleh masalah optimisasi yang lain. Dengan kata lain, suatu optimisasi hirarkis yang terkandung dalam dua level. Di level pertama, pembuat keputusan (pemimpin) harus memilih pertama suatu strategi x untuk meminimumkan fungsi sasaran, dan pembuat keputusan pada level kedua (pengikut) harus memilih suatu strategi y untuk meminimumkan fungsi sasarannya sendiri yang diparameteri x. Mengantisipasi reaksi dari pengikut, maka pemimpin harus menemukan nilai-nilai variabelnya yang memenuhi sasarannya dan juga memenuhi sasaran pengikutnya, oleh Ankhili dan Mansouri (2008). Kondisi kelambanan dari level lower dimasukkan ke sasaran level upper dengan suatu penalty. Kemudian menguraikan program dua level yang linier ke dalam satu barisan program linier dan mendapatkan solusi optimal, Solodov (2007).


10 Program dua tahap dapat diformulasi lebih sederhana dan analisis keberadaan solusi dengan menggunakan metode penalty yaitu dengan membuat level lower sebagai penalty. Hal ini dijelaskan oleh Lv, et all (2007) serta Aboussoror dan Mansouri (2005).


BAB 3 KONTINUITAS DAN KONVEKSITAS

3.1 Analisis Matematika Analisis matematika membicarakan masalah kekontinuan suatu fungsi dan kekonvergenan suatu barisan. Demikian halnya dengan analisis optimisasi berikut, akan membicarakan tentang keoptimalan solusi dengan memperhatikan kekontinuan fungsi serta kekonvergenan barisan solusi yang dibangkitkan oleh suatu algoritma. Pada bagian ini akan dijelaskan beberapa definisi ataupun teorema yang mendukung penganalisisan konveksitas sebuah fungsi dan kekontinuan serta kekonvergenan solusi layaknya, yang akan mendukung pembahasan pada bab berikutnya. Seperti operator norm, kekontinuan seragam, fungsi Lipschitz dan barisan terbatas dan lain-lain.

3.1.1 Fungsi Kontinu dan Fungsi Lipschitz

Definisi 3.1.1 Norm adalah operator yang disimbolkan dengan k.k, yaitu sebuah ukuran panjang dari dua buah vektor x1, x2 ∈ A ⊆ Rn , sehingga: dist(x1, x2) = kx1 − x2k dan dist(x1, A) = inf kx1 − x2k , ∀x2 ∈ A


12 Definisi 3.1.2 Sebuah himpunan A ⊂ R disebut himpunan terbuka jika dan hanya jika untuk setiap x ∈ A terdapat lingkungan Q dari x sedemikian sehingga Q ⊂ A.

Definisi 3.1.3 Sebuah fungsi f : Rn → Rm adalah kontinu pada x1 ∈ dom f jika untuk setiap ε > 0 terdapat δ > 0 sedemikian sehingga: x2 ∈ dom f kx2 − x1 k < δ ⇒ kf (x2 ) − f(x1 )k < ε

Misalkan saja lim f(x) = L (ada) sedemikian implementasi definisi di atas dapat x→c

dijelaskan kembali secara geometri pada gambar di bawah ini:

Gambar 3.1 : Implementasi secara geometri fungsi kontinu

Definisi 3.1.4 Sebuah fungsi f : A → R disebut fungsi kontinu seragam pada A ⊆ R jika dan hanya jika untuk setiap ε > 0 terdapat δ(ε) > 0 sedemikian: x1 , x2 ∈ A maka |x1 − x2| ≤ δ(ε) ⇒ |f (x1 ) − f(x2)| < ε


13 Definisi 3.1.5 (Fungsi Lipschitz) Misalkan A ⊂ R dan f : A → R disebut fungsi Lipschitz jika terdapat K > 0 sedemikian sehingga: kf (x1 ) − f(x2 )k ≤ K kx1 − x2 k , ∀x1, x2 ∈ A

Teorema 3.1.1 Jika f : A → R adalah fungsi Lipschitz maka f adalah fungsi kontinu seragam pada A.

Bukti:

Jika kondisi fungsi Lipschitz f : A → R dipenuhi dengan konstanta

K > 0, kemudian diberikan ε > 0 dan mengambil δ(ε) = ε/K sedemikian sehingga untuk setiap x1, x2 ∈ A memenuhi kx1 − x2 k ≤ δ(ε) ⇒ kf (x1 ) − f(x2 )k < K.ε/K = ε

3.1.2 Barisan (Sequence)

Definisi 3.1.6 Sebuah barisan bilangan riel R adalah sebuah fungsi pada himpunan bilangan asli N dimana hasilnya berada dalam R.

¯ jika Definisi 3.1.7 Sebuah barisan {xn }∞ n=1 konvergen ke sebuah bilangan riel x dan hanya jika ∀ε > 0 terdapat sebuah bilangan bulat n ≥ N sedemikian sehingga: ¯| < ε |xn − x

Definisi 3.1.8 Misalkan {xn } adalah sebuah barisan dalam X. Sebuah

titik

x ¯ ∈ X disebut titik kumpul (cluster point) dari barisan {xn } jika dan hanya jika, untuk setiap lingkungan V , himpunan {n : xn ∈ V } adalah tak berhingga.


14 Definisi 3.1.9 Sebuah barisan {xn } disebut terbatas jika terdapat sebuah bilangan riel K > 0 sedemikian sehingga ∀n ∈ N, kxn k ≤ K.

Teorema 3.1.2 (Bolzano-Weierstrass) Setiap barisan terbatas di R mempunyai sebuah sub-barisan yang konvergen.

Bukti: Misalkan {xn } adalah sebuah barisan terbatas di Rm dan ∀n ∈ N , (n)

(n)

(n)

kxn k ≤ K. Kemudian, untuk setiap n, misalkan juga xn = (x1 , x2 , . . . , xm ). (n)

Barisan {x1 } adalah sebuah barisan pada bilangan riel dan karena ∀n ∈ N ,

(n)

x1 ≤ kxn k ≤ K maka barisan tersebut adalah barisan terbatas. o n n (k) adalah barisan yang konvergen, sedemikian Pilih sebuah sub-barisan x1 1

n o

n1 (k) n (k) adalah barisan yang terbatas se x2 ≤ xn1 (k) ≤ K dimana x2 2 o n n (k) adalah sub-barisan dari barisan konvergen hingga konvergen. Karena x1 2 n o n (k) x1 1 maka akan konvergen juga. Dengan proses yang lebih umum maka setelah langkah ke m sebuah barisan {nm (k)}∞ k=1 dari integer j = 1, . . . , m, masing

n (k) masing barisan {xj m } konvergen ke xj . Karena xnm (k) − x → 0, k → ∞ dengan x = (x1, x2, ..., xm)

3.2 Konveksitas Himpunan dan Fungsi Obyek yang berperan utama dalam penelitian ini adalah himpunan dan fungsi yang bersifat konveks. Berikut pendefinisian dan penjelasan secara teori tentang bentuk konveksitas himpunan dan fungsi tersebut.


15 3.2.1 Himpunan Konveks

Definisi 3.2.1 Himpunan C dikatakan bersifat konveks jika terdapat dua titik dalam C yang membentuk segmen garis yang juga terletak dalam C.

Gambar 3.2 : Konveks dan tidak konveks Bentuk kurva yang digambarkan di atas memperlihatkan bentuk konveks dan tidak konveks suatu himpunan sesuai dengan definisi di atas. Secara matematis, bentuk definisi tersebut dapat dituliskan kembali dengan memberikan setiap titik x1, x2 ∈ C dan untuk setiap 0 ≤ θ ≤ 1 maka θx1 + (1 − θ)x2 ∈ C. Beberapa himpunan yang bersifat konveks adalah: 1. Polihedral

Gambar 3.3 : Polihedron P dengan irisan dari lima buah halfspaces dengan vektor normal a1, . . . , a5


16 2. Cone

Gambar 3.4 : Sebuah convex cone: untuk setiap titik x1 , x2 ∈ C dan untuk setiap 0 ≤ θ ≤ 1 maka θx1 + (1 − θ)x2 ∈ C

3. Hyperplane/Halfspaces

Gambar 3.5 : Sebuah hyperlane dengan dua halfspaces 4. Bola Euklidis dan Ellipsoida

Gambar 3.6 : Sebuah ellipsoid dalam R2


17 3.2.2 Fungsi Konveks

Definisi 3.2.2 Sebuah fungsi f : Rn → R adalah konveks jika domain f adalah himpunan konveks dan jika untuk setiap x1 , x2

∈ Dom f dan untuk setiap

0 ≤ θ ≤ 1, f(θx1 + (1 − θ)x2 ) ≤ θf (x1 ) + (1 − θ)f (x2 )

Gambar 3.7 : Fungsi Konveks dan Fungsi Tidak Konveks

Pertidaksamaan pada Definisi (3.2.2) telah ditunjukkan secara geometri pada gambar di atas, dengan arti bahwa ruas garis yang dibentuk oleh titik A(x1, f (x1 )) dan B(x2, f(x2 )), disebut dengan chord dari titik A ke titik B. Sebuah fungsi f dikatakan dapat didifferensialkan pada titik x jika terdapat sebuah matriks Df(x) ∈ Rmxn sehingga memenuhi: lim

z→x

kf(z) − f (x) − Df (x)(z − x)k2 =0 kz − xk2

(3.1)

dan sebuah fungsi affine dari z diberikan dengan bentuk: f (x) + Df (x)(z − x)


(3.2)

18 Misalkan f adalah fungsi yang bernilai riel f : Rn → R dan terdifferensialkan maka Df (x) adalah sebuah matriks 1 × n, dimana transposnya disebut dengan gradien: ∇f(x) =

∂f(x) ∂f(x) ,..., ∂x1 ∂xn

T

= Df (x)T

(3.3)

dan gradien chord dari fungsi yang dimaksud dapat diformulasikan sebagai approksimasi barisan Taylor orde pertama yang merupakan fungsi affine dari x, yaitu: f (x) ' f(x0) + ∇f (x0 )T (x − x0)

(3.4)

Kemudian, untuk x1, x2 ∈ C ⊆ Rn sedemikian f : Rn → R adalah fungsi konveks maka kurva pada gambar di bawah ini merupakan fungsi konveks jika f terdifferensialkan dan gradiennya ∇f (x) ada ∀x ∈ domf dan memenuhi: f(y) ≥ f (x) + ∇f (x)T (y − x)

Gambar 3.8 : Jika f fungsi terdifferensialkan dan x , y ∈ dom f, f (y) ≥ f (x) + ∇f (x)T (y − x)


(3.5)

maka

19 Pernyataan di atas disajikan kembali sebagai bentuk teorema di bawah ini sehingga lebih terjamin dengan sebuah pembuktian sebagai berikut:

Teorema 3.2.1 Jika x1 , x2 ∈ C ⊆ Rn dan f adalah fungsi yang memenuhi f (x2 ) ≥ f (x1) + ∇f (x1 )T (x2 − x1 ) maka f adalah fungsi konveks.

Bukti: Pilih x 6= y dan 0 ≤ θ ≤ 1 serta x + θ(y − x) ∈ domf . Misalkan z = x + (1 − θ)y sedemikian sehingga: f(x) ≥ f(z) + f 0 (z)(x − z) dan f(y) ≥ f (z) + f 0 (z)(y − z) Dengan mengalikan pertidaksamaan pertama dengan θ dan pertidaksamaan kedua dengan 1 − θ sehingga: θf (x) ≥ θf (z) + θf 0 (z)(x − z) dan f(y) − θf (y) ≥ f (z) − θf (z) + f 0 (z)(y − z) − θf 0 (z)(y − z) Dengan menjumlahkan kedua pertidaksamaan tersebut maka diperoleh: θf (x) + (1 − θ) ≥ f (z) Hasil tersebut jelas merupakan bentuk fungsi konveks.

Teorema 3.2.2 Jika f : C → R adalah fungsi konveks maka f adalah fungsi Lipschitz.


20 Bukti: Fungsi f : C → R dan x1 , x2 ∈ C disebut fungsi konveks jika memenuhi: f(x2 ) ≥ f (x1) + ∇f (x1 )T (x2 − x1 ) atau diformulasi menjadi: f (x1 ) − f (x2 ) ≤ ∇f (x1)T (x1 − x2 ), dengan menggunakan operator norm maka f(x1 ) − f(x2) ≤ ∇f (x1)T (x1 − x2) sehingga kondisi tersebut memenuhi kondisi fungsi Lipschitz. Beberapa jenis fungsi yang bersifat konveks adalah fungsi logaritma pada R+ , fungsi eksponensial pada R, fungsi norm pada Rn , fungsi linear pada Rn , fungsi kuadrat pada Rn dan lain-lain.


BAB 4 OPTIMISASI KONVEKS DAN OPTIMISASI DUA TAHAP SERTA METODE PROYEKSI GRADIEN

Optimisasi matematika mempunyai bentuk secara umum: Minimize f0 (x)

(4.1)

s.t

fi (x) ≤ 0

(4.2)

hi (x) = 0,

(4.3)

Untuk i = 1, 2, . . . , m dan vektor x = (x1 , . . . , xn ) adalah variabel optimisasi dan f0 : Rn → R adalah fungsi objektif serta fi , hi : Rn → R adalah pertidaksamaan atau persamaan kendala. Nilai x disebut solusi layak (feasible solution) jika memenuhi kendala tersebut. Jika C adalah himpunan solusi yang memenuhi kendala di atas maka nilai optimal pada permasalahan optimisasi tersebut dinotasikan: f0 (x) = f ∗ dengan f ∗ = inf f0 (x) x∈C

(4.4)

Penguraian bentuk (4.4) dapat dilihat pada Teorema 5.3.2. Permasalahan optimisasi ini berkembang ke berbagai bentuk kelas optimisasi, seperti optimisasi linear, optimisasi nonlinear, optimisasi konveks, optimisasi tak konveks, optimisasi dua tahap, optimisasi bersifat stokastik, dan sebagainya.


22 4.1 Optimisasi Konveks Optimisasi konveks adalah bentuk optimisasi dengan fungsi tujuan dan fungsi kendala merupakan fungsi konveks. Masalah pendekatan konveksitas banyak dipakai pada model program matematika karena bentuk kesulitan optimisasi bukan dilihat dari bentuk kelinearannya tetapi berdasarkan konveksitasnya. Optimisasi konveks dituliskan dengan bentuk: Min f0 (x)

(4.5)

s.t. fi (x) ≤ 0

(4.6)

dengan fi : Rn → R adalah fungsi konveks, untuk setiap ∀x ∈ Rn adalah himpunan konveks. Adakah keistimewaan optimisasi konveks dibandingkan dengan kelas optimisasi lainnya? Ada tiga alasan yang membuat bentuk optimisasi konveks lebih istimewa dibanding kelas optimisasi lainnya, yaitu sifatnya yang mempunyai solusi lokal yang juga merupakan solusi global (hal ini akan dibuktikan lebih lanjut sebagai Teorema 4.1.1), teori dualitas dan kondisi optimalitas serta metoda solusi yang sederhana (pada kasus ini akan menggunakan algoritma proyeksi gradien). Solusi layak yang optimal dari permasalahan optimisasi dibedakan atas solusi optimal lokal dan solusi optimal global. Misalkan C adalah himpunan solusi layak dari suatu permasalahan optimisasi yang diberikan, maka: Solusi optimal lokal jika memenuhi: x2 ∈ C, kx2 − x1 k ≤ R ⇒ f0 (x2) ≥ f0(x1 ), untuk terdapat R > 0


(4.7)

23 Solusi optimal global jika memenuhi: x2 ∈ C ⇒ f0 (x2) ≥ f0 (x1 )

(4.8)

Perhatikan ilustrasi solusi optimal global dan lokal pada gambar berikut:

Gambar 4.1 : Ilustrasi solusi global dan lokal

Teorema 4.1.1 Pada permasalahan optimisasi konveks, solusi optimal lokal merupakan solusi optimal global.

Bukti: Misalkan bahwa x1 adalah solusi optimal lokal, karena terdapat x2 ∈ C dengan f0 (x2) ≥ f0 (x1) maka dilakukan sedikit langkah pergeseran yang sangat kecil dari x1 menuju x2 yaitu z sehingga z = λx2 + (1 − λ)x1 dengan nilai λ > 0 adalah sangat kecil, sehingga z sangat dekat ke x1 dengan f0 (z) < f0 (x1). Hal ini kontradiksi dengan pernyataan keoptimalan lokal.


24 4.2 Optimisasi Dua Tahap Optimisasi dua tahap adalah persoalan optimisasi yang bersifat hirarkis dimana sebuah himpunan bagian yang dibatasi menjadi solusi dari persoalan optimisasi yang diberikan, yang diparameteri oleh variabel lainnya. Hal ini menggambarkan bahwa untuk setiap keputusan yang diambil pertama sekali (level upper) akan menjadi dasar untuk mengambil keputusan berikutnya (level lower). Dengan demikian opimisasi ini terdiri dengan dua tahap yang disebut dengan level upper sebagai tahap pertama dan level lower sebagai tahap kedua. Secara matematis, untuk setiap variabel pada level upper akan ditentukan beberapa variabel yang terbatas pada level lower (solusi pada level lower) pada optimisasi tahap ganda tersebut. Struktur optimisasi hirarkis ini nampak secara alami diberbagai applikasi ketika aksi dari level lower bergantung pada keputusan level upper. Formula optimisasi dua tahap ini dituliskan dalam bentuk:

(Level upper) Minimizexu ,xl fu (xu , xl ) s.t.

gu (xu ) ≤ 0

(4.9) (4.10)

(Level lower) Minimizexl fl (xu , ·)

(4.11)

s.t.

gl (xu , ·) ≤ 0

(4.12)

xu , xl ≥ 0

(4.13)


25 dengan: xu ∈ Rn , xl ∈ Rn ; fu , fl : Rn × Rn → R gu : Rn → R gl : Rn × Rn → R

(4.14) (4.15)

Secara umum, level upper sering disebut dengan outer problem sementara level lower disebut dengan inner problem. Untuk setiap nilai dari variabel xu pada level upper, kendala pada level lower g(xu , ·) ≤ 0 mendefinisikan himpunan kendala Ω(xu ) dari persoalan level lower: Ω(xu ) = {xl : gl (xu , ·) ≤ 0}

(4.16)

Jadi Sl (xu , xl (xu )) adalah himpunan solusi dari level lower, dengan: Sl (xu , xl (xu )) = {xl ∈ arg min{fl (xu , ·) : xl ∈ Ω(xu )}}

(4.17)

Sehingga optimisasi dua tahap di atas dapat diformulasikan kembali menjadi bentuk: Minimizexu ,xl fu (xu , xl )

(4.18)

s.t.

gu (xu ) ≤ 0

(4.19)

xl ∈ Sl (xu , xl)

(4.20)

Bentuk di atas menunjukkan bahwa untuk setiap solusi level upper beraksi pertama sekali atau sering disebut Leaders Problem, sementara level lower dibuat untuk bereaksi untuk mendapatkan solusi xl secara optimal bergantung pada pilihan xu atau Followers Problem. Kemudian himpunan solusi layak dituliskan


26 dalam bentuk: S = {(xu , xl ) ∈ Rn×n : gu (xu ) ≤ 0, xl ∈ Sl (xu , xl )}

(4.21)

Salah satu kelas optimisasi multitahap adalah optimisasi konveks dua tahap yang akan dibahas pada bab pembahasan.

4.3 Metode Steepest Descent Misalkan permasalahan optimisasi yang dibicarakan tidak mempunyai suatu solusi analitis, sehingga harus digunakan suatu pendekatan atau algoritma numerik (iteratif) untuk memecahkan masalah tersebut. Algoritma tersebut diharapkan dapat dengan cepat mencapai kondisi konvergen ke solusi yang optimal. Metode gradien descent menggunakan gradien negatif (−∇f ) untuk mengevaluasi titik xk secara berkelanjutan sebagai arah dari setiap langkah untuk setiap iterasi algoritma. Kriteria yang memperlihatkan iterasi berhenti adalah jika mencapai kondisi final: k∇f k2 ≤ ε

(4.22)

dimana ε adalah suatu nilai yang kecil dan positif. Metode gradien negatif menjamin arah setiap langkah pada algoritma adalah arah descent. Misalkan f : Rn → R merupakan fungsi kontinu yang dapat didifferen sialkan, maka metode steepest descent membangkitkan sebuah barisan xk ∈ Rn melalui: xk+1 = xk − βk ∇f (xk )


(4.23)

27 dimana βk adalah sejumlah bilangan riel positif dan memenuhi: βk =

αk k∇f (xk )k

(4.24)

dengan ∞ X k=0

αk = ∞,

∞ X

α2k < ∞

(4.25)

k=0

Dasar dari kekonvergenan metoda gradien descent adalah pencarian garis yang tepat (linesearch) atau pelacak Armijo, diperoleh dari teorema kekonvergenan global Zangwill dan teorema kekonvergenan global, serta pernyataan bahwa setiap titik kumpul x ¯ dari xk ∈ Rn bila ada, adalah stasioner, yaitu jika ∇f (¯ x) = 0. Agar keberadaan titik kumpul tersebut dapat dipastikan, maka diperlukan sebuah asumsi bahwa permulaan iterasi x0 berada pada suatu himpunan terbatas dari fungsi f . Situasi ini akan menjadi lebih baik jika f merupakan fungsi konveks. Dengan konveksitas fungsi f maka sangat memungkinkan untuk membuktikan kekonvergenan dari barisan yang dibangkitkan oleh algoritma tersebut. Tetapi pengamatan yang lebih lanjut menyatakan bahwa kasus βk yang diberi oleh (4.24) dan (4.25) pada metoda ini tidaklah menjamin bahwa f (xk+1 ) < f (xk ) untuk semua k.

4.4 Algoritma Proyeksi Gradien (Gradient Projection Algorithms) Metoda proyeksi gradien pertama sekali diperkenalkan oleh Rosen, 1960 dan menjadi salah satu metoda yang digunakan untuk menyelesaikan program nonlinear. Metoda ini akan dipilih untuk menyelesaikan persoalan pada penelitian ini.


28 Adapun yang menjadi alasan untuk menggunakan metode ini adalah karena didalam penerapan, metode proyeksi gradien mampu mengidentifikasi himpunan solusi yang aktif dalam sejumlah iterasi terhitung. Setelah himpunan solusi tersebut diidentifikasi dengan benar, algoritma proyeksi gradien mereduksi algoritma descent pada subruang dari variabel-variabel bebas. Lebih jelasnya, metode ini selalu digunakan bersama-sama dengan metoda lain untuk mendapatkan tingkat kekonvergenan yang lebih cepat. Ada dua metode program nonlinear yang umum dan terkenal yaitu metode proyeksi gradien dan metode fungsi penalty, yang digunakan dengan prosedur descent orde pertama yaitu steepest descent. Metode proyeksi gradien adalah sebuah generalisasi dari metode descent, dimana gradien negatif diproyeksikan pada daerah terbatas dan mencari solusi di sepanjang kurva sehingga metode ini bekerja dengan membangkitkan barisan solusi-solusi layak. Jika himpunan domain fungsi pada kasus ini adalah himpunan konveks C, maka keadaan menjadi memungkinkan untuk menggunakan proyeksi orthogonal pada C, yaitu menunjukkan arah pergerakan gradien disetiap iterasi. Hal ini terjadi karena metode proyeksi gradien meminimisasi sebuah fungsi terdifferensialkan dan kontinu f : Rn → R atas himpunan konveks tak kosong dan tertutup C ⊂ Rn .

Definisi 4.4.1 . 1. hx1, x2i adalah perkalian dalam (inner product) dari x1 dan x2. 2. Jika C adalah himpunan konveks tertutup, maka PC (x) adalah proyeksi or-


29 thogonal titik x pada C, dan jarak x ke C: dist(x, C) = kx − PC (x)k

PC (x) berperan untuk menunjukkan arah yang turun (descent) yang mungkin pada setiap langkah iterasi yang dimulai dari x(k) dengan arah −∇f (x(k)). Berikut adalah deskripsi dari algoritma proyeksi gradien yang dimaksud. Inisialisasi: Ambil x(0) ∈ C Iterasi:

Jika x(k) adalah stasioner maka stop. Iterasi bergerak dari z (k) ke z (k+1) dan dipilih parameter skalar α(k)>0 sehingga: z (k) = PC (x(k) − α(k) ∇f (x(k))) kemudian pilih parameter skalar kedua λ(k) ∈ [0, 1] sehingga: x(k+1) = x(k) + λk (z (k) − x(k) ) Approksimasi akhir algoritma ini bergantung pada nilai kedua parameter tersebut.

Nilai parameter λk (z (k) ∈ [0, 1] dari barisan solusi

k x ∈ Rn dapat di-

tentukan dari bentuk kemonotonan kondisi f (xk+1 ) < f (xk ). Parameter skalar α(k) > 0 yang dipilih merupakan langkah atau iterasi dari algoritma di atas. Nilai α(k) harus diseleksi sehingga diperoleh suatu nilai yang dapat menjamin sem barang limit titik x∗ dari barisan xk ∈ Rn yang memenuhi kondisi optimal yaitu: h∇f (x∗), x − x∗i ≥ 0, x ∈ C


(4.26)

30 atau ∇f (z)T (x − z) ≥ 0, ∀x ∈ C

(4.27)

Sembarang titik x∗ yang memenuhi kondisi keoptimalan di atas disebut dengan titik stasioner dari kasus optimisasi yang akan diteliti (lihat Teorema 5.3.1). Jika ∇f adalah kontinu Lipschitz dengan konstan Lipschitz K dan α(k) memenuhi: 2 (1 − ε) (4.28) K dan untuk ε dalam (0,1), maka ada limit dari xk ∈ Rn yang merupakan titik ε ≤ α(k) ≤

stasioner dari masalah minimisasi pada optimisasi tersebut. Perhatikan gambar di bawah ini

Gambar 4.2 : Contoh ilustrasi metode proyeksi gradien

Proses pada ilustrasi di atas adalah kasus pada sebuah persamaan kendala tunggal h(x) = 0. Pergerakan pertama adalah disepanjang garis yang ditunjukkan dengan ∇f(xk ) ke arah permukaan kendala. Pergerakan berikutnya adalah bagian yang paling utama yaitu arah dari gradien negatif yang diproyeksikan dari p (yang mana sama dengan gradien negatif dari q). Pergerakan yang kedua ini identik dengan menentukan gradien descent dan kemudian menggunakan garis pelacak.


31 Bagaimanapun jika nilai α(k) > 0 adalah besar maka hasil dari pergerakan pertama adalah z k yang berada pada permukaan kendala. Jadi cukup jelas bahwa ide dari metode proyeksi gradien adalah meminimumkan fungsi f atas permukaan S (kendala h(x) = 0) dari titik xk pada S bergerak ke arah xk+1 pada S dengan arah yang ditentukan.

4.5 Analisis kekonvergenan Metode Proyeksi Gradien Pada analisis kekonvergenan metode proyeksi gradien, konvergensi yang kuat dari suatu solusi pada fungsi ditinjau dari bentuk kekontinuan uniformnya. Berdasarkan algoritma proyeksi gradien maka dibangkitkan sebuah barisan solusi solusi layak {xn } yang konvergen ke solusi optimal. Berikut definisi dan teorema yang membuktikan pernyataan berikut.

Definisi 4.5.1 Misalkan C 6= ∅ merupakan himpunan konveks tertutup maka:

1. Dipenuhi y = PC (x) jika dan hanya jika hx − y, z − yi ≤ 0 untuk setiap z ∈ C. 2. Sebuah titik x ¯ disebut pembuat minimum pada sebuah fungsi konveks f pada x − αf 0 (¯ x)), α > 0. himpunan C, jika dan hanya jika x ¯ = PC (¯

Teorema 4.5.1 Asumsikan bahwa permasalahan optimisasi di atas mempunyai solusi. Kemudian algoritma proyeksi gradien membangkitkan sebuah barisan tak hingga xk dan iterasi berhenti pada suatu iterasi k, yang mana xk adalah sebuah solusi dari masalah optimisasi tersebut, yang konvergen ke solusi x ¯.


32 Bukti: Diasumsikan bahwa algoritma tersebut membangkitkan sebuah barisan tak hingga xk . Jika iterasi berhenti pada iterasi ke-k maka xk adalah stasioner. Karena f adalah konveks, titik stasioner merupakan solusi dari permasalahan. Misalkan x ¯ adalah solusi dari masalah optimisasi yang diberikan.

2

2

2

k+1

x − xk + xk − x ¯ − xk+1 − x ¯ = 2 xk − xk+1 , xk − x ¯

= 2γk z k − xk , x ¯ − xk Sifat yang telah dijelaskan pada proyeksi orthogonal (Teorema 4.5.1) dapat ditampilkan sebagai: hPC (u) − u, v − PC (u)i ≥ 0, u ∈ Rn , v ∈ C, sehingga

¯ − zk 0 ≤ z k − xk + βk ∇f(xk ), x

= z k − xk + βk ∇f(xk ), x ¯ − xk + z k − xk + βk ∇f (xk ), xk − z k sehingga dengan ini:

k ¯ − xk ≥ βk ∇f (xk ), xk − x ¯ − z k − xk + βk ∇f (xk ), xk − z k z − xk , x

≥ βk f(xk ) − f(¯ x) + z k − xk + βk ∇f (xk ), z k − xk

≥ z k − xk + βk ∇f (xk ), z k − xk

2

= z k − xk + βk ∇f (xk ), z k − xk dengan menggunakan pertidaksamaan gradien pada fungsi konveks f pada pertidaksamaan yang kedua, maka diperoleh: h

2

2

2

2

k+1

i

x − xk + xk − x ¯ − xk+1 − x ¯ ≥ 2γk z k − xk + βk ∇f (xk ), z k − xk

2

= 2γk−1 xk+1 − xk + 2γk βk ∇f (xk ), z k − xk

dan dengan mengatur kembali, maka:

2

2

2

k+1

x −x ¯ ≤ xk − x ¯ + (1 − 2γk−1 ) xk+1 − xk − 2γk βk ∇f (xk ), z k − xk

2

≤ xk − x ¯ − 2γk βk ∇f (xk ), z k − xk


33 dengan menggunakan kenyataan bahwa γk ∈ [0, 1] pada ketidaksamaan yang kedua. −σγj ∇f(xj )T (z j − xj ) ≤ f (xj ) − f(xj+1 ) dengan mengalikan dengan

(2βk ) , σ

maka

εj ≤ 2βj γj ∇f (xj )T (z j − xj ) karena {f(xj )} tidak naik, diperoleh εj ≤

2βˆ 2βj f (xj ) − f(xj+1 ) ≤ f(xj ) − f(xj+1 ) σ σ

dengan o ≤ j ≤ k maka k X j=0

dan

k P

εj ≤

2βˆ 2βˆ f(x0 ) − f(xk+1 ) ≤ f(x0 ) − f(¯ x) σ σ

εj dapat dijumlahkan sehingga

j=0

k P

εj < ∞, maka

j=0

2

2

k+1

x −x ¯ ≤ xk − x ¯ + εk Akhir perhitungan ini menunjukkan bahwa barisan solusi konvergen ke sebuah titik stasioner.

Misalkan saja bahwa S adalah himpunan solusi dari permasalahan opti misasi pada kasus ini dengan x ¯ ∈ S dan εk dapat dihitung sehingga xk adalah konvergen ke S. Dengan teorema di atas maka xk adalah sebuah barisan yang terbatas sehingga mempunyai suatu titik kumpul (cluster points) atau stasioner. Dengan sifat konveksitas fungsi, maka titik kumpul yang dimaksud adalah solusi dari masalah yang diberikan, dan barisan xk konvergen ke solusi tersebut.


34 Teorema 4.5.2 Misalkan C ⊂ Rn adalah himpunan tidak kosong dan {xk } ⊂ Rn merupakan sebuah barisan sedemikian sehingga:

k+1

2

2

x − z ≤ xk − z + εk Untuk setiap z ∈ C dan untuk setiap k dimana {εk } ⊂ R+ adalah sebuah barisan yang dapat dijumlahkan maka:

1. {xk } adalah terbatas 2. Jika sebuah titik kumpul (cluster point) x ¯ berada di C, maka seluruh barisan ¯. {xk } akan konvergen ke x

Bukti:

1. Misalkan z ∈ C, maka diperoleh bahwa: k−1 ∞

k+1

2 0

2 X

0

2 X

x

−z ≤ x −z + εj ≤ x − z + εj j=0

j=0

Karena {εk } adalah barisan yang dapat dijumlahkan maka {xk } adalah terbatas 2. Misalkan x ¯ ∈ C adalah titik kumpul dari {xk } dan ambil δ > 0. Misalkan ¯. Karena {xk } adalah sebuah subbarisan dari {xk } yang konvergen ke x {εk } adalah sebuah barisan yang dapat dijumlahkan, terdapat k0 sedemikian ∞

2 P εj < δ2 dan terdapat k1 sehingga lk1 ≥ k0 dan xlk − x ¯ < δ2 sehingga j=k0

untuk k ≥ k1 . Kemudian, untuk k > lk1 , dimiliki:


35

k−1 ∞

2

2 X

2 X

k+1 δ δ

x −x ¯ ≤ xlk1 − x ¯ + εj ≤ xlk1 − x ¯ + εj < + = δ 2 2 j=l j=l k1

sehingga lim xk = x ¯. k→∞


k1

BAB 5 PEMBAHASAN

5.1 Formulasi Optimisasi Konveks Dua Tahap Optimisasi konveks dua tahap (Two Level Convex Optimization Problem) adalah kelas optimisasi dua tahap (Bilevel Optimization) yang mempunyai fungsi tujuan maupun fungsi kendala bersifat konveks untuk kedua levelnya. Bentuk optimisasi dua tahap yang telah diuraikan pada Bab 3 dapat ditampilkan kembali dengan mengubah jenis himpunan domain, fungsi kendala dan tujuannya menjadi himpunan dan fungsi bersifat konveks untuk kedua levelnya sehingga diperoleh formulasi bentuk persoalan optimisasi konveks dua tahap sebagai berikut: Minimizexu ,xl fu (xu , xl) s.t

xl ∈ Sl (xu , xl) = arg min{fl (xu , ·)|(xu , xl) ∈ C}

(5.1) (5.2)

dengan C ⊆ Rn adalah himpunan konveks tertutup,

(5.3)

fu , fl : Rn × Rn → R adalah fungsi bersifat konveks.

(5.4)

Berdasarkan bentuk di atas, untuk setiap variabel upper (xu ), terdapat variabel lower (xl ) yang bergantung pada (xu ), yang dibatasi menjadi solusi dari level lower dengan himpunan solusi Sl (xu , ·). Hal ini menjelaskan bahwa semua solusi layak pada level upper, akan layak pada level lower tetapi akan lebih layak secara umum pada optimisasi dua tahap jika didapatkan variabel x(xu , xl ) yang dapat menyelesaikan kedua level. Dengan demikian, semua himpunan solusi yang layak 36 Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

37 pada level lower dan level upper akan terbatas sedemikian sehingga pasangan kedua variabel ini memenuhi optimisasi tahap kedua dan pertama atau dengan kata lain, himpunan solusi tersebut merupakan solusi akhir dari persoalan optimisasi konveks dua tahap dan dikumpulkan di dalam sebuah himpunan S(xu , xl ), yaitu: S = {(xu , xl ) ∈ Rn×n

(5.5)

Perhatikan implementasi pernyataan tentang hubungan antara solusi level upper dengan solusi level lower di atas dengan contoh kasus yang sederhana pada ilustrasi gambar berikut:

Gambar 5.1 : Himpunan solusi upper atau solusi optimisasi Su adalah bagian dari solusi lower Sl

5.2 Regulerisasi Optimisasi Konveks Dua Tahap Dengan formulasi optimisasi konveks dua tahap (5.1 - 5.4) yang telah dijelaskan, maka akan dilakukan regulerisasi fungsi dengan menggunakan metode penalty dan regulerisasi Tikhonov.


38 Definisi 5.2.1 (Fungsi Penalty) Misalkan P adalah sebuah bentuk optimisasi: Minimizex f (x)

P :

s.t.

g(x) ≤ 0 x ∈ Rn

Sebuah fungsi p(x) : Rn → R disebut fungsi penalty pada P jika p(x) memenuhi: 1. p(x) = 0 jika g(x) ≤ 0 2. p(x) > 0 jika g(x) > 0 sehingga dengan program penalty, bentuk masalah P di atas menjadi: P :

Minimizex f (x) + δp(x), δ > 0 s.t.

x ∈ Rn

Teorema 5.2.1 (Teorema Konvergensi Penalty) Misalkan f (x), g(x) dan p(x) adalah fungsi kontinu. Misalkan xk adalah sebuah barisan solusi P (δ). Kemu dian x ¯ dari xk sebagai solusi P (δ). Bukti: Misalkan x ¯ adalah limit dari xk . Dari sifat kekontinuan fungsi diperoleh x), dan q ∗ = lim q(δk , xk ) ≤ f (x∗), sehingga: lim f(xk ) = f (¯

k→∞

k→∞

x) lim δk p(xk ) = lim q(δk , xk ) − f(xk ) = q ∗ − f (¯

k→∞

k→∞

Karena δk → ∞ maka lim p(xk ) = 0. Kemudian dari kekontinuan g(x) dan k→∞

p(x), p(¯ x) = 0 dan g(¯ x) ≤ 0, berarti bahwa x ¯ adalah sebuah solusi layak sehingga: f (xk ) ≤ f(x∗ ) untuk setiap k dan f (xk ) ≤ f (x∗ ). Kemudian x ¯ dari xk adalah solusi dari masalah P (δ) tersebut.


39 Definisi 5.2.2 (Regulerisasi) Misalkan P adalah sebuah bentuk optimisasi dengan dua fungsi objektif kAx − bk dan kxk sebagai berikut: P :

Minimizex (kxk, kAx − bk) s.t.

x ∈ Rn

sehingga bentuk regulerisasi dari masalah P di atas dituliskan: P (δ) :

Minimizex δkxk + kAx − bk, δ > 0 s.t.

x ∈ Rn

untuk sebuah barisan naik (increasing sequence) konstan δ dengan δ → +∞. Kuantitas skalar δ disebut dengan parameter penalty. Dasar dari approksimasi regulerisasi adalah mendapatkan suatu vektor x yang bernilai kecil (jika mungkin) sedemikian sehingga nilai residu (Ax − b) juga kecil. Berdasarkan kedua definisi di atas, dan formulasi optimisasi konveks dua tahap (5.1-5.4) yaitu fungsi objektif pada program dua tahap adalah fungsi kontinu Lipschitz lokal pada titik-titik yang disebut dengan daerah kestabilan, yaitu himpunan semua parameter (variabel upper) dimana solusi optimal pada level lower tidak akan mendapat perubahan, dengan demikian (5.1-5.2) dapat diregulerisasi. Misalkan x = (xu , xl ) ∈ S ⊆ Rn×n sebagai solusi optimisasi konveks dua tahap maka bentuk regulerisasi fungsi objektif dinotasikan dengan sebuah famili fungsi yang berparameter σ sebagai berikut: Fσ (x) = σfu (x) + fl (x), σ > 0


(5.6)

40 dimana σ berubah-ubah sepanjang iterasi, sehingga bentuk (5.1-5.4) dapat dituliskan kembali menjadi: Minimizex Fσ (x) s.t.

x ∈ C ⊆ Rn

Gambar di bawah ini adalah illustrasi kasus sederhana tentang optimisasi tersebut.

Gambar 5.2 : Ilustrasi sederhana minimisasi Fσ (xu , xl) dengan domain Su pada optimisasi konveks dua tahap

Dengan bentuk regulerisasi (5.6) berarti bahwa jika xk ∈ C adalah merupakan iterasi ke-k dan σk adalah parameter ke-k sehingga terjadi iterasi proyeksi gradien dari Fσ (x) ke titik xk , dengan σk dapat di up-date. Kekonvergenan algoritma ke solusi persoalan optimisasi di atas akan menunjukkan: lim σk = 0,

k→∞

∞ X

σk = +∞

k=0


(5.7)

41 Selanjutnya perlu dibuktikan kembali bahwa apakah fungsi regulerisasi Fσ (x) tersebut dapat mempertahankan konveksitas fungsi objektif dan fungsi kendala optimisasi awal atau tidak? Persoalan ini akan ditunjukkan dengan bentuk teorema berikut.

Teorema 5.2.2 Misalkan fu (x) dan fl (x) adalah fungsi objektif bersifat konveks dari masalah optimisasi dua tahap dan Fσ (x) adalah fungsi regulerisasi dengan Fσ (x) = σfu (x) + fl (x), σ > 0 maka Fσ (x) adalah merupakan fungsi konveks.

Bukti: Misalkan Fσ : Rn → R ∀x1, x2 ∈ Rn ; ∀α, β ∈ R ; α + β = 1, α > 0, β > 0 sehingga Fσ (αx1 + βx2) ≤ σfu (αx1 + βx2) + fl (αx1 + βx2) ≤ σ{αfu (x1) + βfu (x2)} + {αfl (x1) + βfl(x2 )} ≤ αFσ (x1) + βFσ (x2 ) Perhitungan akhir jelas menunjukkan bahwa sifat konveksitas (Definisi 3.2.2) pada fungsi regulerisasi Fσ (x) sangat dipenuhi atau dapat dipertahankan. Setelah meregulerisasi bentuk optimisasi dan membuktikan konveksitas dapat dipertahankan maka metode proyeksi gradien akan digunakan untuk menyelesaikan masalah tersebut. Tujuan dari metode ini adalah mendapatkan kekonvergenan barisan ke solusi optimal. Berikut adalah penjelasan tentang kondisi optimal solusi.


42 5.3 Kondisi Optimal dari Solusi

Teorema 5.3.1 Misalkan f : C → R adalah fungsi objektif bersifat konveks pada suatu masalah optimisasi dan terdifferensialkan sehingga untuk setiap x1, x2 ∈ C dan f (x2 ) ≥ f(x1 ) + ∇f(x1)T (x2 − x1) (Teorema 3.2.1) maka x1 adalah optimal jika dan hanya jika x1 ∈ C dan ∇f (x1 )T (x2 − x1) ≥ 0, ∀x2 ∈ C.

Bukti: Pertama sekali misalkan x1 ∈ C memenuhi ∇f (x1)T (x2 − x1) ≥ 0, ∀x2 ∈ C kemudian jika x2 ∈ C maka ∇f (x1)T (x2 − x1 ) < 0. Misalkan bahwa titik z(t) = tx2 + (1 − t)x1, dimana t ∈ [0, 1] adalah parameter. Karena z(t) adalah chord antara x1 ∈ C dan x2 ∈ C dan himpunan layak adalah konveks maka adalah z(t) layak. Nyatakan bahwa t sangat kecil, sehingga d f(z(t)) = ∇f (x1)T (x2 − x1 ) < 0 dt t=0 dan dimiliki f (z(t)) < f (x1 ), yang membuktikan bahwa x1 ∈ C tidak optimal. Kondisi sebaliknya adalah optimal. Perhatikan gambar di bawah ini!

Gambar 5.3 : Interpretasi kondisi optimal


43 Misalkan A adalah himpunan solusi layak yang ditunjukkan dengan daerah arsiran dan terbatas pada daerah A, dan level kurva f (x) ditunjukkan dengan garis arsir. Titik x dikatakan optimal, −∇f (x) mendefinisikan sebuah hyperplane penyangga yang ditunjukkan dengan garis utuh pada A di x.

Teorema 5.3.2 (Weierstrass) Misalkan S ⊆ Rn adalah terbatas dan tertutup dan F : Rn → R adalah fungsi kontinu maka minx∈S F (x) mempunyai solusi optimal.

Bukti: Karena himpunan S adalah terbatas, F (x) dibatasi pada S. Karena S adalah himpunan tidak kosong, terdapat v = inf x∈S F (x). Dengan definisi bahwa untuk ε > 0, Sε = {x ∈ S : v ≤ F (x) ≤ v + ε} adalah tidak kosong. Misalkan saja ε → 0 dengan k → ∞ dan misalkan xk ∈ Sεk . Karena S adalah terbatas, ter¯ ∈ S (Teorema 3.2.5). dapat sebuah subbarisan dari {xn } yang konvergen ke titik x Dengan sifat kekontinuan F (x), maka F (¯ x) = lim F (xk ) dan v ≤ F (xk ) ≤ v + εk , k→∞

hal ini berarti bahwa F (¯ x) = lim F (xk ) = v. k→∞

5.4

Algoritma Proyeksi Gradien dan Analisis Kekonvergenan Solusi Optimisasi Konveks Dua Tahap Pada teori konvergensi global dari algoritma program nonlinear dibuktikan

dengan sebahagian titik limit atau kemungkinan semua titik limit dari barisan yang dibangkitkan memenuhi kondisi dari kasus minimisasi berkendala. Demikian halnya pada optimisasi konveks dua tahap berikut dengan algoritma proyeksi gradien yang dijelaskan sebagai berikut:


44

Algoritma:

Pilih parameter α ¯ > 0, θ ∈ (0, 1) dan η ∈ (0, 1) Pilih x0 ∈ C dan σ > 0 dan set k = 0 sebagai awal Diberikan xk , hitung xk+1 = z k (αk ) dimana, z k (αk ) = PC (xk − αFσ0 k (xk )) dan αk = η mk α ¯ dengan mk adalah bilangan bulat non negatif m yang memenuhi:

¯ )) ≤ Fσk (xk ) + θ Fσ0 k (xk ), z k (η m α ¯ ) − xk Fσk (z k (η m α Pilih 0 < σk+1 < σk dan set k = k + 1 dan ulangi! Jika xk stasioner maka stop.

Berdasarkan Teorema 4.5.2 dan Teorema 4.5.3, algoritma proyeksi gradien telah membangkitkan barisan solusi yang terbatas. Berikut adalah bentuk penganalisisan kekonvergenan barisan solusi yang dibangkitkan oleh algoritma tersebut terhadap optimisasi konveks dua tahap. Teorema 5.4.1 Misalkan xk adalah barisan yang dibangkitkan oleh algoritma proyeksi gradien dan C adalah himpunan solusi x untuk setiap k. Jika xk dan z k memenuhi algoritma tersebut maka xk berada pada C untuk setiap k.

Bukti: Dengan menggunakan induksi matematika maka untuk k = 0 telah dipenuhi berdasarkan langkah awal (inisialisasi) sehingga x0 ∈ C. Asumsikan bahwa xk ∈ C dan dengan z k (αk ) = PC (xk − αFσ0 k (xk )) maka disimpulkan bahwa z k ∈ C. Kemudian, dengan pernyataan bahwa αk ∈ [0.1] dan approksimasi algoritma xk+1 = z k (αk ) maka xk+1 ∈ C. Dengan demikian xk ∈ C.


45 Misalkan himpunan konveks C adalah himpunan solusi yang memenuhi fungsi objektif dan kendala suatu permasalahan optimisasi maka pada penganalisisan kekonvergenan optimisasi konveks dua tahap, diasumsikan bahwa fungsi objektif fu terbatas pada himpunan C sehingga: −∞ < f¯u = inf{fu (x)|x ∈ C}

(5.8)

Misalkan saja bahwa persoalan tersebut dapat diselesaikan maka fungsi tujuan kedua juga secara otomatis terbatas pada C, sehingga: −∞ < f¯l = min{fl (x)|x ∈ C}

(5.9)

Regulerisasi pada fungsi tujuan digunakan untuk menunjukkan kekonvergenan. Dengan (5.11) dan (5.12) maka regulerisasi fungsi (5.6) menjadi: Fσ (x) = σ(fu (x) − f¯u ) + (fl (x) − f¯l ), σ > 0

(5.10)

Asumsikan bahwa x = (xu , xl) ∈ Rn×n adalah solusi masalah optimisasi tersebut. Berikut adalah penjabaran kekonvergenan fungsi Fσ (x) ke suatu solusi x. Teorema 5.4.2 Misalkan xk adalah barisan yang dibangkitkan oleh algoritma tersebut. Jika xk adalah terbatas maka xk juga terbatas.

Bukti: Dengan Teorema 4.5.2 dan Teorema 4.5.3 maka

k x adalah terbatas.

Jika k → ∞ maka ik → ∞. Perhatikan bahwa solusi S = Su 6= ∅ sedemikian x) dan fungsi konveks φ : C → R, dengan φ(x) = max fl (x) − f¯l , fu (x) − fu (¯ sebuah himpunan terbatas L(c) = {x ∈ C|φ(x) ≤ c} , c ∈ R.


46 Karena fu (x) − f¯u ≥ 0 untuk setiap x ∈ C dan σk+1 ≤ σk sehingga dipenuhi Fσk+1 (x) ≤ Fσk (xk ) dan 0 ≤ Fσk+1 (xk+1 ) ≤ Fσk (xk+1 ) ≤ Fσk (xk ). Hal ini menun jukkan bahwa Fσk (xk ) adalah barisan tidak naik dan terbatas sehingga konver gen serta berarti bahwa fl (xk ) − f¯l adalah terbatas. Dengan c ≥ 0 sedemikian x) < 0 ≤ c maka sehingga fl (xk ) − f¯l ≤ c untuk setiap k. Karena fu (xik ) − f¯u (¯ xik ∈ L(c) yaitu himpunan terbatas sedemikian sehingga {xik } terbatas. Teorema 5.4.3 Misalkan xk adalah barisan yang dibangkitkan oleh algoritma tersebut. Jika xk adalah tak berhingga, x ¯ adalah titik kumpul dari barisan tersebut dan permasalahan optimisasi di atas mempunyai solusi maka x ¯ adalah titik stasioner. Bukti: Karena C adalah tertutup, x ¯ ∈ C (oleh Teorema 5.4.1). Misalkan {xjk } ¯. Observasi bahwa adalah subbarisan dari xk sedemikian sehingga lim xjk = x k→∞

¯ sedemikian: {γk } ⊂ [0, 1]; lim βjk = β; k→∞

0 < −σγk ∇Fσ (xk )T (z k − xk ) ≤ Fσ (xk ) − Fσ (xk+1 ) Bentuk di atas menunjukkan Fσ (xk ) adalah barisan turun karena xk ⊂ C dan masalah optimisasi mempunyai solusi dan Fσ (xk ) dibatasi maka konvergen sehingga: lim Fσ (xk ) − Fσ (xk+1 ) = 0

k→∞

diperoleh ¯ σ (¯ x)T PC (¯ x − β∇F x)) − x ¯ ≤0 0 ≤ −σˆ γ ∇Fσ (¯ dengan kekontinuan ∇Fσ dan PC sehingga perhitungan dipisah menjadi dua kasus: ¯ σ (¯ x) sehingga: Kasus 1. γˆ > 0 dan u ¯=x ¯ − β∇F x)T [PC (¯ u) − x ¯] = β¯−1 (¯ x−u ¯)T [PC (¯ u) − x ¯] = 0 ∇Fσ (¯


47 u) − x ¯] = 0, x ¯ ∈ C, sifat proyeksi orthogonal: berdasarkan (¯ u−x ¯)T [PC (¯ ¯ σ (¯ x ¯ = PC (¯ u) = PC (¯ x − β∇F x)) dan β¯ > 0 dan ∇Fσ (¯ x)T (x − x ¯) ≥ 0, ∀x ∈ C (Teorema 5.3.1) sehingga x ¯ adalah titik stasioner optimisasi. Kasus 2. 0 = γˆ = lim γjk , n ∈ N . Karena γjk = 2−l(jk ) , ∃kl(jk ) > n sedemikian: k→∞

Fσ (xjk − 2−n (z jk − xjk )) > Fσ (xjk ) − σ2−n ∇Fσ (xjk )T (xjk − z jk ) ¯ σ (¯ dengan mengambil k → ∞ dan definisi z¯ = PC (¯ x − β∇F x)), diperoleh: Fσ (¯ x − 2−n (¯ z−x ¯)) ≥ Fσ (¯ x) + σ2−n ∇Fσ (¯ x)T (¯ z−x ¯) dengan x)T (¯ x − z¯) ≥ 0 ∇Fσ (¯ diperoleh x)T (¯ z−x ¯) = ∇Fσ (¯ x)T (PC (¯ u) − x ¯) Fσ (¯ Kedua kasus ini mempunyai kesimpulan yang sama, sehingga berdasarkan Teorema 5.3.1, maka kondisi tersebut optimal dan x ¯ adalah titik stasioner.

Teorema 5.4.4 Dengan fu (x) dan fl (x) adalah fungsi yang bersifat konveks yang derivatifnya adalah fungsi Lipschitz kontinu pada himpunan terbatas. Fungsi fu (x) dibatasi pada himpunan konveks tertutup C dan himpunan Su adalah himpunan solusi level upper yang tidak kosong dan terbatas. Kemudian barisan xk memenuhi dist(xk , Su ) → 0, k → ∞.

Bukti: θ Fσ0 k (xk ), xk − xk+1 ≤ Fσk (xk ) − Fσk (xk+1 ) (dengan 5.8) = σk (fu (xk ) − f¯u ) + σk (fu (xk+1 ) − f¯u ) + (fl (xk ) − f¯l ) + (fl (xk+1 ) − f¯l )


48 Dengan melanjutkan penjumlahan untuk k = 0, 1, . . . , k¯ maka diperoleh: ¯ ¯ k k−1 X X

0 k k k+1 0 ¯ Fσk (x ), x − x ≤ σ0 (fu (x ) − fu ) + (σk+1 − σk )(fu (xk+1 ) − f¯u ) θ k=0

k=0 ¯ − σk¯ (fu (xk+1 ) − f¯u ) + (fl (x0) − f¯l ) − (fl (xk+1 ) − f¯l )

≤ σ0 (fu (x0) − f¯u ) + (fl (x0) − f¯l ) Faktanya bahwa untuk setiap k, fu (xk ) ≥ f¯u dan fl (xk ) ≥ f¯l karena xk ∈ C dan 0 < σk+1 ≤ σk . Kemudian dengan memberikan k¯ → ∞, memberi kesimpulan: ∞

P Fσ0 k (xk ), xk − xk+1 ≤ θ−1 (σ0(fu (x0 ) − f¯u ) + (fl (x0 ) − f¯l )) < +∞.

k=0

Secara partikuler:

0 k k Fσk (x ), x − xk+1 → 0, k → ∞

Teorema 5.4.5 Jika xk adalah sebuah barisan terbatas yang dibangkitkan algoritma proyeksi gradien maka semua titik akumulasinya berada pada Sl . Bukti: Misalkan dimiliki barisan solusi xk di atas adalah terbatas (Teorema 4.5.3), Misalkan x ˆ adalah titik akumulasi xk . Dengan memperhitungkan kekon¯ untuk setiap tinuan dari operator proyeksi dan fakta σk → 0 dan 0 < β ≤ αk ≤ α k, disimpulkan dari (xk − xk+1 ) → 0 dan xk − PC (xk − αk (σk fu0 (xk ) + fl0(xk ))) → 0, k → ∞ maka x − αf ˆ l0 (ˆ x)), α ˆ>0 x ˆ = PC (ˆ Berdasarkan Teorema 4.5.1(2) dan Teorema 4.5.2 maka x ˆ adalah nilai pemˆ ∈ Sl ⊂ C atau semua titik buat minimum dari fl pada himpunan C dengan x akumulasinya berada pada himpunan Sl .


49 Berdasarkan definisi dan Teorema 5.4.4 dan Teorema 5.4.5, perlu dianalisis kembali kedua titik akumulasi tersebut. Misalkan x ˆ adalah titik akumulasi pada ¯ adalah titik akumulasi pada Su maka akan diperiksa bahwa apakah setiap Sl dan x titik akumulasi pada sl merupakan titik akumulasi pada su atau tidak? Perhatikan gambar di bawah ini sebagai illustrasi pernyataan diatas.

Gambar 5.4 : Ilustrasi solusi optimal pada Optimisasi Konveks Dua Tahap

Teorema 5.4.6 Jika x ¯ adalah titik akumulasi xk pada Su dan x ˆ adalah titik akumulasi xk pada Sl maka kedua titik akumulasi tersebut adalah sama.

Bukti: Misalkan x ¯ ∈ Su 6= ∅, dan Fσk (x) konveks (Teorema 5.2.1), ditunjukkan:

0 k Fσk (x ), x ¯ − xk ≤ Fσk (¯ x) − Fσk (xk ) = σk (fu (¯ x) − f¯u ) + (fl (¯ x) − f¯l ) − σk (fu (xk ) − f¯u ) + (fl (xk ) − f¯l ) ≤ σk (fl (¯ x) − fl (xk )) dimana dengan menggunakan fakta bahwa fl (¯ x) ≤ fl (xk ), karena x ¯ ∈ Su ⊂ Sl dan xk ∈ C. Selanjutnya dimiliki bahwa:


50

2

2

2

k+1

x −x ¯ = xk − x ¯ + 2 xk+1 − xk , xk − x ¯ + xk+1 − xk

2

2

= xk − x ¯ − xk+1 − xk + 2 xk+1 − xk , xk+1 − x ¯ dengan,

k+1 − xk , xk+1 − x ¯ = xk+1 − xk + αk Fσ0 k (xk ), xk+1 − x¯ − αk Fσ0 k (xk ), xk+1 − x ¯ x

≤ αk Fσ0 k (xk ), xk+1 − x ¯

= αk Fσ0 k (xk ), xk − xk+1 + αk Fσ0 k (xk ), x ¯ − xk

≤α ¯ Fσ0 k (xk ), xk − xk+1 + αk σk (fl (¯ x) − fl (xk ))

berdasarkan fakta Fσ0 k (xk ), xk − xk+1 ≥ 0 dan αk ≤ α ¯ sehingga:

k+1

2

2

x −x ¯ ≤ xk − x ¯ + 2α ¯ Fσ0 k (xk ), xk − xk+1 + 2αk σk (fl (¯ x) − fl (xk ) Misalkan kasus ini dipisah atas dua kasus. Kasus 1. x) ≤ fu (xk ) untuk setiap k ≥ k0 sehingga Terdapat k0 sedemikian sehingga fu (¯ bentuk di atas menunjukkan:

2

2

k+1

x −x ¯ ≤ xk − x ¯ + 2α ¯ Fσ0 k (xk ), xk − xk+1

2 Disimpulkan bahwa xk − x ¯ konvergen sehingga xk terbatas. x) maka asumsikan Selanjutnya untuk menunjukkan bahwa lim fu (xk ) = fu (¯ k→∞

x) ≤ fu (xk )−ε bahwa bertentangan bahwa terdapat ε > 0 sedemikian sehingga fu (¯ untuk setiap k ≥ k2 dan dipenuhi, bahwa:

2

2

k+1

x −x ¯ ≤ xk − x ¯ + 2α ¯ Fσ0 k (xk ), xk − xk+1 − 2βεσk k k X X

k

2

0 i i i+1 2

≤ x −x ¯ + 2α ¯ σi Fσk (x ), x − x − 2βε i=k2 −1


i=k2 −1

51 dengan k → ∞, sehingga: 2βε

∞ X i=k2 −1

∞ X

2

0 i i σi ≤ xk2 − x ¯ + 2α ¯ Fσk (x ), x − xi+1 i=k2 −1

Dimana kontradiksi dengan bentuk di atas. Dengan demikian dapat diambil kex). Karena barisan tersebut adalah barisan tersimpulan bahwa lim fu (xk ) = fu (¯ k→∞

x) = fu (¯ x). Karena batas maka terdapat sebuah titik akumulasi x ˆ sedemikian fu (ˆ k ˆ ∈ Su ⊂ Sl maka x → x ˆ ∈ Su ⊂ Sl . x ˆ ∈ Sl maka dengan Bolzano diperoleh x Kasus 2. x) > fu (xk1 ) dan didefiUntuk setiap k, terdapat k1 ≥ k sedemikian sehingga fu (¯ nisikan: x) > fu (xi ) , ik → ∞, k → ∞ ik = max i ≤ k|fu (¯ dengan Teorema 5.4.2 maka {xik } terbatas dengan demikian: fu (¯ x) ≤ fu (xi ), i = ik + 1, . . . , k untuk k ≥ ik sehingga dimiliki: k−1 X

k

2 i

2

0 i i k

x − x

¯ ≤ x −x ¯ + 2α ¯ Fσi (x ), x − xi+1

2

¯ + 2α ¯ ≤ xik − x

i=ik +1 ∞ X

Fσ0 i (xi ), xi − xi+1

i=ik +1

dengan ik → ∞, maka: ∞ X

0 i i Fσi (x ), x − xi+1 → 0, k → ∞ i=ik +

Karena semua titik akumulasi xk berada pada Sl dan untuk titik akumulasi x) ≥ fu (ˆ x) dan berarti juga bahwa semua titik akumulasi x ˆ dari {xik } maka fu (¯ {xik } adalah solusi dari masalah optimisasi.


BAB 6 KESIMPULAN DAN SARAN

6.1 Kesimpulan Optimisasi konveks dua tahap adalah suatu kelas optimisasi yang hirarkis, dengan dua level (level upper dan level lower). Variabel pada level upper akan menjadi parameter untuk mencari solusi pada level lower sehingga variabel lower bergantung pada variabel upper. Optimisasi konveks dua tahap dapat diformulasikan dengan sederhana dengan regulerisasi Tikhonov dan Metode Penalty, yaitu dengan membuat level lower sebagai penalty, tanpa menghilangkan sifat konveksitas fungsi. Selanjutnya dengan Algoritma Proyeksi Gradien dapat ditunjukkan kekonvergenan solusi optimisasi tersebut, yaitu titik akumulasi pada himpunan solusi level upper dan titik akumulasi pada himpunan solusi level lower adalah titik akumulasi atau titik kumpul (cluster point) yang sama atau titik pembuat minimum kasus optimisasi konveks dua tahap tersebut.

6.2 Saran Penelitian ini masih membicarakan kasus yang sederhana, maka perlu dilakukan penganalisisan ke tahap yang lebih tinggi atau meneliti dengan menggunakan sudut pandang komputerisasi, aljabar topologi, dan lain-lain.


DAFTAR PUSTAKA

Aboussoror, A., Mansouri, A. (2005). Weak linear bilevel programming problems: existence of solutions via a penalty method, Journal of Mathematical Analysis and Applications. Vol. 304, 399-408. Ali, M. S. S. (2005). Descent Methods for Convex Optimization Problems in Banach Spaces. International Journal of Mathematics and Mathematical Science, Vol. 15, 2347-2357. Ankhili, Z., Mansouri, A. (2008). An Exact Penalty on Bilevel Programs with Linear Vector Optimization Lower Level, European Journal of Operational Research, Journal Homepage: www.elsevier.com/locate/ejor. Audet, C., Haddad, J., Savard, G. (2006). A Note on the Definition of a Linear Bilevel Programming Solution, Journal of Applied Mathematics and Computation, Vol. 181, 351-355. Bard, J. F., Plummer, J., Souie, J. C. (2000), A Bilevel Programming Approach to Determining Tax for Biofuel Production, European Journal of Operational Research, Vol. 12, 30-46. Bartle, R. G., Sherbert, D. R. (1994), Introduction to Riel Analysis, Jhon Wiley & Sons (SEA), INC, Singapore. Borwein, J. M., Lewis, A. S. (1999), Convex Analysis and NonLinear Optimization. Gargnano, Italy. Boyd, S., Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press, Cambridge, USA. Calamai, P, H., More, J, J,. (1987). Projected Gradient Methods for Linearly Constrained Problems, Journal of Mathematical Programming, Vol. 39, 93116. Chiou, S. (2004). Bilevel Programming for The Continuous Transport Network Design Problem, Journal of Transportation Research, Part B Vol. 39, 361383. Farag, M. H. (1996). The Gradient Projection Method for Solving an Optimal Control Problem, J: Applicationes Mathematicae, Vol 24. No 2, 141-147. Freund, R. M. (2004). Penalty and Barrier Methods for Constrained Optimization. Massachusetts Institute of Technology, Massachusetts. Gaughan E. D. (1987). Introducton to Analysis. Wadsworth Inc, Belmont, Pacific Grove, California, USA. Hindi, H. (2004). A Tutorial on Convex Optimization. Palo Alto Research Centre (PARC), Palo Alto, California. 53 Lasker Pangarapan Sinaga : Analisis Persoalan Optimisasi Konveks Dua Tahap (Two-Level), 2009.

54 Iusem, A. N. (2003). On the Convergence Properties of the Projected Gradient Method for Convex Optimization. Journal of Computational and Applied Mathematics, Vol. 22 No 1, 37-52. Kleywegt, A. J., Shapiro, A. (2000). Stochastic Optimization. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia. Luenberger, D. G. (1974). A Combined Penalty Function and Gradient Projection Methods for Nonlienar Programming. Journal of Optimization Theory and Applications, Vol. 14 No 5. Luenberger, D. G. (1972). The Gradient Projection Methods along Geodesis. Journal of Management Science, Vol. 18 No 11. Lv, Y., Hu, T., Wang G., Wan, Z. (2007). A Penalty Function Method Based On KuhnTucker Condition for Solving Linear Bilevel Programming, Journal of Applied Mathematics and Computation, Vol. 188, 808-813. Polak, E., Sargent, R. W. H., Sebastian, D. J. (1974). On the Convergence of Sequential Minimization Algorithms. Journal of Optimization Theory and Applications, Vol. 14 No. 4 Rosen, J. B., (1960). The Gradient Projection Methods for Nonlinear Programming. Part I, Linear Consraint. Siam Journal Applied Mathematics, Vol. 8, 181-217. Shi, C., Lu, J., Zhang, G., Zhou, H. (2006). An Extended Branch and Bound Algorithm for Linear Bilevel Programming, Journal of Applied Mathematics and Computation, Vol. 180, 529-537 Solodov, M. (2007). An Explicit Descent Methods For Bilevel Convex Optimization. Journal of Convex Analysis, Vol. 14, No. 2. Tseveendorj, I. (2006). Reverse Convex Problems: An Approach Based On Optimality Conditions. Journal of Applied Mathematics and Decision Sciences. Vol. 2006, Article ID 29023, 1-16. Vicente, L. N. (1997). Bilevel Programming. Journal of Global Optimization. Departemento de Matematica Universidade de Coimbra, 3000 Coimbra, Portugal. Wang, G., Wan, Z., Wang, X., Lv, Y. (2008). Genetic Algorithm Based on Simplex Method for Solving Linear-Quadratic Bilevel Programming Problem. Journal of Computers and Mathematics with Applications, Vol 56, 2550-2555. Yang, J., Zhang, M., He, B., Yang, C. (2008). Bilevel Programming Model and Hybrid Genetic Algorithm for Flow Interception Problem with Customer Choice. Journal of Computers and Mathematics with Applications, Journal Homepage: www.elsevier.com/locate/camwa. Ye, J. J. (1999). Optimality Conditions for Optimization Problems with Complementarity Constraints. Siam Journal Optimization, Vol. 9 No. 2, 374-387.


55 Zhu Z., Zhang B,. (2006). A General Projection Gradient Methods for Linear Constrained Optimization with Superlinear Convergence. Journal of Applied Sciences, Vol. 6 No 5, 1085-1089.


ANALISIS PERSOALAN OPTIMISASI KONVEKS DUA TAHAP (TWO-LEVEL)

Recommend Documents