METODE PENYELESAIAN UNTUK PERSOALAN PERTIDAKSAMAAN VARIASIONAL DENGAN KENDALA PERSAMAAN DAN PERTIDAKSAMAAN
TESIS
Oleh RUTH MAYASARI SIMANJUNTAK 117021050/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2013
Universitas Sumatera Utara
METODE PENYELESAIAN UNTUK PERSOALAN PERTIDAKSAMAAN VARIASIONAL DENGAN KENDALA PERSAMAAN DAN PERTIDAKSAMAAN
TESIS
Diajukan Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara
Oleh RUTH MAYASARI SIMANJUNTAK 117021050/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2013
Universitas Sumatera Utara
Judul Tesis
Nama Mahasiswa Nomor Pokok Program Studi
: METODE PENYELESAIAN UNTUK PERSOALAN PERTIDAKSAMAAN VARIASIONAL DENGAN KENDALA PERSAMAAN DAN PERTIDAKSAMAAN : Ruth Mayasari Simanjuntak : 117021050 : Magister Matematika
Menyetujui, Komisi Pembimbing
(Prof. Dr. Herman Mawengkang) Ketua
(Prof. Dr. Opim Salim S, M.Sc) Anggota
Ketua Program Studi
Dekan
(Prof. Dr. Herman Mawengkang)
(Dr. Sutarman, M.Sc)
Tanggal lulus: 17 Desember 2013
Universitas Sumatera Utara
Telah diuji pada Tanggal 17 desember 2013
PANITIA PENGUJI TESIS Ketua : Prof. Dr. Herman Mawengkang Anggota : 1. Prof. Dr. Opim Salim S, M.Sc 2. Prof. Dr. Muhammad Zarlis 3. Prof. Dr. Saib Suwilo, M.Sc
Universitas Sumatera Utara
PERNYATAAN
METODE PENYELESAIAN UNTUK PERSOALAN PERTIDAKSAMAAN VARIASIONAL DENGAN KENDALA PERSAMAAN DAN PERTIDAKSAMAAN
TESIS
Saya mengakui bahwa tesis ini adalah hasil karya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing dituliskan sumbernya.
Medan, Desember 2013 Penulis, Ruth Mayasari Simanjuntak
i Universitas Sumatera Utara
ABSTRAK Pertidaksamaan variasional adalah pertidaksamaan yang melibatkan fungsi yang harus diselesaikan untuk semua nilai dari suatu variabel, biasanya untuk himpunan konveks. Kelas fungsi vektor simetri yang membentuk pasangan kendala persamaan dan pertidaksamaan telah diperkenalkan. Ada beberapa metode yang digunakan untuk menyelesaikan persoalan pertidaksamaan variasi yaitu metode yang melibatkan modifikasi fungsi Lagrange, metode prediksi type proximal, dan metode prediksi type gradient. Kekonvergenan dari metode tersebut dibuktikan. Dari analisa yang dilakukan ketiga metode itu kurang efisien digunakan karena membutuhkan waktu yang lama dalam penyelesaian. Metode proyeksi sederhana, alternating direction method, dan metode ekstragradien adalah metode yang tepat dalam menyelesaikan persoalan pertidaksamaan variasional karena menggunakan algoritma, dan algoritma yang dihasilkan menarik, sederhana, dan sangat cepat. Kata kunci: Persoalan pertidaksamaan variasional, Alternating direction method, Optimisasi.
ii Universitas Sumatera Utara
ABSTRACT Variational inequality is an inequality involving a functional, which has to be solved for all possible values of a given variable, belonging usually to a convex set. The class of symmetric vector functions that form inequality and equality constrains is introduced. There are several methods used to solve the variational inequality problems, i.e the methods involving the modified Lagrange functions, a prediction type proximal, and a prediction type gradient method. The convergence of the methods is proved. The simple projection method, alternating direction method, and extragradient method is a appropriate methods in solving variational inequality problems because the resulting algorithm is attractive, simple, and very fast. Keyword:Variational inequality problem, Alternating direction method,Optimization
iii Universitas Sumatera Utara
KATA PENGANTAR Puji syukur kepada Tuhan Yang Maha Esa yang selalu memberikan rahmat yang luar biasa sehingga penulis dapat menyelesaikan tesis dengan judul: METODE PENYELESAIAN UNTUK PERSOALAN PERTIDAKSAMAAN VARIASIONAL DENGAN KENDALA PERSAMAAN DAN PERTIDAKSAMAAN. Penulis menyampaikan terima kasih kepada: Bapak Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc(CTM), Sp.A(K) selaku Rektor Universitas Sumatera Utara. Bapak Dr. Sutarman, M.Sc, Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Magister Matematika di FMIPA Universitas Sumatera Utara. Bapak Prof. Dr. Herman Mawengkang, Ketua Program Studi Magister Matematika FMIPA Universitas Sumatera Utara sekaligus pembimbing-I yang telah memberikan bimbingan, arahan dan ilmu pengetahuan dalam menyelesaikan tesis ini. Bapak Prof. Dr. Saib Suwilo, M.Sc, selaku Sekretaris Program Studi Magister Matematika FMIPA Universitas Sumatera Utara sekaligus pembanding-II yang telah memberikan saran dan kritik dalam penyempurnaan tesis ini. Bapak Prof. Dr. Muhammad Zarlis, Pembanding-I yang telah memberikan saran dan kritik dalam penyempurnaan tesis ini. Bapak Prof. Dr. Opim Salim S, M.Sc, Pembimbing-II yang memberikan bimbingan, arahan, dan ilmu pengetahuan dalam menyelesaikan tesis ini. Bapak/Ibu Dosen Program Studi Magister Matematika FMIPA Universitas Sumatera Utara yang telah memberikan ilmunya selama masa perkuliahan. Ibu Misiani, S.Si, staf administrasi Program Studi Magister Matematika FMIPA Universitas Sumatera Utara yang banyak membantu proses administrasi.
iv Universitas Sumatera Utara
Ucapan terimakasih juga penulis sampaikan kepada : Ibunda dan ayahanda tercinta, yang telah memberikan kasih sayang dan dukungan baik selama penulis dalam pendidikan dan penyelesaian tesis ini. Suami tercinta yang telah memberikan doa, kasih sayang, dukungan baik secara moril maupun materi. Rekan-rekan mahasiswa Program Studi Magister Matematika FMIPA Universitas Sumatera Utara khususnya angkatan reguler tahun 2011 genap, dan semua pihak yang tidak dapat penulis sebutkan satu persatu pada tesis ini. Semoga Tuhan Yang Maha Kuasa membalas segala kebaikan dan bantuan yang telah diberikan.
Medan, Desember 2013 Penulis, Ruth Mayasari Simanjuntak
v Universitas Sumatera Utara
RIWAYAT HIDUP Ruth Mayasari Simanjuntak, dilahirkan di Tobasari pada tanggal 22 Juli 1983, merupakan anak keempat dari lima bersaudara dari ayah W. Simanjuntak dan ibunda A.Aritonang. Penulis menyelesaikan pendidikan Sekolah Dasar (SD) di SD Negeri 060925 Kabupaten Simalungun pada tahun 1995, Sekolah Lanjutan Tingkat Pertama (SLTP) di SLTP Pembangunan Kabupaten Simalungun pada tahun 1998, dan Sekolah Menengah Atas (SMA) di SMA RK Budi Mulia Pematangsiantar pada tahun 2001. Pada tahun 2002 penulis melanjutkan pendidikan sarjana Strata-1 pada Fakultas Matematika dan Ilmu Pengetahuan Alam jurusan Pendidikan Matematika di Universitas Negeri Medan dan memperoleh gelar Sarjana Pendidikan pada tahun 2007. Pada Februari 2012 penulis melanjutkan studi pada Program Studi Magister Matematika di FMIPA Universitas Sumatera Utara.
vi Universitas Sumatera Utara
DAFTAR ISI Halaman PERNYATAAN
i
ABSTRAK
ii
ABSTRACT
iii
KATA PENGANTAR
iv
RIWAYAT HIDUP
vi
DAFTAR ISI
vii
BAB 1 PENDAHULUAN
1
1.1 Latar Belakang
1
1.2 Perumusan Masalah
3
1.3 Tujuan Penelitian
4
1.4 Manfaat Penelitian
4
BAB 2 TINJAUAN PUSTAKA
5
2.1 Pertidaksamaan Variasional (Variational Inequalities)
5
2.2 Quasi-Variational Inequalities
7
2.3 Metode Pengali Lagrange
7
2.4 Equality dan Inequality Constraint (Kendala Persamaan dan Pertidaksamaan)
8
BAB 3 LANDASAN TEORITIS
9
3.1 Pendekatan Optimasi
9
3.2 Kondisi Convex
9
3.3 Kondisi Optimal KKT
10
3.4 Fungsi Simmetri
10 vii Universitas Sumatera Utara
3.5 Kesimetrian
12
3.6 Mereduksi Masalah Saddle-Point
13
BAB 4 PEMBAHASAN DAN HASIL
16
4.1 Metode yang Melibatkan Fungsi Modifikasi Lagrange
16
4.2 Metode Prediksi Type Proximal yang Menghubungkan Variabel Dual
20
4.3 Metode Prediksi Type Gradient yang Menghubungkan Variabel Primal dan Dual
23
4.4 Alternating Direction Method
27
4.5 Metode Proyeksi Sederhana
29
4.6 Metode Ekstragradien
29
BAB 5 KESIMPULAN DAN SARAN
31
5.1 Kesimpulan
31
5.2 Saran
31
DAFTAR PUSTAKA
32
viii Universitas Sumatera Utara
