## Optimasi Masalah Convex Quadratic Programming dengan Metode Primal Dual Interior Point

## Nurwahidah
Universitas Islam Negeri Alauddin Makassar, nurwahidah.abidin@uin-alauddin.ac.id
ABSTRAK , Quadratic programming adalah permasalahan  optimasi  untuk  memaksimumkan  atau meminimumkan  fungsi  tujuan  kuadratik  dan  kendala berbentuk linear . Quadratic programming dapat diselesaikan  menggunakan  metode  simpleks,  hanya  saja metode interior point lebih efisien dalam menemukan titik ekstrim  yang  optimal.  Metode primal  dual merupakan metode interior point untuk masalah quadratic programming yang  lebih  efektif  dalam  penyelesaian masalah skala besar atau lebih dari 2 variabel .
Kata  Kunci:  optimasi,  quadratic  programming,  primal dual, interior pont

## 1. PENDAHULUAN
Dalam  kehidupan  sehari-hari,  manusia cenderung untuk ingin memperoleh keuntungan semaksimal mungkin dan meminimalisir kerugian.  Hal  ini  berarti  manusia  melakukan optimasi  dalam  memenuhi  keperluan  hidupnya. Akan  tetapi,  masyarakat  awam  lebih  banyak menggunakan intuisi dalam menerapkan konsep optimasi.  Kasus  optimasi  dapat  dirumuskan menggunakan  model  matematika.  Optimasi diartikan  sebagai  sebuah  usaha  dalam  mencari atau menentukan nilai maksimum atau minimum dari  suatu  fungsi.  Dengan  kata  lain,  optimasi merupakan  penentuan  nilai  terbaik  yang didasarkan pada fungsi tujuan dengan daerah asal yang terdefinisi.
Suatu masalah optimasi disebut non linear apabila  salah  satu  atau  keduanya  dari  fungsi tujuan  dan  fungsi  kendala  berbentuk  non linear[1].  Optimasi  non  linear  merupakan  suatu konsep  yang  membutuhkan  pengetahuan  terkait kalkulus  dan  aljabar  linear.  Selain  itu, penyelesaian  masalah  optimasi  non  linear  juga membutuhkan algoritma numerik. Optimasi non linear  memerlukan  metode  penentuan  nilai optimal  global  agar  tidak  terjebak  dalam pencapaian nilai optimal local [2].
Quadratic programming merupakan sebuah  teknik  dalam  menyelesaikan  masalah optimasi  non  linear  dengan  fungsi  tujuan kuadratik dan kendala berbentuk linear.
Quadratic  programming dapat  diterapkan  pada berbagai  masalah  dalam  bidang  industri  dan keuangan  [5]. Quadratic  programming dapat diselesaikan  menggunakan  metode  simpleks, hanya  saja  metode interior  point lebih  efisien dalam  menemukan  titik  ekstrim  yang  optimal. Metode interior point yang dapat menyelesaikan masalah quadratic  programming terdiri  atas metode primal  affine  scaling dan primal  dual interior  point .  Metode primal  affine  scaling merupakan metode  interior  point ynag  paling sederhana , sedangkan primal  dual merupakan metode interior  point yang  lebih  efektif  dari metode  simpleks  untuk  penyelesaian  masalah skala besar.
Penelitian  ini  memaparkan  penyelesaian masalah  program  non  linear  kuadratik  untuk fungsi  konveks  dengan  metode primal  dual interior  point Penelitian  ini  dibuat  setelah dilakukan kajian literatur dari beberapa buku dan artikel  ilmiah  yang  telah  terbit.  Tujuan  dari penelitian  ini  adalah  agar  pembaca  dapat membentuk  model  matematika  dari  masalah optimasi  non  linear.  Penelitian  ini  diharapkan dapat menjadi  salah satu alat bantu  dalam studi terkait  persoalan  alokasi  sumber-sumber  secara optimal  dan  mencari  keuntungan  maksimum masalah  optimasi  non  linear  dengan  metode primal dual interior point .

