BAB I PENDAHULUAN
1.1
Latar Belakang Masalah
Setiap manusia memiliki kebutuhan yang harus dipenuhi. Kebutuhan manusia untuk setiap orangnya berbeda-beda, baik dari kuantitas maupun dari kualitas. Di zaman modern saat ini, begitu banyak barang dan atau jasa yang diberikan untuk memenuhi kebutuhan setiap manusia. Meskipun demikian, kebutuhan manusia jumlahnya tak sebanding dengan barang dan atau jasa yang tersedia. Oleh karena itu, dibutuhan keputusan atau kebijakan dalam memilih barang dan atau jasa yang digunakan untuk memenuhi kebutuhan manusia. Disinilah peran penting matematika, khususnya optimisasi dalam mendasari keputusan ataupun kebijakan dalam memilih barang dan atau jasa yang digunakan untuk memenuhi kebutuhan manusia. Optimisasi adalah salah satu bidang ilmu di matematika yang mempelajari tentang pemilihan sistematis nilai variabel real atau bulat dari suatu himpunan yang meminimalkan atau memaksimalkan suatu fungsi real. Optimisasi yang sering dikenalkan adalah program linear. Program linear telah banyak digunakan di berbagai bidang antara lain ekonomi, teknik, industri, dan lain-lain. Meski demikian, banyak masalah optimisasi yang tidak dapat diselesaikan dengan program linear, contohnya antara lain adalah masalah meminimalkan norma dan program kuadratik berkendala kuadrat. Oleh karena itu, mempelajari optimisasi selain program linear diperlukan dan bermanfaat untuk menyelesaikan masalah-masalah optimisasi yang lebih luas, salah satunya adalah program kerucut orde dua (second order cone programming). Program kerucut orde dua atau second order cone programming (SOCP) adalah masalah optimisasi yang meminimalkan fungsi tujuan linear atas kendala sistem persamaan linear dan cartesian product sebanyak berhingga dari kerucut orde dua atau second order cone (SOC). Alizadeh dan Goldfarb (2003) menyatakan bahwa beberapa masalah optimisasi dapat diformulasikan menjadi SOCP antara lain program linear, masalah meminimalkan norma, program kuadratik berkendala kuadrat, dan lain-lain. Berdasarkan latar belakang tersebutlah penulis tertarik dan menganggap penting untuk mempelajari SOCP lebih lanjut.
1
2
1.2
Perumusan Masalah Rumusan masalah yang dibahas dalam skripsi ini adalah:
1. Definisi dan sifat dari himpunan kerucut (cone), pointed, dan SOC di ruang Rn atas R. 2. Definisi dan sifat dari primal-dual SOCP. 3. Sifat aljabar dari SOC. 4. Algoritma primal-dual titik interior untuk menyelesaikan primal-dual SOCP. 1.3
Batasan Masalah
Pada penulisan skripsi ini, penulis membatasi masalah pada perumusan masalah di skripsi ini. Skripsi ini hanya membahas sifat sederhana dari himpunan kerucut, pointed, dan SOC yang digunakan untuk pembahasan selanjutnya di skripsi ini. Selain itu, tidak dibahas mengenai masalah-masalah optimisasi yang dapat diformulasikan menjadi SOCP dan teori dualitas dari SOCP, serta tidak dibahas mengenai konsep-konsep Aljabar Jordan Euclidean yang bersesuaian dengan SOC untuk melandasi pembentukan algoritma primal-dual titik interior. Aljabar Jordan Euclidean tersebut dianggap sebagai sifat aljabar dari SOC dan lebih dipandang sebagai ruang vektor dilengkapi dengan operasi biner yang komutatif dan bilinear, sebab memerlukan penelitian tersendiri secara terpisah. 1.4
Maksud dan Tujuan
Selain untuk memenuhi syarat kelulusan Program Strata-1 (S1) Program Studi Matematika Universitas Gadjah Mada, penyusunan skripsi ini bertujuan untuk memahami optimisiasi SOCP, terkait mengenai SOC dan primal-dual SOCP. Selanjutnya, untuk memahami salah satu algoritma primal-dual titik interior untuk SOCP, sehingga masalah primal-dual SOCP dapat diselesaikan. 1.5
Tinjauan Pustaka
Pada skripsi ini, digunakan sejumlah buku dan jurnal sebagai acuan. Sebagai acuan utama dari skripsi ini adalah buku karangan Faraut dan Koranyi (1994), jurnal
3
karangan Alizadeh dan Goldfarb (2003), dan jurnal karangan Wang dan Bai (2009). Pembahasan terkait himpunan kerucut dan pointed diacu berdasarkan buku karangan Faraut dan Koranyi (1994) yang membahas sedikit definisi himpunan konveks, kerucut, dan pointed untuk pengantar symmetric cone. Pembahas mengenai definisi dan sifat dari SOC, primal-dual SOCP, dan sifat aljabar dari SOC diacu berdasarkan jurnal Alizadeh dan Goldfarb (2003). Selain itu, sifat aljabar dari SOC diacu juga dari jurnal karangan Wang dan Bai (2009). Kedua jurnal tersebut menjelaskan bahwa sifat aljabar dari SOC merupakan suatu Aljabar Jordan Euclidean dan memberikan ide untuk pembentukan algoritma primal-dual titik interior untuk primal-dual SOCP berdasarkan sifat aljabar dari SOC tersebut. Pembahasan mengenai algoritma primaldual titik interior untuk SOCP di skripsi ini diacu pada jurnal karangan Wang dan Bai (2009). Algoritma di jurnal karangan Wang dan Bai (2009) dibentuk berdasarkan sifat aljabar dari SOC yang sama dengan di jurnal karangan Alizadeh dan Goldfarb (2003), tetapi ide untuk pembentukan algoritma yang diberikan sedikit berbeda. Pembentukan algoritma di jurnal karangan Wang dan Bai (2009) menggunakan fungsi injektif bernilai real pada [0, +∞) di R dan diferensiabel pada (0, +∞), dengan ψ 0 (t) > 0 untuk setiap t > 0, untuk mencari arah perbaikan dan diberikan juga analisis untuk algoritma tersebut. Untuk dasar teori mengenai ruang Rn , digunakan buku karya Bartle dan Sherbert (2000) dan Bartle (1976). Bartle (1976) membicarakan mengenai konsep topologi, barisan, dan fungsi kontinu di ruang Rn dan Bartle dan Sherbert (2000) membicarakan mengenai ruang Rn untuk kasus n = 1. Untuk dasar teori mengenai matriks bilangan real, digunakan buku acuan karya Bellman (1970) yang membicarakan mengenai matriks bilangan real terkait persamaan karakteristik, nilai eigen, vektor eigen, matriks simetris, matriks ortogonal, definit positif, dan diagonalisasi matriks simetris. Untuk dasar teori mengenai matriks blok (partisi), digunakan buku karya Zhang (2011) yang membahas mengenai teori matriks. Untuk dasar teori mengenai relasi himpunan, digunakan buku acuan karya Goodaire dan Parmenter (2003) yang membahas mengenai relasi suatu himpunan dan jenis-jenis dari relasi. Adapun buku atau jurnal lain yang digunakan sebagai acuan penunjang/tambahan dalam skripsi ini, khususnya untuk sifat aljabar dari SOC dan algoritma primaldual titik interior untuk SOCP adalah jurnal karangan Wang dan Bai (2012) dan jurnal karangan Schmieta dan Alizadeh (2003) yang membicarakan mengenai algoritma primal-dual titik interior untuk symmetric optimization, dengan SOCP sebagai kejadian khususnya. Selain itu, untuk primal-dual SOCP adalah buku karangan Ben-tal
4
dan Nemirovski (2001) yang membicarakan himpunan konveks, kerucut, dan pointed di ruang Rn , serta conic programming dengan SOCP sebagai kejadian khususnya. 1.6
Metodologi Penelitian
Metode yang digunakan dalam pembuatan skripsi ini adalah dengan terlebih dahulu melakukan studi literatur mengenai himpunan kerucut (cone) dan pointed di ruang Rn . Setelah itu, dilakukan studi literatur mengenai sifat di ruang Rn terkait himpunan konveks, topologi, barisan, dan fungsi kontinu, serta dilanjutkan melakukan studi literatur mengenai relasi pada himpunan dan matriks bilangan real. Pemahaman himpunan kerucut (cone) dan pointed di ruang Rn diperlukan untuk memahami bahwa kerucut orde dua (SOC) merupakan himpunan kerucut (cone) dan pointed di ruang Rn . Pemahaman di ruang Rn dan relasi himpunan diperlukan untuk membuktikan bahwa SOC merupakan himpunan tertutup, konveks, dan himpunan semua titik interiornya tidak kosong di ruang Rn dan terdapat suatu relasi urutan parsial di ruang Rn berdasarkan SOC. Pemahaman mengenai sifat dari SOC yang diperoleh kemudian digunakan untuk membahas sifat dari cartesian product sebanyak berhingga dari SOC. Pemahaman mengenai sifat cartesian product sebanyak berhingga dari SOC yang diperoleh kemudian digunakan untuk memahami program kerucut orde dua (SOCP) dan sifat terkait primal-dual SOCP, khususnya syarat cukup solusi optimal dari primal-dual SOCP. Pemahaman mengenai matriks bilangan real terkait persamaan karakteristik, nilai eigen, vektor eigen, matriks simetris, matriks ortogonal, definit positif, dan diagonalisasi matriks simetris diperlukan untuk selanjutnya mempelajari sifat aljabar dari SOC. Sifat aljabar dari SOC disini merupakan salah satu contoh dari Aljabar Jordan Euclidean, tetapi di skripsi ini dipandang sebagai ruang Rn dilengkapi dengan operasi biner ◦. Berdasarkan hasil pembahasan mengenai sifat aljabar dari SOC dengan pemahaman matriks blok bilangan real, dapat diperluas untuk cartesian product sebanyak berhingga dari SOC. Berdasarkan hasil perluasan dari sifat aljabar dari SOC untuk cartesian product sebanyak berhingga dari SOC, selanjutnya dipelajari algoritma primal-dual titik interior untuk SOCP. Kemudian, berdasarkan pemahaman mengenai matriks bilangan real dan fungsi kontinu di R dipelajari mengenai analisis dari algoritma primal-dual titik interior tersebut agar terdefinisi dengan baik atau menuju solusi optimal dari primal-dual SOCP.
5
1.7
Sistematika Penulisan Pada penulisan skripsi ini, penulis menggunakan sistematika sebagai berikut.
BAB I PENDAHULUAN Pada bab ini dibahas mengenai latar belakang, perumusan masalah, maksud dan tujuan penulisan skripsi, tinjauan pustaka, metodologi penelitian, serta sistematika penulisan. BAB II DASAR TEORI Pada bab ini dibahas tentang relasi, ruang Rn atas R sebagai ruang bernorma dengan norma standar, dan sifat-sifat tentang matriks bilangan real. BAB III PROGRAM KERUCUT ORDE DUA Pada bab ini dibahas mengenai definisi himpunan kerucut (cone) dan pointed di Rn , definisi dan sifat dari SOC, serta definisi dan sifat dari primal-dual SOCP. BAB IV SIFAT ALJABAR UNTUK KERUCUT ORDE DUA Pada bab ini dibahas mengenai sifat aljabar untuk SOC. Sifat aljabar di bab ini adalah terkait ruang Rn atas R dilengkapi dengan operasi biner ◦ yang memiliki hubungan dengan SOC. Selanjutnya, operasi biner ◦ diperluas menjadi ◦r , sehingga ruang Rn dilengkapi ◦r memiliki hubungan dengan cartesian product dari sebanyak r SOC. BAB V ALGORITMA PRIMAL-DUAL TITIK INTERIOR UNTUK PROGRAM KERUCUT ORDE DUA Pada bab ini dibahas mengenai pembentukan algoritma primal-dual titik interior untuk SOCP. Pembentukan algoritma primal-dual titik interior ini dilandasi dari sifat aljabar yang dibahas pada bab IV. BAB VI PENUTUP Pada bab ini berisi kesimpulan-kesimpulan yang diperoleh dari penulisan ini, beserta saran-saran yang dapat diambil berdasarkan materi-materi yang telah dibahas pada bab-bab sebelumnya.
