PROSIDING
ISBN :
SECOND ORDER CONE (SOC) DAN SIFAT-SIFAT KENDALA SECOND ORDER CONE PROGRAMMING DENGAN NORMA 1 Caturiyati1, Ch. Rini Indrati2, Lina Aryati2 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] 1
Abstrak Pada makalah ini dikembangkan pengertian Second Order Cone (SOC) dan sifat sifat kendala Second Order Cone Programming dengan Norma 1. Kata kunci: Second Order Cone (SOC), Second Order Cone Programming
PENDAHULUAN Cone order dua (second order cone/SOC) [9] didefinisikan sebagai πΏπ = π± = π₯1 , β¦ , π₯π β βπ π₯π β₯
2 π₯12 + β― + π₯π β1 , π β₯ 2,
dan program cone order dua (Second-order cone programming/SOCP) adalah masalah conic: meminimumkan ππ π π¨π β π β₯πΎ π , dengan cone πΎ merupakan hasil kali langsung (direct product) dari beberapa cone order dua: πΎ = πΏπ 1 Γ πΏπ 2 Γ β¦ Γ πΏπ π dan β₯πΎ menyatakan urutan conic, yaitu π β₯πΎ π βΊ π β π β₯πΎ π βΊ π β π β πΎ. Pada masalah program cone order dua, suatu fungsi linear diminimumkan atas irisan himpunan afine dan hasil kali langsung beberapa cone order dua. SOCP merupakan masalah konveks nonlinear dengan program linear dan program kuadratik (konveks) sebagai kasus khusus [2,5,8]. Dalam beberapa tahun terakhir, masalah SOCP mendapat perhatian para peneliti karena jangkauan aplikasinya yang luas [1,2]. Masalah optimisasi cone order dua secara teori dapat diselesaikan secara efisien menggunakan metode titik interior. Dalam perkembangan penelitian di bidang optimisasi terdapat pergeseran-pergeseran struktur. Kwak [7] mengajukan metode principal component analysis (PCA) berdasarkan teknik optimisasi yang dikerjakan dengan norma πΏ1 . Metode tersebut merupakan pengembangan dari PCA konvensional berdasarkan norma πΏ2 . Metode PCA yang dikerjakan Kahl lebih sederhana dan mudah diimplementasikan. Perkembangan penelitian optimisasi akhir-akhir ini mempunyai kecenderungan menggantikan norma πΏ2 dengan norma πΏ1 [10].
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
ISBN :
Sementara itu Kahl [6] menyajikan kerangka kerja baru untuk menyelesaikan struktur geometri dan masalah gerakan berdasar pada norma πΏβ daripada menggunakan fungsi cost norma πΏ2 . Kerangka kerja ini menghasilkan komputasi estimasi global yang efisien, dalam arti solusinya invarian terhadap transformasi proyektif pada sistem koordinat dunia dan similaritas transformasi dalam bidang image, karena metrik jarak image dari error reproyektif juga invarian terhadap transformasi yang dimaksud. Dengan kata lain tidak memerlukan normalisasi koordinat image. Selain itu berbagai masalah struktur dan gerakan, seperti triangulasi, resection kamera dan estimasi homografi dapat dinyatakan ulang sebagai masalah optimisasi quasi konveks yang dapat diselesaikan menggunakan program cone order dua (SOCP). Becker [3] membangun suatu kerangka kerja untuk menyelesaikan berbagai masalah cone konveks dengan pendekatan sebagai berikut: pertama, menentukan formulasi conic dari masalah; kedua, menentukan dualnya; ketiga, aplikasi smoothing; keempat, menyelesaikan menggunakan suatu metode optimal order satu. Kegunaan pendekatan ini adalah fleksibilitasnya. Suatu estimator yang dipandang efektif secara teori dan praktek adalah selector Dantzig [4], yang ide prosedur sederhananya: mendapatkan estimasi yang konsisten dari data observasi dan mempunyai norma π1 yang minimum. Selector Dantzig adalah solusi program konveks meminimumkan π 1 , dengan kendala π¨β π β π¨π β β€ πΏ, dengan πΏ skalar dan diasumsikan kolom matriks π΄ dinormalisasikan. Berdasarkan referensi yang diuraikan tersebut dan terutama berdasarkan paper Lobo, et. al. [8] yang menguraikan masalah program cone order dua maka pada paper ini akan dibahas masalah SOCP dengan mengubah fungsi kendala menjadi fungsi norma 1 dengan domain βπ+. PEMBAHASAN 1. Second Order Cone Sebelum membicarakan second order conic programming (SOCP), akan dibicarakan terlebih dahulu mengenai SOC sebagai berikut. Untuk itu akan dibicarakan dulu beberapa hal terkait SOC. 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 nonnegatif, βπ π₯π β₯ 0, π = 1, β¦ , π + = π = π₯1 , β¦ , π₯π 2. Cone order dua πΆπ = π = π₯1 , β¦ , π₯π β1 , π₯π
π
β βπ π₯π β₯
πβ1 2 π=1 π₯π
.
3. Cone semidefinit positif, π+π , cone dalam ruang π π yaitu ruang matriks berukuran π Γ π dan memuat semua matriks semidefinit positif π¨ berukuran π Γ π.
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
2
PROSIDING
ISBN :
2. Second Order Cone Programming Diberikan definisi program conic berikut dari Ben Tal dan Nemirovski. 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) dengan π β βπ variabel keputusan, dan parameter π β βπ , π¨π β β(π π β1)Γπ , ππ β βπ π β1 , ππ β βπ dan ππ β β . Kendala π¨π π + ππ β€ πππ π + π
π disebut kendala SOC berdimensi ππ . Berdasarkan definisi, SOC standar berdimensi π didefinisikan sebagai, πΆπ = π, π‘ π β βπ β1 , π‘ β β, π 2 β€ π‘ . Untuk π = 1, πΆ1 = π‘ π‘ β β, 0 β€ π‘ , dan secara geometris dapat digambarkan seperti Gambar 1 berikut. πΆ1
.
t
0
Gambar 1. SOC πΆ1 Untuk π = 2, πΆ2 = π’, π‘ π’ β β, π‘ β β, π’ 2 β€ π‘ = π’, π‘ π’ β β, π‘ β β, π’ β€ π‘ = π’, π‘ π’ β β, π‘ β β, βπ‘ β€ π’ β€ π‘ , dan secara geometris digambarkan seperti Gambar 2 berikut. π‘ π‘ = βπ’
π‘=π’ πΆ2 π’ Gambar 2. SOC πΆ2
Untuk π = 3, πΆ3 = π₯, π¦, π‘ π₯, π¦ β β2 , π‘ β β, π₯, π¦ 2 β€ π‘ = π₯, π¦, π‘ π₯, π¦ β β2 , π‘ β β, π₯ 2 + π¦ 2 β€ π‘ , dan secara geometris digambarkan seperti Gambar 3 berikut.
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
3
PROSIDING
ISBN :
π§
πΆ3 π₯ π¦ Gambar 3. SOC πΆ3 Lemma 1. Himpunan titik-titik yang memenuhi kendala cone order dua adalah image invers dari cone order dua satuan terhadap pemetaan affine: π¨π π π¨π π + ππ 2 β€ πππ π + π
π βΊ π π + π β πΆ3 ππ ππ dan konveks, i=1,2,...,N. Bukti: Tanpa mengurangi keumuman, diasumsikan π = 1, ππ = 2 = π, ππ = π, ππ = π β β, maka parameter masalah SOCP berdimensi 2 adalah π1 π11 π12 β π¨= π , π = π , π = 1 , ππ = π₯1 , π₯2 π . π β2 21 22 2 Kendala masalah SOCP berdimensi 2: π¨π + π 2 β€ ππ π + π π1 π11 π12 π₯1 π₯1 βΊ π + π β€ β1 β2 π π₯ + π π π₯ 21 22 2 2 2 2 π11 π₯1 + π12 π₯2 + π1 βΊ π π₯ +π π₯ +π β€ β1 π₯1 + β2 π₯2 + π 21 1 22 2 2 2 π11 π₯1 + π12 π₯2 + π1 2 + π21 π₯1 + π22 π₯2 + π2 2 β€ β1 π₯1 + β2 π₯2 + π π11 π₯1 + π12 π₯2 + π1 π¨ π π βΊ 21 π₯1 + π22 π₯2 + π2 β πΆ3 βΊ π π + β πΆ3 . οΌ π π β1 π₯1 + β2 π₯2 + π βΊ
3. Second Order Cone (SOC) pada SOCP dengan Norma 1 Diberikan masalah SOCP (1). Apabila norma pada fungsi kendala masalah SOCP (1) diubah menjadi fungsi kendala bernorma 1, maka diperoleh masalah SOCP: meminimumkan ππ π, dengan kendala π¨π π + ππ 1 β€ πππ π + ππ (π = 1, β¦ , π) (2) π π (π π β1)Γπ dengan π β β adalah variabel keputusan, dan parameter π β β , π¨π β β , ππ β βπ π β1 , ππ β βπ dan ππ β β. Sebelum membahas masalah SOCP (2), perlu didefinisikan pengertian SOC norma 1 sebagai berikut: πΆπβ = π, π‘ π β βπβ1 , π‘ β β, π 1 β€ π‘ . Namun dengan pengubahan tersebut terdapat perbedaan antara SOC standar (norma 2) dengan SOC norma 1 sebagai berikut: Untuk π = 1, πΆ1β = π‘ π‘ β β, 0 1 β€ π‘ = π‘ π‘ β β, 0 β€ π‘ = πΆ1 . Untuk π = 2, πΆ2β = π’, π‘ π’ β β, π‘ β β, π’ 1 β€ π‘ = π’, π‘ π’ β β, π‘ β β, π’ β€ π‘ = πΆ2 . Untuk π = 3, πΆ3β = π₯, π¦, π‘ π₯, π¦ β β2 , π‘ β β, π₯, π¦ 1 β€ π‘ = π₯, π¦, π‘ π₯, π¦ β β2 , π‘ β β, π₯ + π¦ β€ π‘ β πΆ3 . Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
4
PROSIDING
ISBN :
Contoh 1. Merupakan suatu counter example. Ambil π₯ = 12, π¦ = 34, π‘ = 1, π₯, π¦, π‘ β β. Akan ditunjukkan πΆ3β β πΆ3 . Untuk π₯, π¦, π‘ β πΆ3 , berlaku π₯2 + π¦2 β€ π‘ βΊ
1 2
2
+
3 4
2
Sementara itu untuk π₯, π¦, π‘ β πΆ3β berlaku Dari (3) dan (4) terbukti πΆ3β β πΆ3 . οΌ
1 4
= 1 2
+
3 4
+
9 16
=
13 16
< 1.
= 54 > 1.
(3) (4)
Lemma 2. Jika πΆ1 , πΆ2 , πΆ3 adalah SOC norma . 2 dan πΆ1β , πΆ2β , πΆ3β adalah SOC norma . 1 , maka berlaku πΆ1β = πΆ1 , πΆ2β = πΆ2 , tetapi πΆ3β β πΆ3 . Bukti: Jelas πΆ1β = πΆ1 dan πΆ2β = πΆ2 , sedangkan untuk πΆ3β menurut definisinya πΆ3β = π₯, π¦, π‘ π₯, π¦ β β2 , π‘ β β, π₯, π¦ 1 β€ π‘ = π₯, π¦, π‘ π₯, π¦ β β2 , π‘ β β, π₯ + π¦ β€ π‘ β πΆ3 . Terbukti πΆ1β = πΆ1 , πΆ2β = πΆ2 , tetapi πΆ3β β πΆ3 . οΌ Secara geometris perbedaan antara πΆ3β dan πΆ3 terlihat seperti Gambat 4 berikut: π§
πΆ3β π₯ π¦ Gambar 4. SOC πΆ3β Lemma 3. Diberikan π₯, π¦, π‘ β β berlaku π₯ 2 + π¦ 2 β€ π‘ β π₯ + π¦ β€ π‘. Bukti: (dengan counter example) pada Contoh 1. Berikut ini akan ditunjukkan hubungan kendala SOCP standar dengan kendala SOCP norma 1 dan hubungannya dengan pemetaan affine. Lemma 4. Untuk kendala SOCP (1) dan kendala SOCP (2) terhadap pemetaan affine berlaku hubungan sebagai berikut: π¨π π (i) π¨π π + ππ 1 β€ πππ π + ππ βΊ π π + π β πΆ3β ππ ππ π¨ π π (ii) π¨π π + ππ 2 β€ πππ π + ππ β π π + π β πΆ3β. ππ ππ Bukti: Tanpa mengurangi keumuman diasumsikan π = 1, ππ = 2 = π, ππ = π, ππ = π β β, maka parameter masalah SOCP berdimensi 2 adalah π1 π11 π12 β1 π¨= π , π = , π = , ππ = π₯1 , π₯2 π . π2 β2 21 π22 (i) Diperoleh
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
5
PROSIDING
ISBN :
β€ ππ π + π βΊ π11 π₯1 + π12 π₯2 + π1 + π21 π₯1 + π22 π₯2 + π2 β€ π11 π₯1 + π12 π₯2 + π1 π¨ π β1 π₯1 + β2 π₯2 + π βΊ π21 π₯1 + π22 π₯2 + π2 β πΆ3β βΊ π π + β πΆ3β . π π β1 π₯1 + β2 π₯2 + π (ii) Didapatkan π¨π + π 2 β€ ππ π + π βΊ π11 π₯1 + π12 π₯2 + π1 2 + π21 π₯1 + π22 π₯2 + π2 2 β€ β1 π₯1 + β2 π₯2 + π π11 π₯1 + π12 π₯2 + π1 π¨ π βΊ π21 π₯1 + π22 π₯2 + π2 β πΆ3 βΊ π π + β πΆ3 . π π β1 π₯1 + β2 π₯2 + π Sementara telah diketahui πΆ3 β πΆ3β , sehingga kendala SOCP (1) tidak ekuivalen dengan pemetaan affine di πΆ3β.οΌ π¨π + π
1
KESIMPULAN a. πΆ1β = πΆ1 , πΆ2β = πΆ2 , tetapi πΆ3β β πΆ3 . b. Kendala SOCP (1) tidak ekuivalen dengan pemetaan affine di πΆ3β. c. Masalah SOCP (2) memerlukan sejumlah teori tambahan agar teori-teori pada SOCP (1) berlaku pada SOCP (2). DAFTAR PUSTAKA Alizadeh, F. and Goldfarb, D., Second-order Cone programming, Math. Program, 95, 3-51, 2003. Andersen, E.D., Roos, C., and Terlaky, T., Notes on duality in second order and π-order Cone optimization, A Journal of Mathematical Programming and Operation Research, Volume 51, Issue 4, pages 627-643, 2002. Becker, S., Candes, E.J. and Grant, M., Templates for convex Cone problems with applications to sparse signal recovery, Mathematical Programming Computation, Vol 3, Number 3, 165-218, 2011. Ben Tal, A. and Nemirovski, A., Lectures on Modern Convex Optimization : Analysis, Algorithms, and Engineering applications, MPS SIAM series on Application, Philadelphia, 2001.Candes, E.J. and Tao, T., The Dantzig selector: statistical estimation when p is much larger than n, Annals of Statistics, pages 2313-2351, 2005. Cao, Q., Yu, Z., and Wang, A., A Boxed Optimization Reformulation for the Convex Second Order Cone Programming, AMO-Advanced Modeling and Optimization, Volume 12, Number 1, 2010. Kahl, F. And Hartley, R., Multiple View Geometry Under the πΏβ -norm, IEEE Transactions Analysis Machine Intelligence, Volume: 30, Issue: 9, pages 1603-1617, 2008. Kwak, N., Principal Component Analysis based on πΏ1 -norm Maximization, IEEE Transactions Analysis Machine Intelligence, Volume: 30, Issue: 9, pages 1672-1680, 2008. Lobo, M.S., Vandenberghe, L., Boyd, S., and Lebret, H., Applications of second-order Cone programming, Linear Algebra and its Applications 284, 193-228, 1998.
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
6
PROSIDING
ISBN :
Schmidt, M., Least squares optimization with πΏ1 -norm regularization, 2005. Diunduh dari http://www.di.ens.fr/~mschmidt/Software/lasso.pdf tanggal 20 Mei 2012
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
7
PROSIDING
ISBN :
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
8