## 2. TINJAUAN PUSTAKA
Fungsi Konveks Holder Stolz dan Hadamard
memperkenalkan  fungsi  konveks  pada  tahun 1889-1893.  Fungsi  konveks  diterapkan  pada ketaksamaan  Hadamard  pada  tahun  1893  [3]. Bentuk  umum  fungsi  konveks  adalah  sebagai berikut:
𝑓((1 − 𝑡)𝑥 1 + 𝑡𝑥 2 ) ≤ (1 − 𝑡)𝑓(𝑥 1 ) + 𝑡𝑓(𝑥 2 )
(2.1)
dimana ∀ 0 ≤ 𝑡 ≤ 1 dan 𝑥 1 , 𝑥 2 merupakan sebarang  anggota  dari  daerah  asal 𝑓 .  Fungsi konveks merupakan fungsi dengan karakteristik
garis yang menghubungkan titik (𝑥 1 , 𝑓((𝑥 1 )) dan (𝑥 2 , 𝑓((𝑥 2 )) selalu terletak di atas fungsi 𝑓 .

## Metode Pengali Lagrange
Metode Pengali Lagrange sering
digunakan  pada  penyelesaian  optimasi  dengan kendala  tertentu.  Prinsip  metode  ini  adalah mencari nilai optimal suatu fungsi tujuan f (x, y) dengan  kendala  tertentu,  yaitu  g  (x,  y)  =  0. Fungsi  Lagrange  dapat  dituliskan  sebagai berikut:
𝐹(𝑥, 𝑦, 𝜆) = 𝑓(𝑥, 𝑦) + 𝜆𝑔(𝑥, 𝑦)             (2.2) dengan syarat ekstrim:
𝜕𝐹 𝜕𝑥 = 0, 𝜕𝐹 𝜕𝑦 = 0, 𝑑𝑎𝑛 𝜕𝐹 𝜕𝜆 = 0
Dimana 𝜆 adalah pengali Lagrange.
Metode  pengali  Lagrange  dengan  lebih dari  satu  fungsi  kendala  dapat  ditambahkan parameter  menjadi 𝜆, 𝜇 atau  parameter  lain. Misal untuk memperoleh nilai ekstrim 𝑓(𝑥, 𝑦, 𝑧) dengan  batasan 𝑔(𝑥, 𝑦, 𝑧) = 0 dan ℎ(𝑥, 𝑦, 𝑧) = 0 , maka fungsi Lagrange yang dibentuk adalah: 𝐹(𝑥, 𝑦, 𝑧, 𝜆, 𝜇) = 𝑓(𝑥, 𝑦, 𝑧) + 𝜆𝑔(𝑥, 𝑦, 𝑧) + 𝜇ℎ(𝑥, 𝑦, 𝑧) .                    (2.3) Solusinya  adalah  dengan  mencari  penyelesaian dari
𝜕𝐹 𝜕𝑥 = 0, 𝜕𝐹 𝜕𝑦 = 0, 𝜕𝐹 𝜕𝑧 = 0, 𝜕𝐹 𝜕𝜆 = 0, 𝜕𝐹 𝜕𝜇 = 0.
Metode  ini  dapat  diperluas  untuk  n variabel 𝑓(𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 ) dengan  k  kendala 𝜙 1 (𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 ), 𝜙 2 (𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 ), … , 𝜙 𝑘 (𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 ). Fungsi Lagrange yang dibentuk adalah: 𝐹(𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 , 𝜆 1 , 𝜆 2 , … , 𝜆 𝑛 ) = 𝑓 + 𝜆 1 𝜙 1 + 𝜆 2 𝜙 2 + ⋯ + 𝜆 𝑘 𝜙 𝑘 .                                     (2.4) Solusinya  adalah  dengan  mencari  penyelesaian dari:
𝜕𝐹 𝜕𝑥 1 = 0, 𝜕𝐹 𝜕𝑥 2 = 0, … , 𝜕𝐹 𝜕𝑥 𝑛 = 0, 𝜕𝐹 𝜕𝜆 1 = 0, 𝜕𝐹 𝜕𝜆 2 = 0, … , 𝜕𝐹 𝜕𝜆 𝑛 = 0 dimana 𝜆 1 , 𝜆 2 , … , 𝜆 𝑛 adalah pengali Lagrange.

## Quadratic Programming
Quadratic Programming (QP) atau pemrograman  kuadrat  adalah  permasalahan optimasi untuk memaksimumkan atau meminimumkan  fungsi  tujuan  yang  berbentuk kuadrat  dengan  fungsi  kendala  berbentuk persamaan atau pertidaksamaan linear.  Masalah
quadratic  programming secara  umum  dapat dituliskan sebagai berikut:
(𝑄𝑃) { 𝑚𝑖𝑛 𝑥 1 2 𝑥 𝑇 Σ𝑥 +   𝑐 𝑇 𝑥
𝑠. 𝑡. 𝐴𝑥 = 𝑏 𝑥 ≥ 0 (2.5) Berdasarkan masalah (2.1), akan ditentukan  nilai  x  yang  dapat  meminimalkan fungsi  tujuan 1 2 𝑥 𝑇 Σ𝑥 +   𝑐 𝑇 𝑥 dengan  kendala 𝐴𝑥 = 𝑏 dan 𝑥 ≥ 0 .
Keterangan: x : Vektor variabel optimasi (𝑛 × 1) A : Matriks koefisien kendala (𝑛 × 𝑚) b : Vektor kendala ruas kanan (𝑚 × 1)
c : Vektor yang memuat koefisien suku-suku linear pada fungsi kendala (𝑛 × 1)
Σ : Matriks Hessian, matriks dengan koefisien  dari  suku  berpangkat  dua  atau suku  campuran  dari  fungsi  tujuan (𝑛 ×
𝑛) .
Fungsi  tujuan  dari  masalah quadratic programming merupakan fungsi konveks apabila Σ merupakan  matriks positive  semidefinite atau 𝑥 𝑇 Σ𝑥 ≥ 0 untuk  setiap 𝑥 .  Dengan  demikian, ketika Σ merupakan matriks positive semidefinite, maka  masalah  (2.5)  merupakan masalah  optimasi  konveks,  dimana  solusi optimal  lokal  juga  merupakan  solusi  optimal global.

## Bentuk Primal dan Dual
Masalah  (2.5)  dapat  disebut  berbentuk primal.  Setiap  bentuk  primal  akan  memiliki “bayangan”  yang  disebut  bentuk  dual. Penyelesaian  permasalahan  optimasi  dapat dilakukan  tanpa  melibatkan  bentuk  dual. Keberadaan dual dapat memudahkan penyelesaian  masalah,  karena  bentuk  dual biasanya lebih sederhana daripada primalnya.
Sistem  (2.1)  juga  dapat  diubah  ke  bentuk dual, sebagai berikut: (𝑄𝐷) { 𝑚𝑎𝑥 𝑥,𝑣,𝑢 − 1 2 𝑥 𝑇 Σ𝑥 +   𝑣 𝑇 𝑏 𝑠. 𝑡. Σ𝑥 + 𝑐 − 𝑢 − 𝐴 𝑇 𝑣 = 0 𝑢 𝑖 ≥ 0, 𝑖 = 1,2, … 𝑛 (2.6)
dimana 𝑣 merupakan  vektor  pengali  Lagrange yang bersesuaian dengan kendala persamaan dan 𝑢 ≥ 0 merupakan  vektor  pengali  Lagrange dengan kendala positif.
Optimasi Masalah Convex Quadratic Programming dengan Metode Primal Dual Interior Point • 54

## Kondisi Karush-Kuhn-Tucker (KKT)
Kondisi  optimal  penyelesaian quadratic programming akan  tercapai  jika  memenuhi kondisi  KKT.  Jika  dihadapkan  pada  masalah optimasi dalam bentuk: max/min 𝑍 = 𝑓(𝑥), 𝑋 = {𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 } s.t 𝑔 𝑖 (𝑥) ≤ 0 atau 𝑔 𝑖 (𝑥) ≥ 0, 𝑖 = 1,2, … , 𝑚 𝑋 ≥ 0 𝑚 ≤ 𝑛
Langkah  pertama  adalah  menuliskan  kembali fungsi  kendala  yang  memiliki  tanda  lebih  kecil atau sama dengan, kemudian menambah variabel slack berturut-turut  pada  ruas  kiri  kendala sehingga  setiap  ketidaksamaan  menjadi  suatu kesamaan.  Variabel  surplus  yang  dikurangkan dari model matematik kendala untuk mengkonversi pertidaksamaan ≥ menjadi persamaan ( =) , sedangkan penambahan slack ke model matematik kendala dengan
mengkonversikan  pertidaksamaan ≤ menjadi persamaan (=).
Teorema  1  memberikan  kondisi  Kuhn- tucker  untuk  memecahkan  persoalan  linear berkendala.
Teorema  1, Diasumsikan 𝑓(𝑥), 𝑔 1 (𝑥), 𝑔 2 (𝑥), … , 𝑔 𝑛 (𝑥) merupakan fungsi yang dapat diturunkan,  maka 𝑥 ∗ = (𝑥 1 ′ , 𝑥 2 ′ , … , 𝑥 𝑛 ′ ) menjadi solusi optimal untuk permasalahan pemrograman  nonlinear  masalah  minimasi hanya  jika  terdapat  sejumlah  m  bilangan 𝑣 1 , 𝑣 2 , … , 𝑣 𝑚 sehingga  semua  syarat  kondisi KKT berikut terpenuhi :
(i) 𝜕𝑓 𝜕𝑥 𝑗 + ∑ 𝑣 𝑖 𝑚 𝑖=1 𝜕𝑔 𝜕𝑥 𝑗 ≥ 0 , 𝑥 = 𝑥 ∗ , 𝑗 = 1,2, … , 𝑛 (ii) 𝑥 𝑗 ( 𝜕𝑓 𝜕𝑥 𝑗 + ∑ 𝑣 𝑖 𝑚 𝑖=1 𝜕𝑔 𝜕𝑥 𝑗 ) = 0, 𝑥 = 𝑥 ∗ 𝑗 = 1,2, … , 𝑛 (iii) 𝜕𝑓 𝜕𝑣 𝑖 + ∑ 𝑣 𝑖 𝑚 𝑖=1 𝜕𝑔 𝜕𝑣 𝑖 ≤ 0 , 𝑖 = 1,2, … , 𝑚
(iv) 𝑣 𝑖 𝑔 𝑖 (𝑥) = 0 , 𝑖 = 1,2, … , 𝑚 (v) 𝑥 𝑗 ≥ 0 , 𝑗 = 1,2, … , 𝑛 (vi) 𝑣 𝑖 ≥ 0 , 𝑖 = 1,2, … , 𝑚

## Kondisi Optimal Quadratic Programming
Fungsi Lagrange untuk masalah quadratic programming (2.1) adalah sebagai berikut:
𝐿(𝑥, 𝑣) = 𝑐𝑥 + 1 2 𝑥 𝑇 Σ𝑥 + 𝑣 𝑇 (𝑏 − 𝐴𝑥)
Dimana 𝑣 adalah  pengali  Lagrange.  Kondisi KKT quadratic  programming untuk  minimum lokal memenuhi:
𝜕𝐿 𝜕𝑥 𝑗 ≥ 0, 𝑗 = 1, … , 𝑛 maka 𝑐 + 𝑥 𝑇 Σ − 𝑣𝐴 ≥ 0 (2.7) 𝜕𝐿 𝜕𝑣 𝑗 ≤ 0 , maka 𝑏 − 𝐴𝑥 ≤ 0
𝑥 𝑗 𝜕𝑓 𝜕𝑥 𝑖 = 0, 𝑗 = 1, … , 𝑛 maka 𝑥 𝑇 (𝑐 𝑇 + Σ𝑥 − 𝐴 𝑇 𝑣) = 0 𝑣 𝑖 𝑔 𝑖 (𝑥) = 0, 𝑖 = 1, … , 𝑛 maka 𝑣(𝑏 − 𝐴𝑥) = 0 𝑥 𝑗 ≥ 0, 𝑗 = 1, …, 𝑥 ≥ 0 𝑣 𝑖 ≥ 0, 𝑖 = 1, … , 𝑚 , 𝑣 ≥ 0 Persamaan  (2.7)  ditambahkan  variabel 𝑞 dan 𝑠 untuk  mencari  penyelesaia  optimal, sehingga diperoleh:
𝑐 𝑇 + Σ𝑥 − 𝐴 𝑇 𝑣 𝑇 − 𝑞 = 0 dan 𝐴𝑥 − 𝑏 + 𝑠 = 0 Dengan demikian, kondisi KKT menjadi:
−Σ𝑥 + 𝐴 𝑇 𝑣 𝑇 + 𝑞 = 𝑐 𝑇
𝐴𝑥 − 𝑏 = 0 𝑞 𝑇 𝑥 = 0, 𝑣𝑠 = 0 , 𝑥 ≥ 0, 𝑣 ≥ 0, 𝑞 ≥ 0, 𝑠 ≥ 0

## Fungsi Barrier
Fungsi barrier berguna untuk menemukan solusi  masalah  optimasi  nonlinear  berkendala dengan  mengubahnya  menjadi  barisan  masalah tanpa  kendala  parameter.  Bentuk  umum  fungsi barrier adalah sebagai berikut:
𝐹(𝑥, 𝛾) = 𝑓(𝑥) + 𝛾 ∑ 𝑞 𝑗 (𝑥) 𝑗 (2.8)
dimana  f(x)  adalah  fungsi  tujuan, 𝛾 adalah pengali barrier positif dan 𝑞 𝑗 (𝑥) → +∞ sebagai j kendala yang mendekati nol.
Jika  meminimalkan  fungsi  f(x)  dengan kendala 𝑥 ≥ 0 ,  maka  fungsi barrier yang dipakai untuk memberikan batas besar dari atau sama  dengan  nol  terhadap  suatu  fungsi  adalah fungsi barrier logaritma sebagai berikut: 𝜔(𝑥, 𝛾) = 𝑓(𝑥) − 𝛾 log 𝑥 (2.9) Nilai 𝛾 relatif  besar  mengakibatkan  pencarian titik  optimal  berada  jauh  dari  batas feasible region .  Sebaliknya,  nilai 𝛾 relatif  kecil mengakibatkan pencarian titik optimal dilakukan di dekat batas feasible region . Fungsi  logaritmik barrier sesuai  dengan fungsi  Lagrange  untuk  masalah  (2.5)  adalah sebagai berikut:
𝐿(𝑥, 𝑣, 𝛾) = 1 2 𝑥 𝑇 Σ𝑥 + 𝑐 𝑇 𝑥 − 𝛾 ∑ 𝑙𝑜𝑔𝑥 + 𝑣(𝑏 − 𝐴𝑥) .                     (2.10)
Masalah  (2.5)  menggunakan  fungsi barrier logaritmik dalam  hal  ini −𝛾 ∑ 𝑙𝑜𝑔𝑥 karena adanya  kendala 𝑥 ≥ 0 .  Fungsi barrier yang terbentuk  harus  sesuai  dengan  kendala  agar dapat diperoleh feasible region yang baik.

## Metode Newton
Algoritma metode Newton untuk meminimumkan 𝑓(𝑥) tanpa kendala dengan 𝑥 ∈ ℜ 𝑛 , sebagai berikut:
a) Menentukan titik awal 𝑥 0 , saat 𝑘 ← 0 .
b) Menentukan Newton direction 𝑑 𝑘 = −Σ(𝑥 𝑘 ) −1 ∇𝑓(𝑥 𝑘 ). Jika 𝑑 𝑘 = 0 ,  maka perhitungan berhenti.
c) Memilih step size 𝛼 𝑘 = 1 .
d) Mentukan 𝑥 𝑘+1 ← 𝑥 𝑘 + 𝛼 𝑘 𝑑 𝑘 , saat 𝑘 ← 𝑘 + 1 , kemudian kembali ke langkah b.
Metode  Newton  dapat  dikembangkan dalam  proses  peminimalan  fungsi  berkendala khususnya dalam penyelesaian quadratic programming dengan  metode  titik  interior. Dalam quadratic programming , Newton direction merupakan  vektor  yang  mengarahkan ke nilai optimal fungsi tujuan.

