Vol. 7, No. 2, Desember 2012
SIFAT KENDALA PEMROGRAMAN KERUCUT ORDER DUA DENGAN NORMA ∞ Caturiyati1, Ch. Rini Indrati2, Lina Aryati2 Mahasiswa Pemrograman Studi S3 Matematika FMIPA UGM dan dosen Jurusan Pendidikan Matematika FMIPA UNY 2 Dosen Jurusan Matematika FMIPA UGM
1
[email protected],
[email protected],
[email protected] Abstrak Masalah pemrograman kerucut order dua (Second Order Cone Programming/SOCP) dengan norma ∞ merupakan suatu masalah yang merupakan bentuk khusus dari masalah pemrograman kerucut order dua dengan norma 2. Pada makalah ini dikembangkan pengertian kerucut order dua (Second Order Cone/SOC) dengan norma ∞ dan sifat sifat kendala pemrograman kerucut order dua dengan Norma ∞ berdasarkan pada pengertian kerucut order dua dengan norma 2 dan pemrograman kerucut order dua dengan norma 2. Paper ini ditulis dengan menguraikan pengertian kerucut order dua dengan norma 2 dan pemrograman kerucut order dua dengan norma 2, dilanjutkan dengan mengembangkan pengertian kerucut order dua dengan norma ∞ dan pemrograman kerucut order dua dengan norma ∞ besera sifat-sifat yang dihasilkannya. Kata kunci: Second Order Cone (SOC), Second Order Cone Programming
Tal and Nemirovski (2001) didefinisikan
PENDAHULUAN Kerucut order dua (SOC) dalam Ben = ( ,…,
=
)∈ℝ
sebagai ≥
+⋯+
,
≥ 2,
dan pemrograman kerucut order dua (SOCP)
(konveks) sebagai kasus khusus (Andersen
adalah masalah konik:
et. Al., 2002, Cao et.al., 2010, Lobo et. Al.,
meminimumkan |
{
−
1998). Dalam beberapa tahun terakhir,
},
≥
dengan kerucut
masalah SOCP mendapat perhatian para merupakan hasil kali
peneliti karena jangkauan aplikasinya yang
langsung (direct product) dari beberapa
luas
kerucut order dua:
Andersen et. Al., 2002). Masalah optimisasi
= dan ≥ ≥
×
kerucut
× …×
menyatakan urutan konik, yaitu ⟺
−
≥
⟺
−
∈ .
dua,
suatu
fungsi
linear
order
and
dua
Goldfarb,
2003,
secara teori dapat
diselesaikan secara efisien menggunakan metode titik interior. Dalam
Pada masalah pemrograman kerucut order
(Alizadeh
perkembangan
penelitian
dibidang optimisasi terdapat pergeseran-
diminimumkan atas irisan himpunan afine
pergeseran
dan hasil kali langsung beberapa kerucut
mengajukan metode principal component
order
analysis
dua.
SOCP merupakan
masalah
konveks nonlinear dengan pemrograman linear
dan
pemrograman
kuadratik
struktur.
(PCA)
Kwak
(2008)
berdasarkan
teknik
optimisasi yang dikerjakan dengan norma .
Metode
tersebut
merupakan
9
Sifat Kendala Pemrograman Kerucut...... (Caturiyati dkk)
pengembangan dari PCA berdasarkan norma
penghalusan;
keempat,
menyelesaikan
. Metode PCA tersebut lebih sederhana
menggunakan suatu metode optimal order
dan mudah diimplementasikan. Sehingga
satu. Kegunaan pendekatan ini adalah
dirasakan
fleksibilitasnya.
perkembangan
optimisasi
akhir-akhir
penelitian
ini
mempunyai
Suatu
estimator
yang
dipandang efektif secara teori dan praktek
kecenderungan menggantikan norma
adalah pemilih Dantzig (Candes and Tao,
dengan norma
2005),
(Schmidt, 2005).
Sementara itu Kahl and Hartley
yang
ide
sederhananya
adalah
mendapatkan estimasi konsisten dari data
(2008) menyajikan kerangka kerja baru
observasi dan meminimumkan norma
untuk menyelesaikan struktur geometri dan
Pemilih Dantzig merupakan solusi masalah
masalah gerakan berdasar pada norma
pemrograman konveks sebagai berikut
∞
.
Kerangka
kerja
ini
menghasilkan
∗(
kendala ‖
kolom matriks
transformasi proyektif pada sistem koordinat
dengan
)‖ ≤ ,
−
dengan
komputasi estimasi global yang efisien, dalam arti solusinya invarian terhadap
‖ ‖ ,
meminimumkan
daripada menggunakan fungsi cost norma
.
skalar dan diasumsikan dinormalisasikan.
Berdasarkan
referensi
yang
dunia dan similaritas transformasi dalam
diuraikan tersebut dan terutama berdasarkan
bidang gambar, karena metrik jarak gambar
paper Lobo, et. al. (1998) yang menguraikan
dari kesalahan proyeksi ulangnya juga
masalah pemrograman kerucut order dua
invarian
yang
maka pada paper ini akan dibahas masalah
tidak
SOCP dengan mengubah fungsi kendala
memerlukan normalisasi koordinat gambar.
menjadi fungsi norma ∞ dengan domain ℝ .
terhadap
dimaksud.
Dengan
transformasi kata
lain
Selain itu berbagai masalah struktur dan gerakan,
seperti
triangulasi,
pembagian
PEMBAHASAN
ulang kamera dan estimasi homografi dapat
1.
dinyatakan ulang sebagai masalah optimisasi
Sebelum
quasi konveks yang dapat diselesaikan
kerucut order dua (SOCP), akan dibicarakan
menggunakan pemrograman kerucut order
terlebih dahulu mengenai kerucut order dua
dua (SOCP).
(SOC) sebagai berikut.
Becker et.al. (2011) membangun
Kerucut Order Dua
kerucut
berbagai masalah kerucut konveks dengan
≻
berikut:
=
⟺
pertama,
parsial,
menentukan formulasi konik dari masalah;
pointed
kedua, menentukan dualnya; ketiga, aplikasi
berikut:
10
sebagai
pemrograman
Ben Tal dan Nemirovski mengatakan suatu
suatu kerangka kerja untuk menyelesaikan
pendekatan
membicarakan
−
∈ℝ ≻
,
dengan
dan ≻ suatu urutan
adalah suatu yang
≻
kerucut
memenuhi
konveks
syarat-syarat
Vol. 7, No. 2, Desember 2012
1.
tak kosong dan tertutup terhadap penjumlahan,
,
∈
⟹
Dengan urutan parsial pada himpunan
+ ′∈
ℝ terdapat tiga macam kerucut berikut: 1. Ortan
2.
∈
himpunan konik,
, ≥0⟹
ℝ
nonnegatif,
=
{ = ( ,…,
∈ 3.
∈
pointed,
dan − ∈
di
⟹
) |
≥ 0, = 1, … ,
2. Kerucut order dua
= .
= ( ,…,
=
3. Kerucut semidefinit positif,
, ,
) ∈ℝ
∑
≥
dengan ≥
.
urutan parsial pada himpunan
kerucut dalam ruang
yaitu ruang
kerucut
matriks
×
dan
beberapa SOC, maka masalah pemrograman
memuat semua matriks semidefinit
konik tersebut disebut dengan masalah
positif
berukuran
berukuran
×
. Jika
adalah hasil kali langsung
SOCP. Secara umum SOCP dimodelkan
.
sebagai berikut (Lobo et al), 2.
meminimumkan
Pemrograman Kerucut Order Dua
Diberikan
definisi
pemrograman
dengan kendala ‖
konik
+
berikut dari Ben Tal dan Nemirovski. suatu kerucut di ℝ
Misalkan
kosong). Diberikan
∈ ℝ , matriks kendala
+
‖ ≤
( = 1, … , )
(konveks,
pointed, tertutup, dan dengan interior tak
,
(1) ∈ℝ
dengan
variabel keputusan, dan ∈ℝ ,
parameter
∈ ℝ(
)×
,
∈
× , dan vektor ruas kanan
ℝ
,
∈ℝ
dan
∈ ℝ.
Kendala
∈ ℝ , masalah optimisasi berikut disebut
‖
+
‖≤
+
disebut
kendala
berukuran
dengan pemrograman konik, meminimumkan kendala
−
SOC berdimensi ,
dengan
≥
= 1,
SOC standar berdimensi
didefinisikan
sebagai, = {( , )| ∈ ℝ
Untuk
. Berdasarkan definisi,
= { | ∈ ℝ, 0 ≤ }, dan
, ∈ ℝ, ‖ ‖ ≤ }.
Gambar 1 berikut.
secara geometris dapat digambarkan seperti
.
0
t
Gambar 1. SOC
11
}
Sifat Kendala Pemrograman Kerucut...... (Caturiyati dkk)
Untuk
= 2,
dan secara geometris digambarkan seperti
= {( , )| ∈ ℝ, ∈ ℝ, ‖ ‖ ≤ }
Gambar 2 berikut.
= {( , )| ∈ ℝ, ∈ ℝ, | | ≤ } = {( , )| ∈ ℝ, ∈ ℝ, − ≤
≤ },
=−
=
Gambar 2. SOC = 3,
Untuk =
( , , ) ( , ) ∈ ℝ , ∈ ℝ,
+
≤
, dan
{( , , )|( , ) ∈ ℝ , ∈ ℝ, ‖( , )‖ ≤ }
secara
geometris
digambarkan
seperti
Gambar 3 berikut. =
Gambar 3. SOC
Lemma 1. (Ben Tal dan Nemirovski, 2001)
kerucut
order
Himpunan titik-titik yang memenuhi kendala
pemetaan afine:
dua
satuan
terhadap
kerucut order dua adalah image invers dari ‖
+
‖ ≤
+
⟺
+
∈
dan konveks, i=1,2,...,N. Bukti:
Tanpa
mengurangi = 1,
diasumsikan =
keumuman,
= 2 = , ,
=
, =
= ℎ , ℎ
,
=
∈ ℝ, maka parameter masalah
SOCP berdimensi 2 adalah =( ,
) .
12
Vol. 7, No. 2, Desember 2012
Kendala masalah SOCP berdimensi 2: ‖ ⟺ + +
+ +
⟺ (
+
+
+ + +ℎ
⟺ ℎ ⟺ 3.
≤ [ℎ
+
⟺
+
+ ‖ ≤ ℎ ]
≤ℎ
+
+ℎ
) +(
+ + +
+
+
+
) ≤ℎ
+
+ℎ
+
∈
.
∈
∗
= 1,
Kerucut Order Dua (SOC) pada
Untuk
SOCP dengan Norma ∞
{ | ∈ ℝ, 0 ≤ } =
Diberikan masalah SOCP (1). Apabila
= { | ∈ ℝ, ‖0‖
≤ }=
. = 2,
Untuk ∗
norma pada fungsi kendala masalah SOCP
= {( , )| ∈ ℝ, ∈ ℝ, ‖ ‖ ≤ }
(1) diubah menjadi fungsi kendala bernorma ∞, maka diperoleh masalah SOCP: meminimumkan
,
dengan kendala ‖ +
= {( , )| ∈ ℝ, ∈ ℝ, | | ≤ } =
. = 3,
Untuk ∗
‖ ≤
+
( = 1, … , )
=
{( , , )|( , ) ∈ ℝ , ∈ ℝ, ‖( , )‖ ≤ }
(2) dengan
∈ℝ
adalah variabel keputusan, ∈ℝ ,
dan parameter ℝ
,
∈ℝ
membahas
∈ ℝ( ∈ ℝ.
dan
masalah
)×
SOCP
,
∈
= {( , , )|( , ) ∈ ℝ , ∈ ℝ, | | + | | ≤ } ≠ .
Sebelum (2),
perlu
didefinisikan pengertian SOC norma ∞
Contoh
sebagai berikut:
example
∗
= {( , )| ∈ ℝ
, ∈ ℝ, ‖ ‖ ≤ }.
1.
Merupakan
yang
dengan
pengubahan
tersebut
counter
menunjukkan
adanya
perbedaan antara SOC norma 2 dengan SOC norma ∞ mulai
Namun
suatu
= ,
Ambil
= 3 sebagai berikut. = , = 1, , , ∈ ℝ. Akan
∗
≠
terdapat perbedaan antara SOC standar
ditunjukkan
(norma 2) dengan SOC norma ∞ sebagai
Untuk ( , , ) ∈
. , berlaku
berikut: +
≤ ⟺
+
=
+
=
< 1.
(3) Sementara itu untuk ( , , ) ∈
∗
berlaku
+
= > 1.
13
Sifat Kendala Pemrograman Kerucut...... (Caturiyati dkk)
∗
(4) Dari (3) dan (4) terbukti
∗
.
≠
=
{( , , )|( , ) ∈ ℝ , ∈ ℝ, ‖( , )‖ ≤ }
Berikut ini adalah hasil yang diperoleh yang =
dinyatakan dalam Lemma 2 dan Lemma 3. Lemma 2. Jika
,
,
norma ‖. ‖
∗
∗
dan
,
adalah SOC ,
∗
, tetapi Bukti:
∗
≠
Jelas
sedangkan untuk
adalah SOC ∗
norma ‖. ‖ , maka berlaku
{( , , )|( , ) ∈ ℝ , ∈ ℝ, | | + | | ≤ } ≠
=
,
∗
=
. Terbukti
∗
=
∗
,
=
, tetapi
∗
≠
.
. ∗
=
∗
∗
menurut definisinya
dan
=
, ∗
Secara geometris perbedaan antara
dan
terlihat seperti Gambat 4 berikut:
∗
∗
Gambar 4. SOC
Lemma 3. Diberikan +
, , ∈ ℝ berlaku
(ii)
‖
‖ ≤
+
≤ ⇎| |+| |≤ .
+
+ ∗
∈
⇎
.
Bukti: (dengan counter example) pada Bukti:
Contoh 1.
Tanpa
mengurangi = 1,
diasumsikan Berikut ini akan ditunjukkan hasil yang diperoleh berupa hubungan kendala SOCP
,
=
=
,
(i)
‖ ⟺|
+
14
‖ ≤ ∈
+ ∗
⟺
ℎ , ℎ
, =
=
) .
Diperoleh
berlaku hubungan sebagai berikut: +
=
( ,
kendala SOCP (2) terhadap pemetaan afine ‖
=
∈ ℝ, maka parameter masalah
hubungannya dengan pemetaan afine.
(i)
=2= ,
SOCP berdimensi 2 adalah
standar dengan kendala SOCP norma ∞ dan
Lemma 4. Untuk kendala SOCP (1) dan
keumuman
+ ‖ ≤ + +
|≤ℎ
+ +
|+|
+ℎ
+
+
Vol. 7, No. 2, Desember 2012
+ + +ℎ
⟺ ℎ ⟺
+ + +
+
∗
∈
∈
Kompetensi Dasar Matematika
∗
SMP/MTs
Isi
untuk Satuan Pendidikan Dasar
.
dan Menengah. Jakarta.
(ii) Didapatkan ‖
dalam Standar
+ ‖ ≤
Bransford, J. dan B.S. Stein. (1993). The
+
IDEAL Problem Solver: A Guide
⟺ (
+
ℎ
+ℎ
⟺ ℎ
) +(
+
+
+
for
Improving
) ≤
Thinking,
Learning, and Creativity (2nd
+ + + +ℎ
ed). New York: W.H. Freeman.
+ + +
∈
Grabe, M. (1986). Attentional processes in education. In G. Phye &
⟺
+
∈
.
Sementara telah diketahui
∗
≠
,
sehingga kendala SOCP (1) tidak ekuivalen ∗
dengan pemetaan afine di
.
Kerucut
order
dua
∞
norma
order dua norma 2 mulai pada kerucut , b.
∗
=
3
sebagai
, tetapi
∗
∗
berikut ≠
SOCP
(1)
menjadi
tidak ∗
.
Dengan adanya perbedaan tersebut maka
learning
pada
masalah
Cognitive (pp.49-82).
Orlando, FL: Academic Press.
SOCP
Traditional
Methods:
Thousand
Student
Mechanics
Test
Introductory
Six-
Survey
Of
Data
For
Physics
Courses.
American Journal of Physics, 66 (1), 64-67.
.
ekuivalen dengan pemetaan afine di c.
=
Akibat adanya perbedaan tersebut maka kendala
classroom
v.s
mempunyai perbedaan dengan kerucut
dimensi
(Eds.),
Hake, R. (1998). Interactive Engagement
KESIMPULAN a.
T.Andre
(2)
diperlukan sejumlah teori tambahan agar teori-teori pada SOCP (1) berlaku pada SOCP (2).
DAFTAR PUSTAKA
Badan Standar Nasional Pendidikan. (2006). Standar Kompetensi dan
Henton, J., Baden. R.M. dan Kieren, D., (1979). Problem Solving in the Classroom.
The
Family
Coordinator, 28 (1), 61-66. Jonassen, D.H. (1997). Instructional Design
Models
Structured
for
Well-
and
lll-structured
Problem-Solving
Learning
Outcomes. Technology
Educational Research
and
Development, 45 (1), 65-94.
15
Sifat Kendala Pemrograman Kerucut...... (Caturiyati dkk)
Sobel M.A & E.M. Maletsky. (2001).
W.
S.
Mengajar Matematika. Sebuah
Pengajaran.
Buku
Yogyakarta.
Sumber
Alat
Peraga,
Aktivitas dan Strategi. Jakarta: Erlangga. Sudjana, N. (2005).
Penilaian Hasil
Proses Belajar Mengajar. Jakarta: PT. Remaja Rosdakarya. Sukestiyarno, YL. (2012). Olah Data Penelitian
berbantuan
SPSS.
Semarang: UNNES. Thiagarajan, S., D. S. Semmel and M. I. Semmel.
(1974). Instructional
Development
for
Teachers
of
Children.
A
Training Exceptional
Source
Book.
Blomington: Indiana University. Tisngati,
U.
(2012).
Karakter
“Membangun
Dalam Pembelajaran
Matematika Melalui Ketrampilan Komunikasi”. Prosiding. seminar nasional
matematika
pendidikan
dan
matematika.
10
November 2012. Yogyakarta : Universitas Negeri Yogyakarta. Widyantini, Th. (2008). Paket Fasilitasi Pemberdayaan KKG dan MGMP Matematika. Yogyakarta: Pusat Pengembangan Pemberdayaan
dan Pendidik
dan
Tenaga Kependidikan (PPPPTK) Matematika.
16
Winkel,
(2009). Media
Psikologi Abadi:
