## SIFAT KENDALA PEMROGRAMAN KERUCUT ORDER DUA DENGAN NORMA ∞
Caturiyati 1 , Ch. Rini Indrati 2 , Lina Aryati 2
1 Mahasiswa Pemrograman Studi S3 Matematika FMIPA UGM dan dosen Jurusan Pendidikan Matematika FMIPA UNY
2 Dosen Jurusan Matematika FMIPA UGM wcaturiyati@yahoo.com, rinii@ugm.ac.id, lina@ugm.ac.id

## 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

## PENDAHULUAN
Kerucut order dua (SOC) dalam Ben Tal  and  Nemirovski  (2001)  didefinisikan sebagai = = ( , … , ) ∈ ℝ ≥ + ⋯ + , ≥ 2,
dan pemrograman kerucut order dua (SOCP) adalah masalah konik:
meminimumkan { | − ≥ } , dengan  kerucut merupakan  hasil  kali langsung  ( direct  product )  dari  beberapa kerucut order dua:
= × × … × dan ≥ menyatakan  urutan  konik,  yaitu
≥ ⟺ − ≥ ⟺ − ∈ .
Pada  masalah  pemrograman  kerucut order dua, suatu fungsi linear diminimumkan  atas  irisan  himpunan  afine dan  hasil  kali  langsung  beberapa  kerucut order  dua.  SOCP  merupakan  masalah konveks  nonlinear  dengan  pemrograman linear dan pemrograman kuadratik
(konveks)  sebagai  kasus  khusus  (Andersen et. Al.,  2002,  Cao  et.al.,  2010,  Lobo  et. Al., 1998).  Dalam  beberapa  tahun  terakhir, masalah  SOCP  mendapat  perhatian  para peneliti  karena  jangkauan  aplikasinya  yang luas (Alizadeh and Goldfarb, 2003,
Andersen  et. Al.,  2002).  Masalah  optimisasi kerucut  order  dua  secara  teori  dapat diselesaikan  secara  efisien  menggunakan metode titik interior.
Dalam perkembangan penelitian
dibidang  optimisasi  terdapat  pergeseran- pergeseran struktur. Kwak (2008)
mengajukan  metode principal  component analysis (PCA) berdasarkan teknik optimisasi  yang  dikerjakan  dengan  norma
. Metode tersebut merupakan
pengembangan dari PCA berdasarkan norma .  Metode  PCA  tersebut  lebih  sederhana
dan  mudah  diimplementasikan.  Sehingga dirasakan perkembangan penelitian optimisasi akhir-akhir ini mempunyai kecenderungan  menggantikan  norma dengan norma (Schmidt, 2005).
Sementara  itu  Kahl  and  Hartley (2008)  menyajikan  kerangka  kerja  baru untuk  menyelesaikan  struktur  geometri  dan masalah  gerakan  berdasar  pada  norma ∞ daripada  menggunakan  fungsi cost norma .  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  gambar,  karena  metrik  jarak  gambar dari  kesalahan  proyeksi  ulangnya  juga invarian terhadap transformasi yang dimaksud. Dengan kata lain tidak memerlukan  normalisasi  koordinat  gambar. Selain  itu  berbagai  masalah  struktur  dan gerakan,  seperti  triangulasi,  pembagian ulang  kamera  dan  estimasi  homografi  dapat dinyatakan ulang sebagai masalah optimisasi quasi  konveks  yang  dapat  diselesaikan menggunakan  pemrograman  kerucut  order dua (SOCP).
Becker  et.al.  (2011)  membangun suatu  kerangka  kerja  untuk  menyelesaikan berbagai  masalah  kerucut  konveks  dengan pendekatan sebagai berikut: pertama, menentukan  formulasi  konik  dari  masalah; kedua, menentukan  dualnya; ketiga, aplikasi
penghalusan; keempat, menyelesaikan menggunakan  suatu  metode  optimal  order satu.  Kegunaan  pendekatan  ini  adalah fleksibilitasnya. Suatu estimator yang dipandang  efektif  secara  teori  dan  praktek adalah  pemilih  Dantzig  (Candes  and  Tao, 2005),  yang  ide  sederhananya  adalah mendapatkan  estimasi  konsisten  dari  data observasi  dan  meminimumkan  norma . Pemilih  Dantzig  merupakan  solusi  masalah pemrograman konveks sebagai berikut
meminimumkan ‖ ‖ , dengan
kendala ‖ ∗ ( − ) ‖ ≤ , dengan skalar  dan  diasumsikan kolom matriks   dinormalisasikan.
Berdasarkan referensi yang diuraikan  tersebut  dan  terutama  berdasarkan paper Lobo, et. al. (1998) yang menguraikan masalah  pemrograman  kerucut  order  dua maka  pada  paper  ini  akan  dibahas  masalah SOCP  dengan  mengubah  fungsi  kendala menjadi fungsi norma ∞ dengan domain ℝ .

## PEMBAHASAN
1. Kerucut Order Dua
Sebelum membicarakan pemrograman kerucut order dua (SOCP), akan dibicarakan terlebih  dahulu  mengenai  kerucut  order  dua (SOC) sebagai berikut.
Ben  Tal  dan  Nemirovski  mengatakan  suatu kerucut = ∈ ℝ ≻ , dengan ≻ ⟺ − ≻ dan ≻ suatu  urutan parsial,  adalah  suatu  kerucut  konveks pointed yang memenuhi syarat-syarat berikut:
1. tak  kosong  dan  tertutup  terhadap penjumlahan, , ∈ ⟹ + ′ ∈ 2. himpunan  konik, ∈ , ≥ 0 ⟹ ∈ 3. pointed, ∈ dan − ∈ ⟹ = .
Dengan  urutan  parsial  pada  himpunan    di
ℝ terdapat tiga macam kerucut berikut: 1. Ortan nonnegatif, ℝ = { = ( , … , ) | ≥ 0, = 1, … , } 2. Kerucut order dua = = ( , … , , ) ∈ ℝ ≥ ∑ . 3. Kerucut  semidefinit  positif, , kerucut dalam ruang yaitu ruang
matriks  berukuran × dan memuat  semua  matriks  semidefinit positif   berukuran × .

