PROSIDING
ISBN :
KEKONVEKSKAN DAERAH FISIBEL SECOND ORDER CONE PROGRAMMING DENGAN NORMA 1 Caturiyati1, Ch. Rini Indrati2, Lina Aryati2
1
Mahasiswa Program Studi S3 Matematika FMIPA UGM dan dosen Jurusan Pendidikan Matematika FMIPA UNY 2 Dosen Jurusan Matematika FMIPA UGM
[email protected],
[email protected],
[email protected]
Abstrak Pada makalah ini disampaikan kekonvekskan daerah fisibel Second Order Cone Programming dengan Norma 1. Kata kunci: daerah fisibel, Second Order Cone Programming
PENDAHULUAN Kekonvekskan merupakan satu hal yang penting dalam mempelajari masalah optimisasi. Terdapat banyak situasi dimana sifat-sifat kekonvekskan telah berkembang menjadi begitu penting. Sebagai contoh, di dalam masalah optimisasi titik-titik fisibel seringkali merupakan himpunan konveks. Kekonvekskan himpunan fisibel memainkan peranan dalam penentuan eksistensi solusi optimal, struktur himpunan solusi optimal, dan yang sangat penting bagaimana menyelesaikan masalah secara numerik. Telah banyak buku yang mengupas tentang himpunan konveks, diantaranya Rockafellar (1970), Dattorro (2005), dan Boyd and Vandenberghe (2004) membahas himpunan cone konveks. Karena demikian pentingnya masalah kekonvekskan maka pada paper ini dibahas mengenai kekonvekskan masalah SOCP norma . 1 . PEMBAHASAN Sebelum membahas masalah kekonvekskan, terlebih dahulu akan disampaikan definisi norma dan norma . 1 sebagai contohnya. Definisi 1. (Norma) Norma dari ruang vektor real atau kompleks V adalah fungsi . yang memetakan V ke β yang memenuhi syarat-syarat berikut: 1. π β₯ 0 dan π = 0 βΊ π = π 2. πΌπ = πΌ π untuk setiap skalar πΌ 3. π + π = π + π . Berikut ini adalah contoh norma 1 yang didefinisikan pada ruang vektor βπ . Contoh 1: Diberikan ruang vektor real βπ dan fungsi . 1 : βπ β β dengan π 1 = π₯1 , β¦ , π₯π 1 = π₯1 + β― + π₯π , π = π₯1 , β¦ , π₯π β βπ . Fungsi . 1 memenuhi aksioma-aksioma norma, yaitu: 1. π 1 β₯ 0. Untuk π = π₯1 , β¦ , π₯π β βπ berlaku π 1 = π₯1 , β¦ , π₯π 1 = π₯1 + β― + π₯π β₯ 0.
Makalah dipresentasikan dalam Seminar Nasional Matematika dan Pendidikan Matematika dengan tema β Kontribusi Pendidikan Matematika dan Matematika dalam Membangun Karakter Guru dan Siswa" pada tanggal 10 November 2012 di Jurusan Pendidikan Matematika FMIPA UNY
PROSIDING
π 1 = 0 βΊ π = π. Untuk π = π₯1 , β¦ , π₯π β βπ berlaku π
ISBN :
1
= π₯1 , β¦ , π₯π 1 = π₯1 + β― + π₯π = 0 βΊ π₯1 = 0, β¦ , π₯π = 0,
yaitu π = π. 2.
πΌπ 1 = πΌ π 1 untuk setiap skalar πΌ. Untuk π = π₯1 , β¦ , π₯π β βπ dan untuk sebarang skalar πΌ berlaku πΌπ 1 = πΌ π₯1 , β¦ , π₯π 1 = πΌπ₯1 , β¦ , πΌπ₯π 1 = πΌπ₯1 + β― + πΌπ₯π = πΌ π₯1 + β― + πΌ π₯π = πΌ π₯1 + β― + π₯π = πΌ π 1.
3.
π + π 1 = π 1 + π 1. Untuk π = π₯1 , β¦ , π₯π , π = y1 , β¦ , yπ β βπ berlaku π + π 1 = π₯1 + π¦1 , β¦ , π₯π + π¦π 1 = π₯1 + π¦1 + β― + π₯π + π¦π β€ π₯1 + π¦1 + β― + π₯π + π¦π = π₯1 + β― + π₯π + y1 + β― + yπ = π₯1 , β¦ , π₯π 1 + y1 , β¦ , yπ 1 = π 1 + π 1.
Selanjutnya disampaikan definisi-definisi mengenai kekonvekskan yang selanjutnya akan digunakan dalam pembahasan paper ini. Definisi 2. (Himpunan Konveks) Himpunan πΆ konveks jika untuk sebarang π₯1 , π₯2 β πΆ dan sebarang π dengan 0 β€ π β€ 1, diperoleh ππ₯1 + 1 β π π₯2 β πΆ. Definisi 3. (Cone) Himpunan πΆ disebut cone jika untuk setiap π₯ β πΆ dan π β₯ 0 maka ππ₯ β πΆ. Definisi 4. (Cone Konveks) Himpunan πΆ cone konveks jika πΆ konveks dan merupakan cone. Definisi 5. (Kombinasi Conic) Suatu titik berbentuk π1 π₯1 + β― + ππ π₯π dengan π1 , β¦ , ππ β₯ 0 disebut kombinasi conic π₯1 , β¦ , π₯π . Jika π₯π di cone konveks πΆ, maka setiap kombinasi conic π₯π di πΆ. Selanjutnya akan dibicarakan terlebih dahulu mengenai daerah fisibel. Definisi 6. (Solusi Fisibel) Solusi fisibel di dalam masalah optimisasi adalah solusi yang memenuhi semua kendala. Definisi 7. (Daerah Fisibel) Daerah fisibel di dalam masalah optimisasi adalah himpunan semua solusi fisibel yang mungkin. Daerah fisibel ini merupakan irisan semua kendala yang ada pada masalah optimisasinya. Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
2
PROSIDING
ISBN :
Sebelum membicarakan kekonvekskan daerah fisibel second order conic programming (SOCP) pada norma . 1 , akan dibicarakan mengenai SOC dan SOCP pada norma . 2 sebagai berikut. Ben Tal dan Nemirovski mengatakan suatu cone πΎ = π β βπ π β» π , dengan π β» π βΊ π β π β» π dan β» suatu urutan parsial, adalah suatu pointed convex cone yang memenuhi syarat-syarat berikut: 1. πΎ tak kosong dan tertutup terhadap penjumlahan, π, πβ² β πΎ βΉ π + πβ² β πΎ 2. πΎ himpunan conic, π β πΎ, π β₯ 0 βΉ ππ β πΎ 3. πΎ pointed, π β πΎ dan βπ β πΎ βΉ π = π. Dengan urutan parsial pada himpunan πΎ di βπ terdapat tiga macam cone berikut: 1. Ortan nonnegative cone, βπ+ = π = π₯1 , β¦ , π₯π π π₯π β₯ 0, π = 1, β¦ , π 2. Second Order Cone (SOC) πΆπ = π = π₯1 , β¦ , π₯πβ1 , π₯π
π
β βπ π₯π β₯
πβ1 2 π=1 π₯π
.
3. Semidefinit Positif Cone (SDC), π+π , cone dalam ruang π π yaitu ruang matriks berukuran π Γ π dan memuat semua matriks semidefinit positif π¨ berukuran π Γ π. Selanjutnya diberikan definisi program conic berikut dari Ben Tal dan Nemirovski. Definisi 8. Misalkan πΆ suatu cone di βπ (convex, pointed, closed, dan dengan interior tak kosong). Diberikan π β βπ , matriks kendala π¨ berukuran π Γ π, dan vektor ruas kanan π β βπ , masalah optimisasi berikut disebut dengan program conic, meminimumkan ππ π, dengan kendala π¨π β π β₯πΆ π dengan β₯πΆ urutan parsial pada himpunan cone πΆ. Jika πΆ adalah direct product beberapa SOC, maka masalah program conic di atas disebut dengan masalah second order cone programming (SOCP). Secara umum SOCP dimodelkan sebagai berikut (Lobo et al), meminimumkan ππ π, dengan kendala π¨π π + ππ 2 β€ πππ π + ππ (π = 1, β¦ , π) (1) π π (π π β1)Γπ dengan π β β variabel keputusan, dan parameter π β β , π¨π β β , ππ β βπ π β1 , ππ β βπ dan ππ β β . Kendala π¨π π + ππ β€ πππ π + π
π disebut kendala SOC berdimensi ππ . Definisi 9. (SOC) Second Order Cone norma . 2 berdimensi π didefinisikan sebagai π πΆπ = π’ β βπβ1 , π‘ β β, untuk t β₯ π 2 π‘ dengan π
2
=
πβ1 2 π=1 π’π .
Lemma 1. Second Order Cone πΆ merupakan himpunan konveks di βπ . Bukti: Lihat di NN. Berikut adalah sketsa Cone order dua dalam beberapa dimensi,
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
3
PROSIDING
ISBN :
Cone order dua berdimensi (a) π = 1, (b) π = 2, dan (c) π = 3. Kekonvekskan pada cone order dua norma . 1 Didefinisikan terlebih dahulu mengenai SOC norma . 1 sebagai berikut. (Caturiyati dkk, 2012) Definisi 10. (SOC norma . 1 ). Second Order Cone norma . 1 berdimensi π didefinisikan sebagai π πΆπβ = π’ β βπβ1 , π‘ β β, untuk t β₯ π 1 π‘ dengan π 1 = π’1 + β― + π’π β1 . Definisi 11. (SOCP norma . 1 ) (Caturiyati dkk, 2012) SOCP norma . 1 dimodelkan sebagai berikut, meminimumkan ππ π, dengan kendala π¨π π + ππ 1 β€ πππ π + ππ (π = 1, β¦ , π) (2) dengan π β βπ variabel keputusan, dan parameter π β βπ , π¨π β β(π π β1)Γπ , ππ β βπ π β1 , ππ β βπ dan ππ β β . Kendala π¨π π + ππ 1 β€ πππ π + π
π disebut kendala SOC norma . 1 berdimensi ππ . Selanjutnya akan diuraikan suatu lemma kekonvekskan SOC norma . 1 berikut. Lemma 2. Diberikan suatu cone order dua norma . 1 πΆπβ = π, π‘ π β βπβ1 , π‘ β β, π 1 β€ π‘ , akan ditunjukkan πΆπβ konveks untuk setiap π. Bukti: Ambil sebarang π = π1 , π‘1 , π = π2 , π‘2 β πΆπβ dengan π1 1 β€ π‘1 dan π2 1 β€ π‘2 dan suatu skalar π β 0,1 , diperoleh π1 π2 ππ1 + 1 β π π2 π π‘ + 1βπ π‘ = ππ‘1 + 1 β π π‘2 1 2 dengan ππ1 + 1 β π π2 1 β€ π π1 1 + 1 β π π2 1 β€ ππ‘1 + 1 β π π‘2 . Terbukti πΆπβ adalah himpunan konveks. Lemma 3. (Kekonvekskan Irisan SOC Norma . π ). Jika πΆπβπ , π = 1, β¦ , π adalah SOC norma . 1 yang konveks untuk setiap π , maka πΆ β = πΆπβ1 β© πΆπβ2 β© β¦ β© πΆπβπ himpunan konveks. Bukti: Ambil sebarang π, π β πΆ β dan π β [0,1]. Akan ditunjukkan ππ + (1 β π)π β πΆ β . Karena π, π β πΆπβ1 β© πΆπβ2 β© β¦ β© πΆπβπ , maka π, π β πΆπβ1 dan π, π β πΆπβ2 dan ...dan π, π β πΆπβπ . Karena πΆπβ1 , πΆπβ2 , β¦ , πΆπβπ konveks, maka ππ + (1 β π)π β πΆπβ1 dan ππ + (1 β π)π β πΆπβ2 dan ...dan ππ + (1 β π)π β πΆπβπ . Sehingga ππ + (1 β π)π β πΆ β .
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
4
PROSIDING
ISBN :
Lemma 4. (Kekonvekskan pada SOCP norma . π ). Untuk kendala SOCP terhadap pemetaan affine berlaku hubungan sebagai berikut: π¨π π π¨π π + ππ 1 β€ πππ π + ππ βΊ π π + π β πΆπβ , ππ ππ maka irisan kendala pada SOCP norma . 1 adalah himpunan konveks. Bukti: Lihat Lemma 4 Caturiyati dkk, 2012 dan Lemma 3 paper ini. KESIMPULAN Karena SOC norma .
1
konveks maka masalah SOCP norma .
1
juga konveks.
DAFTAR PUSTAKA Ben Tal, A. and Nemirovski, A. 2001. Lectures on Modern Convex Optimization : Analysis, Algorithms, and Engineering applications. MPS SIAM series on Application. Philadelphia. Boyd, S., and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press, Cambridge. Caturiyati, Ch. Rini Indrati, dan Lina Aryati. 2012. Second Order Cone (Soc) Dan Sifat-Sifat Kendala Second Order Cone Programming Dengan Norma 1. Dipresentasikan pada Seminar Nasional Matematika dan Pendidikan Matematika di FMIPA UNY, 10 Nopember 2012. Dattorro, J. 2005. Convex Optimization & Euclidean Distance Geometry. Meboo Publishing USA, California. Lobo, M.S., Vandenberghe, L., Boyd, S., and Lebret, H. 1998. Applications of second-order cone programming. Linear Algebra and Its Applications, vol 284, pp. 193-228. NN, Chapter 14 Semidefinite and Second-Order Cone Programming. Diunduh dari http://shmathsoc.org.cn/lu/core%20part/Chap14.pdf pada tanggal 10 Oktober 2012. Rockafellar, R.T., 1970. Convex Analysis. Princenton University Press. Princenton, New Jersey.
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
5
PROSIDING
ISBN :
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
6