## 3. HASIL DAN PEMBAHASAN
Penyelesaian Masalah Quadratic
Programming  dengan  Metode  Primal  Dual
Interior Point
Fungsi  Lagrange  untuk  masalah  (2.5) dapat dituliskan sebagai berikut:
𝐿(𝑥, 𝑣, 𝛾) = 1 2 𝑥 𝑇 Σ𝑥 + 𝑐 𝑇 𝑥 + 𝑣 𝑇 (𝑏 − 𝐴𝑥) − 𝛾 ∑ 𝑙𝑜𝑔 (𝑥 𝑖 ) 𝑖
dimana 𝜐 adalah pengali Lagrange dan 𝛾 adalah pengali dari barrier term .
Selanjutnya  fungsi  L  diturunkan  secara parsial  terhadap 𝑥 dan 𝑣 ,  secara  berturut-turut diperoleh  kondisi dual  feasibility dan primal feasibily .
Σ𝑥 + 𝑐 − 𝐴 𝑇 𝑣 − 𝛾𝑋 −1 𝑏 − 𝐴𝑥 = 0 .                                   (3.1) 𝑋 merupakan matriks diagonal 𝑥 𝑖 , 𝑖 = 1,2, … , 𝑛. pada  persamaan  (3.2).  Pembentukan slackness condition dapat dilakukan sebagai berikut: 𝑢 = 𝛾𝑋 −1
𝑋𝑢 = 𝛾𝑒 (3.2) dimana X  adalah  matriks diagonal 𝑥 𝑖 , U adalah matriks  diagonal 𝑢 𝑖 ,  dan  e  adalah  matriks  yang semua entrinya bernilai 1.
Persamaan non-linear pada masalah quadratic  programming menyebabkan  tidak adanya  teknik  penyelesaian  secara  langsung, kecuali  metode trial  and  error serta  iterasi menggunakan  metode  Newton.Vektor 𝑥, 𝑢, 𝑣 merupakan  nilai  awal  yang  pada  iterasi selanjutnya  akan  menjadi 𝑥 + 𝑑 𝑥 , 𝑢 + 𝑑 𝑢 , 𝑣 + 𝑑 𝑣 , dimana nilai 𝑑 𝑥 , 𝑑 𝑢 , 𝑑 𝑣 , perlu ditentukan. −Σ(𝑥 + 𝑑 𝑥 ) + 𝐴 𝑇 (𝑣 + 𝑑 𝑣 ) + (𝑢 + 𝑑 𝑢 ) = 𝑐 𝐴(𝑥 + 𝑑 𝑥 ) − 𝑏 = 0 (3.3) −𝑋𝑈𝑒 − 𝑈𝑑 𝑥 𝑒 − 𝑋𝑑 𝑢 𝑒 − 𝑑 𝑥 𝑑 𝑢 𝑒 = −𝛾𝑒. 𝑑 𝑥 𝑑 𝑢 𝑒 pada  sistem  (3.3)  memiliki  nilai  yang kecil, sehingga dapat diabaikan untuk melinearkan sistem (3.3) dengan (3.2) dan (3.1).
𝐴𝑑 𝑥 = −𝐴𝑥 + 𝑏 −Σ𝑑 𝑥 + 𝑑 𝑢 + 𝐴 𝑇 𝑑 𝑣 = Σ𝑥 + 𝑐 − 𝐴 𝑇 𝑣 − 𝑢 (3.4) 𝑈𝑑 𝑥 + 𝑋𝑑 𝑢 = −𝑋𝑈𝑒 + 𝛾𝑒 . Berdasarkan  (2.6),  nilai 𝑥, 𝑢, dan 𝑣 yang baru  dapat  diperoleh  dengan  menyelesaikan persamaan berikut:
( 𝐴 0 0 −Σ 𝐼 𝐴 𝑇 𝑈 𝑋 0 ) ( 𝑑 𝑥 𝑑 𝑢 𝑑 𝑣 ) = − ( 𝐴𝑥 𝑘 − 𝑏 −Σx + A T v k + u k − c 𝑋𝑈𝑒 − 𝛾 𝑘 𝑒 ) (3.5)
Matriks  U  dan  X  terdefinisi  sebagai  titik  yang diketahui  pada  iterasi  k.  Perhitungan  nilai 𝑑 𝑥 , 𝑑 𝑢 , 𝑑 𝑣 pada persamaan (3.5) dapat dilakukan sebagai berikut:
𝐴𝑑 𝑥 = −𝐴𝑥 𝑘 + 𝑏 ≡ 𝑟 𝑝 (3.6) −Σ𝑑 𝑥 + 𝑑 𝑢 + 𝐴 𝑇 𝑑 𝑣 = Σx − A T v k − u k + c ≡ 𝑟 𝑑 (3.7 ) 𝑈𝑑 𝑥 + 𝑋𝑑 𝑢 = 𝑋𝑈𝑒 − 𝜇 𝑘 𝑒 ≡ 𝑟 𝑐 . (3.8)
Dengan  mengalikan  persamaan  (3.7)  dengan  X dan  kemudian  disubstitusi  untuk 𝑋𝑑 𝑢 di persamaan (3.8) diperoleh:
−𝑑 𝑥 + [𝑋Σ + U] −1 𝑋𝐴 𝑇 𝑑 𝑣 = [𝑋Σ + U] −1 (X𝑟 𝑑 − 𝑟 𝑐 ) (3.9)
Kalikan  dengan  matriks  A,  gunakan  persamaan (3.9), diperoleh sistem persamaan berikut untuk menyelesaikan 𝑑 𝑣 :
𝐴[𝑋Σ + U] −1 𝑋𝐴 𝑇 𝑑 𝑣 = 𝑟 𝑝 + 𝐴[𝑋Σ + U] −1 (X𝑟 𝑑 − 𝑟 𝑐 ) 𝑑 𝑥 dapat dihitung dari (3.9) dan 𝑑 𝑢 dari (3.10).
Optimasi Masalah Convex Quadratic Programming dengan Metode Primal Dual Interior Point • 56
𝑑 𝑥 = [𝑋Σ + U] −1 (𝑋𝐴 𝑇 𝑑 𝑣 − X𝑟 𝑑 + 𝑟 𝑐 ) dan
𝑑 𝑢 = 𝑋 −1 (𝑟 𝑐 − 𝑈𝑑 𝑥 ) .
Diasumsikan  nilai 𝑥, 𝑢, 𝑣 yang  baru dimulai  dari  nilai  awal  positif.  Parameter 𝛼 menyatakan step  length .  Nilai  maksimum  dari step  length merupakan  nilai  yang  membuat 𝑥 𝑖 atau 𝛾 𝑖 menuju nol. 𝑥 𝑖 + 𝛼 𝑝 𝑑 𝑥𝑖 ≥ 0 𝑑𝑎𝑛 𝑢 𝑘+1 = 𝛾 𝑖 + 𝛼 𝑑 𝑑 𝑢𝑖 ≥ 0, 𝑖 = 1, … , 𝑛
Untuk  menjaga feasibility, step  length bernilai lebih kecil dari nilai maksimum dan dirumuskan sebagai berikut:
𝛼 𝑝 = 𝛽 𝑀𝑖𝑛 [1, − 𝑥 𝑖 𝑑 𝑥𝑖 , 𝑑 𝑥𝑖 < 0] 𝛼 𝑑 = 𝛽 𝑀𝑖𝑛 [1, − 𝑢 𝑖 𝑑 𝑢𝑖 , 𝑑 𝑢𝑖 < 0]
𝛽 adalah  skalar  atau  pengali  yang  bertujuan untuk  menentukan  banyaknya  nilai  yang ditambahkan  dari  arah  sebelumnya  pada  proses penentuan  nilai  yang  baru.  Nilai  parameter 𝛽 berada diantara 0 dan 1. Nilai 𝛽 = 0.999 sering digunakan.  Nilai  yang  baru  dari 𝑥, 𝑢, 𝑑𝑎𝑛 𝑣 adalah sebagai berikut:
𝑥 𝑘+1 = 𝑥 𝑘 + 𝛼 𝑝 𝑑 𝑥 𝑢 𝑘+1 = 𝜇 𝑘 + 𝛼 𝑑 𝑑 𝑢 𝑣 𝑘+1 = 𝑣 𝑘 + 𝛼 𝑑 𝑑 𝑣 .
Ada tiga syarat untuk mengetahui keoptimalan solusi, yakni memenuhi konvergensi feasibility , konvergensi dual feasibility ,  dan complementary slackmess . Apabila  sudah  memenuhi  ketiga  hal  tersebut maka iterasi menggunakan metode Newton boleh dihentikan.
Fungsi kendala 𝐴𝑥 𝑘 − 𝑏 = 0 harus terpenuhi oleh solusi optimal. Dengan demikian, kriteria konvergensi untuk feasibility dinyatakan sebagai berikut:
𝜎 𝑝 = ‖𝐴𝑥 𝑘 − 𝑏‖ ‖𝑏‖ + 1 ≤ 𝜖 1
dimana 𝜖 1 merupakan  bilangan  positif  yang sangat  kecil  dan  1  ditambahkan  pada  penyebut untuk  menghindari  pembagian  dengan  bilangan yang bernilai kecil.
Selain  itu  dipunyai  juga dual  feasibility −Σ𝑥 + 𝑢 𝑘 + 𝐴 𝑇 𝑣 𝑘 = 𝑐 .  Kriteria  konvergensi untuk dual feasibility dinyatakan sebagai berikut:
𝜎 𝑑 = ‖𝑟 𝑑 ‖ ‖Σ𝑥 + 𝑐‖ + 1 ≤ 𝜖 2
dimana 𝜖 2 merupakan  bilangan  positif  yang sangat kecil.
Nilai  parameter 𝜇 menentukan  seberapa baik slackness  condition terpenuhi.  Eksperimen numerik  mendefinisikan  sebuah  nilai  rata-rata dari 𝜇 sebagai berikut:
𝛾 𝑘 = (𝑥 𝑘 ) 𝑇 𝑢 𝑛 dimana  n  adalah  banyaknya  variabel  optimasi. Parameter  ini  harus  bernilai  nol  ketika  kondisi optimum  sudah  tepenuhi.  Sehingga,  kriteria konvergensi untuk slackness condition adalah: 𝛾 ≤ 𝜖 3 dimana 𝜖 3 merupakan  bilangan  positif  yang sangat kecil.