## 2. Pemrograman Kerucut Order Dua
Diberikan  definisi  pemrograman  konik berikut  dari  Ben  Tal  dan  Nemirovski. Misalkan    suatu  kerucut  di ℝ (konveks ,
pointed , tertutup,  dan  dengan  interior  tak kosong). Diberikan ∈ ℝ , matriks kendala berukuran × ,  dan  vektor  ruas  kanan ∈ ℝ ,  masalah  optimisasi  berikut  disebut dengan pemrograman konik, meminimumkan
, dengan kendala − ≥
dengan ≥ urutan  parsial  pada  himpunan kerucut  . Jika   adalah hasil kali langsung beberapa SOC, maka masalah pemrograman konik  tersebut  disebut  dengan  masalah SOCP.  Secara  umum  SOCP  dimodelkan sebagai berikut (Lobo et al),
meminimumkan , dengan kendala ‖ + ‖ ≤ + ( = 1, … , ) (1) dengan ∈ ℝ variabel  keputusan,  dan parameter ∈ ℝ , ∈ ℝ ( )× , ∈ ℝ , ∈ ℝ dan ∈ ℝ . Kendala ‖ + ‖ ≤ + disebut  kendala
SOC  berdimensi .  Berdasarkan  definisi,
SOC  standar  berdimensi didefinisikan sebagai,
= {( , )| ∈ ℝ , ∈ ℝ , ‖ ‖ ≤ }.
Untuk = 1 , = { | ∈ ℝ , 0 ≤ }, dan
secara  geometris  dapat  digambarkan  seperti
Gambar 1 berikut.
t . 0
Untuk = 2 ,
= {( , )| ∈ ℝ , ∈ ℝ , ‖ ‖ ≤ }
= {( , )| ∈ ℝ , ∈ ℝ , | | ≤ } = {( , )| ∈ ℝ , ∈ ℝ , − ≤ ≤ } ,
dan  secara  geometris  digambarkan  seperti Gambar 2 berikut.
Gambar 2. SOC
Untuk = 3 , =
{( , , )|( , ) ∈ ℝ , ∈ ℝ , ‖ ( , ) ‖ ≤ }
=
( , , ) ( , ) ∈ ℝ , ∈ ℝ , + ≤ , dan secara geometris digambarkan seperti Gambar 3 berikut.
Gambar 3. SOC
Lemma  1 .  (Ben  Tal  dan  Nemirovski,  2001)
Himpunan titik-titik yang memenuhi kendala
kerucut order  dua adalah  image invers  dari
kerucut order dua satuan terhadap pemetaan afine :
‖ + ‖ ≤ + ⟺ + ∈
dan konveks, i=1,2,...,N .
Bukti: Tanpa mengurangi keumuman,
diasumsikan = 1, = 2 = , =
, = ∈ ℝ ,  maka  parameter  masalah SOCP berdimensi 2 adalah
= , = , = ℎ ℎ , = ( , ) .
= = −
Kendala masalah SOCP berdimensi 2: ‖ + ‖ ≤ + ⟺ + ≤ [ ℎ ℎ ] + ⟺ + + + + ≤ ℎ + ℎ + ⟺ ( + + ) + ( + + ) ≤ ℎ + ℎ + ⟺ + + + +
ℎ + ℎ +
∈
⟺ + ∈ . 
3. Kerucut  Order  Dua  (SOC)  pada
SOCP dengan Norma ∞
Diberikan  masalah  SOCP  (1).  Apabila norma  pada  fungsi  kendala  masalah  SOCP (1) diubah menjadi fungsi kendala bernorma
∞ , maka diperoleh masalah SOCP:
meminimumkan , dengan kendala ‖ + ‖ ≤
+ ( = 1, … , )
(2)
dengan ∈ ℝ adalah  variabel  keputusan, dan  parameter ∈ ℝ , ∈ ℝ ( )× , ∈ ℝ , ∈ ℝ dan ∈ ℝ . Sebelum
membahas masalah SOCP (2), perlu didefinisikan  pengertian  SOC  norma ∞ sebagai berikut:
∗ = {( , )| ∈ ℝ , ∈ ℝ , ‖ ‖ ≤ }.
Namun dengan pengubahan tersebut terdapat  perbedaan  antara  SOC  standar (norma  2)  dengan  SOC  norma ∞ sebagai berikut:
Untuk = 1 , ∗ = { | ∈ ℝ , ‖ 0 ‖ ≤ } = { | ∈ ℝ , 0 ≤ } = . Untuk = 2 , ∗ = {( , )| ∈ ℝ , ∈ ℝ , ‖ ‖ ≤ } = {( , )| ∈ ℝ , ∈ ℝ , | | ≤ } = . Untuk = 3 , ∗ =
{( , , )|( , ) ∈ ℝ , ∈ ℝ , ‖ ( , ) ‖ ≤ } = {( , , )|( , ) ∈ ℝ , ∈ ℝ , | | + | | ≤ } ≠
.
Contoh  1. Merupakan  suatu counter example yang menunjukkan adanya perbedaan antara SOC norma 2 dengan SOC norma ∞ mulai = 3 sebagai berikut. Ambil = , = , = 1, , , ∈ ℝ .  Akan ditunjukkan ∗ ≠ .
Untuk ( , , ) ∈ , berlaku
+ ≤ ⟺ + = + = < 1 .
(3)
Sementara  itu  untuk ( , , ) ∈ ∗ berlaku
+ = > 1 .
(4)
Dari (3) dan (4) terbukti ∗ ≠ . 
Berikut ini adalah hasil yang diperoleh yang dinyatakan dalam Lemma 2 dan Lemma 3.
Lemma  2. Jika , , adalah  SOC
norma ‖ . ‖ dan ∗ , ∗ , ∗ adalah  SOC norma ‖ . ‖ ,  maka  berlaku ∗ = , ∗ = , tetapi ∗ ≠ . Bukti: Jelas ∗ = dan ∗ = , sedangkan untuk ∗ menurut definisinya
∗ = {( , , )|( , ) ∈ ℝ , ∈ ℝ , ‖ ( , ) ‖ ≤ } = {( , , )|( , ) ∈ ℝ , ∈ ℝ , | | + | | ≤ } ≠
.
Terbukti ∗ = , ∗ = ,  tetapi ∗ ≠ . 
Secara  geometris  perbedaan  antara ∗ dan terlihat seperti Gambat 4 berikut:
Gambar 4. SOC ∗
Lemma  3. Diberikan , , ∈ ℝ berlaku
+ ≤ ⇎ | | + | | ≤ .
Bukti: (dengan counter  example )  pada
Contoh 1.
Berikut  ini  akan  ditunjukkan  hasil  yang diperoleh  berupa  hubungan  kendala  SOCP standar dengan kendala SOCP norma ∞ dan hubungannya dengan pemetaan afine.
Lemma  4. Untuk  kendala  SOCP  (1)  dan kendala  SOCP  (2)  terhadap  pemetaan  afine berlaku hubungan sebagai berikut:
(i) ‖ + ‖ ≤ + ⟺ + ∈ ∗
(ii) ‖ + ‖ ≤ + ⇎
+ ∈ ∗ .
Bukti: Tanpa mengurangi keumuman diasumsikan = 1, = 2 = , =
, = ∈ ℝ ,  maka  parameter  masalah
SOCP berdimensi 2 adalah
= , = , = ℎ ℎ , = ( , ) .
(i) Diperoleh
‖ + ‖ ≤ + ⟺ | + + | + | +
+ | ≤ ℎ + ℎ +
∗
⟺ + + + + ℎ + ℎ + ∈ ∗ ⟺ + ∈ ∗ .
(ii) Didapatkan ‖ + ‖ ≤ + ⟺ ( + + ) + ( + + ) ≤ ℎ + ℎ + ⟺ + +
+ + ℎ + ℎ + ∈ ⟺ + ∈ . Sementara  telah  diketahui ≠ ∗ ,
sehingga  kendala  SOCP  (1)  tidak  ekuivalen dengan pemetaan afine di ∗ . 