## Algoritma  Penyelesaian  Masalah  Quadratic Programming  dengan  Metode  Primal  Dual Interior Point
Diberikan  matriks  koefisien  kendala  A, matriks Hessian Σ , vektor kendala ruas kanan b, vektor pengali Lagrange v, parameter perubahan titik 𝛽 , dan parameter toleransi kekonvergenan. Tahap-tahap  penentuan  nilai  optimal adalah sebagai berikut:
a) Menentukan  nilai  awal  saat  k=0,  dimana  k menunjukkan  iterasi  yang  dilakukan.  Nilai awal  yang  diambil  harus  lebih  besar  atau sama  dengan  0.  Nilai  awal  yang  diambil adalah:
𝑥 0 = ( 1 1 1 ⋯ 1 ) , 𝑢 0 = ( 1 1 1 ⋯ 1 ) , 𝑣 0 = ( 0 0 0 ⋯ 0 ) . b) Dilakukan perhitungan sebagai berikut:
𝑟 𝑝 = −𝐴𝑥 𝑘 + 𝑏 𝑟 𝑑 = Σ ∗ 𝑥 𝑘 − 𝐴 𝑇 𝑣 𝑘 − 𝑢 𝑘 + 𝑐 𝑟 𝑐 = −𝑋𝑈𝑒 + 𝑢 𝑘 e.
Dimana
𝛾 𝑘 = [ (𝑥 𝑘 ) 𝑇 𝑢 𝑛 ] /(𝑘 + 1) . c) Setelah  vektor 𝑟 𝑝 , 𝑟 𝑑 ,  dan 𝑟 𝑐 ditentukan, dilakukan  pengecekan  konvergensi  untuk melihat apakah nilai yang diambil sebelumnya  sudah  optimal  atau  belum. Kekonvergenan dipenuhi apabila:
[ ‖𝐴𝑥 𝑘 − 𝑏‖ ‖𝑏‖ + 1 ≤ 𝜖 1 , ‖𝑟 𝑑 ‖ ‖Σ ∗ 𝑥 + 𝑐‖ + 1 ≤ 𝜖 2 , 𝛾 ≤ 𝜖 3 ] dimana 𝜖 1 , 𝜖 2 , 𝜖 3 merupakan  bilangan  yang bernilai kecil.
Jika  hasil  perhitungan  sudah  memenuhi syarat  di  atas,  maka  tidak  usah  dilakukan iterasi  selanjutnya  karena  sudah  ditemukan solusi optimal. Tetapi jika hasil perhitungan tidak  memenuhi  syarat  di  atas,  maka  harus dilakukan iterasi lagi.
d) Jika belum ditemukan solusi optimal, maka dilakukan perhitungan untuk mencari
Newton direction 𝑑 𝑥 , 𝑑 𝑣 , 𝑑 𝑢 . 𝑑 𝑣 = [[𝑋Σ ∗ + U] −1 𝑋𝐴 𝑇 ] −1 [𝑟 𝑝 + 𝐴[𝑋Σ ∗ + U] −1 (X𝑟 𝑑 − 𝑟 𝑐 )] 𝑑 𝑥 = [𝑋Σ ∗ + U] −1 (𝑋𝐴 𝑇 𝑑 𝑣 − X𝑟 𝑑 + 𝑟 𝑐 ) 𝑑 𝑢 = 𝑋 −1 (𝑟 𝑐 − 𝑈𝑑 𝑥 ) .
e) Penentuan step length dari nilai semula
𝛼 𝑝 = 𝛽 𝑀𝑖𝑛 [1, − 𝑥 𝑖 𝑑 𝑥𝑖 , 𝑑 𝑥𝑖 < 0] 𝛼 𝑑 = 𝛽 𝑀𝑖𝑛 [1, − 𝑢 𝑖 𝑑 𝑢𝑖 , 𝑑 𝑢𝑖 < 0] . f) Penentuan nilai 𝑥 𝑘+1 , 𝑢 𝑘+1 , 𝑣 𝑘+1 yang baru: 𝑥 𝑘+1 = 𝑥 𝑘 + 𝛼 𝑝 𝑑 𝑥 𝑢 𝑘+1 = 𝜇 𝑘 + 𝛼 𝑑 𝑑 𝑢 𝑣 𝑘+1 = 𝑣 𝑘 + 𝛼 𝑑 𝑑 𝑣 . g) Langkah  (b)  dan  (c)  dilakukan  kembali untuk mengecek konvergensi dari nilai yang baru.  Jika  syarat  konvergensi  terpenuhi, maka  solusi  optimal  telah  ditemukan. Apabila belum memenuhi syarat konvergensi,  maka langkah (d),  (e), dan  (f) dilakukan  kembali  sampai  menemukan solusi optimal.
Contoh Soal [4] Tentukan
solusi masalah quadratic
programming berikut  menggunakan  metode primal-dual titik interior.
min 𝑓 = −2𝑥 1 + 𝑥 1 2 2 − 6𝑥 2 − 𝑥 1 𝑥 2 + 𝑥 2 2 𝑠. 𝑡. ( 3𝑥 1 + 𝑥 2 ≤ 25 −𝑥 1 + 2𝑥 2 ≤ 10 𝑥 1 + 2𝑥 2 ≤ 15 𝑥 𝑖 ≥ 0, 𝑖 = 1,2 )
Penyelesaian:
Langkah  pertama  adalah  membawa  sistem  di atas  ke  bentuk  standar quadratic  programming sebagai berikut:
(𝑄𝑃) { 𝑚𝑖𝑛 𝑥 1 2 𝑥 𝑇 Σ𝑥 +   𝑐 𝑇 𝑥
𝑠. 𝑡.
𝐴𝑥 = 𝑏 𝑥 ≥ 0
Untuk memudahkan pembentukan matriks A, b, c dan Σ , maka masalah quadratic programming dapat dituliskan sebagai berikut:
min 𝑓 = −2𝑥 1 + 𝑥 1 2 2 − 6𝑥 2 − 𝑥 1 𝑥 2 + 𝑥 2 2 𝑠. 𝑡. ( 3𝑥 1 + 𝑥 2 + 𝑥 3 = 25 −𝑥 1 + 2𝑥 2 + 𝑥 4 = 10 𝑥 1 + 2𝑥 2 + 𝑥 5 = 15 𝑥 𝑖 ≥ 0, 𝑖 = 1, … ,5 )
Dilakukan  penambahan  variabel  slack 𝑥 3 , 𝑥 4, 𝑥 5 untuk mengubah tanda ( ≤) menjadi (=).
Matriks koefisien kendala A, vektor kendala ruas kanan b, vektor koefisien suku-suku linear c, dan matriks  hessian Σ dapat  dituliskan  sebagai berikut:
𝐴 = ( 3 1 1 0 0 −1 2 0 1 0 1 2 0 0 1 ) , 𝑏 = ( 25 10 15 ) 𝑐 = ( −2 −6 0 0 0 ) , Σ = ( 1 −1 0 0 0 −1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
Nilai  awal  untuk  variabel 𝑥, 𝑢, 𝑑𝑎𝑛 𝑣 dapat dituliskan dalam bentuk vektor sebagai berikut:
𝑣𝑎𝑟𝑖𝑎𝑏𝑒𝑙 𝑝𝑟𝑖𝑚𝑎𝑙(𝑥) =
( 1 1 1 1 1) ,
𝑣𝑎𝑟𝑖𝑎𝑏𝑒𝑙 𝑑𝑢𝑎𝑙 (𝑢) =
( 1 1 1 1 1) 𝑝𝑒𝑛𝑔𝑎𝑙𝑖 (𝑣) = ( 0 0 0 ) Jika nilai 𝑥 1 = 1, 𝑥 2 = 1, maka 𝑓 = −7,5 . Diambil ∈= 0,00001 ,  dari  hasil  pengecekan konvergensi  diperoleh 𝜎 𝑝 = 0,760063 , 𝜎 𝑑 = 1,08505, 𝜇 = 1 .  Nilai 𝜎 𝑝 >∈ 𝜎 𝑑 >∈, 𝜇 > ∈
Optimasi Masalah Convex Quadratic Programming dengan Metode Primal Dual Interior Point • 58
sehingga  belum  diperoleh  solusi  optimal. Dengan demikian, masih perlu dilakukan iterasi menggunakan metode Newton. Pertama-tama, ditentukan 𝑟 𝑝 , 𝑟 𝑑 , 𝑟 𝑐 . 𝑟 𝑝 = ( 20 8 11 ) , 𝑟 𝑑 = ( −3 −6 −1 −1 −1) , 𝑟 𝑑 = ( 0 0 0 0 0) .
Diketahui  diagonal  X  dan  U  adalah  sebagai berikut:
𝑑𝑖𝑎𝑔𝑜𝑛𝑎𝑙 𝑋 =
( 1 0 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1) ,
𝑑𝑖𝑎𝑔𝑜𝑛𝑎𝑙 𝑈 =
( 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1)
Untuk memperoleh newton direction 𝑑 𝑣 , 𝑑 𝑥 , 𝑑 𝑢 atau  vektor  yang  petunjuk  menuju nilai  minimal  fungsi  tujuan,  maka  dilakukan perhitungan sebagai berikut:
XΣ + U =
( 2 −1 0 0 0 −1 3 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1) , (XΣ + U) −1 =
( 0,6 0,2 0 0 0 0,2 0,4 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1) (XΣ + U) −1 XA T
= ( 8 2,22045 × 10 −16 4 2,22045 × 10 −16 2,4 1 4 1 4 ) 𝑟 𝑝 + 𝐴(XΣ + U) −1 (X𝑟 𝑑 − 𝑟 𝑐 ) = ( 7 4 1 ) Jadi,
𝑑 𝑣 =   ( 2,19079
2,76136
−2,63158 ) 𝑑 𝑥 = ( 4,19737 4,21711 3,19079
3,76316 −1,63158) , 𝑑 𝑢 = ( −4,19737 −4,21711
−3,19079 −3,76316
1,63158 )
Setelah Newton  direction ditentukan,  maka dicari  step  length  atau  jarak  antara  nilai  awal dengan  nilai  yang  baru.  Diperoleh  nilai step length 𝛼 𝑝 = 0,606774 dan 𝛼 𝑑 = 0,234758 . Diperoleh  nilai 𝑥, 𝑢, 𝑣 yang  baru  atau 𝑥′, 𝑢′, 𝑑𝑎𝑛 𝑣′ sebagai berikut: 𝑥 ′ = (3,54 3,55 2,93 3.28 0,01) 𝑢′ = (0,014 0,01 0,250 0,116 1,383) 𝑣′ = (0,514 0,648 −0,617)
𝑓 = −22.114 𝑥 1 = 3,54685 𝑑𝑎𝑛 𝑥 2 = 3,55883 . Setelah dilakukan  pengecekan  kriteria  konvergensi, ternyata nilai 𝑥 1 𝑑𝑎𝑛 𝑥 2 belum optimal sehingga dilakukan  lagi  iterasi  sampai  tujuh  kali  untuk memperoleh  nilai  optimal.  Berdasarkan  hasil iterasi  ke-7  diperoleh 𝑥 1 = 5,59981, 𝑥 2 = 4,69992, 𝑓 = −27,9496 .  Setelah  dilakukan pengecekan  konvergensi,  dapat  disimpulkan bahwa nilai optimal ditemukan pada iterasi ke-7.

## 4. KESIMPULAN
Berdasarkan  pembahasan  dari  penelitian yang  telah  dilakukan,  diperoleh  kesimpulan bahwa penyelesaian masalah quadratic programming menggunakan metode primal dual titik  interior  dapat  dilakukan  untuk  kasus  yang lebih besar dari 2 variabel.

## 5. DAFTAR PUSTAKA
[1] Azis, A., Prihandono, B., & Ilhamsyah. (2016). Algoritma  Genetika  pada  Pemrograman  Linear dan  Non-Linear. Buletin  Ilmiah  Matematika, Statistika,  Dan  Terapannya  (Bimaster) , 5 (3),
265–274. [2] Hariadi, V. (2009). Pencarian Solusi Pemrograman Non-Linear Menggunakan Algoritma Branch-and-Bound. Section (SNATI) 2009:  Bidang  Informatika  Teori .  Seminar
Nasional Aplikasi Teknologi Informasi
(SNATI), Yogyakarta.
[3] Irawan,  R.,  Eridani,  &  Jaelani,  A.  (2020). Ketaksamaan Hadamard pada Fungsi Konveks. Contemporary
of Mathematics and
Applications , 2 (1), 1–12.
[4] M Asghar Bhatti. (2000). Practical optimization methods: with  Mathematica applications . Springer.
[5] Rianingsih, W., Hasan, M., & Pradjaningsih, A.
(2017). Optimasi Portofolio dengan Menggunakan Pemprograman Kuadratik. Majalah Ilmiah Matematika Dan Statistika , 7 (2), 67–78.