## KESIMPULAN
a. Kerucut order dua norma ∞
mempunyai  perbedaan  dengan  kerucut order  dua  norma  2  mulai  pada  kerucut dimensi  3  sebagai  berikut ∗ =
, ∗ = , tetapi ∗ ≠ .
b. Akibat adanya perbedaan tersebut maka kendala  SOCP  (1)  menjadi  tidak ekuivalen dengan pemetaan afine di ∗ .
c. Dengan  adanya  perbedaan  tersebut maka pada masalah SOCP (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
Kompetensi  Dasar  Matematika SMP/MTs  dalam  Standar  Isi untuk  Satuan  Pendidikan  Dasar dan Menengah . Jakarta.
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  &
T.Andre (Eds.), Cognitive
classroom  learning (pp.49-82).
Orlando, FL: Academic Press. Hake, R. (1998). Interactive Engagement
v.s  Traditional  Methods:  Six-
Thousand  Student  Survey  Of Mechanics Test Data For Introductory Physics Courses. American  Journal  of  Physics ,  66
(1), 64-67 .
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 for Well- Structured and lll-structured Problem-Solving Learning Outcomes . Educational Technology Research and Development, 45 (1), 65-94.
Sobel  M.A  &  E.M.  Maletsky.  (2001).
Mengajar  Matematika.  Sebuah Buku 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 Training Teachers of Exceptional Children. A Source Book .
Blomington: Indiana University.
Tisngati, U. (2012). “Membangun
Karakter  Dalam  Pembelajaran Matematika  Melalui  Ketrampilan Komunikasi”. Prosiding . seminar
nasional matematika dan pendidikan matematika. 10
November  2012 .  Yogyakarta  :
Universitas Negeri Yogyakarta. Widyantini,  Th.  (2008). Paket  Fasilitasi
Pemberdayaan  KKG  dan MGMP
Matematika .  Yogyakarta:  Pusat Pengembangan dan Pemberdayaan Pendidik dan Tenaga  Kependidikan  (PPPPTK) Matematika. Winkel, W. S. (2009). Psikologi Pengajaran . Media Abadi: Yogyakarta.