Optimisasi Statistika - Quadratic Programming

Video Pembelajaran - P9

Video Pembelajaran dapat diakses melalui link berikut : https://ipb.link/materiopstat

Quadratic Programming (QP)

Definisi: Quadratic Programming (QP) adalah salah satu metode optimasi matematis yang digunakan untuk meminimalkan atau memaksimalkan fungsi objektif kuadratik dengan kendala linear. Bentuk umum dari QP adalah:

\[ \text{Minimalkan } f(b) = -d^T b + \frac{1}{2} b^T D b \]

dengan:
- \(b\): Vektor keputusan (\(b \in \mathbb{R}^n\))
- \(D\): Matriks simetris positif-semi definit (\(D \in \mathbb{R}^{n \times n}\)), yang menentukan bentuk kuadratik fungsi
- \(d\): Vektor koefisien linier (\(d \in \mathbb{R}^n\))
- \(\frac{1}{2} b^T D b\): Komponen kuadratik
- \(-d^T b\): Komponen linier

Fungsi ini sering disertai dengan kendala linear yang berbentuk:
\[ A^T b \geq b_0 \] dimana:
- \(A\): Matriks kendala (\(A \in \mathbb{R}^{n \times m}\))
- \(b_0\): Vektor batas kendala (\(b_0 \in \mathbb{R}^m\))

Langkah-Langkah Solusi QP

1. Formulasi Masalah

Langkah pertama adalah menuliskan fungsi kuadratik dalam bentuk matriks \(D\) dan \(d\), serta menyusun kendala \(A^T b \geq b_0\) jika ada.

2. Menyusun Matriks

  • Matriks \(D\): Diperoleh dari koefisien kuadrat dalam fungsi objektif. Harus berbentuk simetris positif-semi definit.
  • Vektor \(d\): Koefisien linier dalam fungsi objektif.
  • Matriks \(A\): Merepresentasikan kendala. Setiap baris menyatakan satu kendala.
  • Vektor \(b_0\): Batas bawah dari kendala.

3. Menyelesaikan dengan Fungsi solve.QP (R)

Fungsi solve.QP dari library quadprog digunakan untuk menyelesaikan masalah QP.

Kasus Tanpa Kendala

Misalkan fungsi objektif:
\[ f(x_1, x_2) = -8x_1 - 16x_2 + x_1^2 + 4x_2^2 \]

Langkah-Langkah:

  1. Identifikasi komponen kuadrat (\(D\)) dan linier (\(d\)):
    \[ D = \begin{bmatrix} 2 & 0 \\ 0 & 8 \end{bmatrix}, \quad d = \begin{bmatrix} 8 \\ 16 \end{bmatrix} \]

  2. Tidak ada kendala, sehingga:
    \[ A = \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}, \quad b_0 = \begin{bmatrix} 0 \\ 0 \end{bmatrix} \]

  3. Gunakan solve.QP:

library(quadprog)
D <- matrix(c(2, 0, 0, 8), 2, 2, byrow = TRUE)
d <- c(8, 16)
A <- matrix(0, 2, 2)
b0 <- c(0, 0)

solve.QP(D, d, A, b0)
## $solution
## [1] 4 2
## 
## $value
## [1] -32
## 
## $unconstrained.solution
## [1] 4 2
## 
## $iterations
## [1] 1 0
## 
## $Lagrangian
## [1] 0 0
## 
## $iact
## [1] 0

Hasil:

  • Solusi: \(b = \begin{bmatrix} 4 \\ 2 \end{bmatrix}\)
  • Nilai fungsi minimum: \(f(b) = -32\)

Interpretasi:
Nilai \(b = [4, 2]\) adalah solusi optimal tanpa kendala, yaitu titik dimana fungsi objektif mencapai nilai minimum.

Kasus Dengan Kendala (\(\geq\))

Fungsi objektif tetap sama, tetapi sekarang dengan kendala:
\[ x_1 + x_2 \geq 5, \quad x_1 \geq 4.5 \]

Langkah-Langkah:

  1. Formulasi kendala:

    • Kendala pertama (\(x_1 + x_2 \geq 5\)): \(A_1 = [1, 1], \, b_0 = 5\)
    • Kendala kedua (\(x_1 \geq 4.5\)): \(A_2 = [1, 0], \, b_0 = 4.5\)

  2. Matriks kendala:
    \[ A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}, \quad b_0 = \begin{bmatrix} 5 \\ 4.5 \end{bmatrix} \]

  3. Gunakan solve.QP:

A <- matrix(c(1, 1, 1, 0), 2, 2, byrow = TRUE)
b0 <- c(5, 4.5)

solve.QP(D, d, A, b0)
## $solution
## [1] 4.5 2.0
## 
## $value
## [1] -31.75
## 
## $unconstrained.solution
## [1] 4 2
## 
## $iterations
## [1] 2 0
## 
## $Lagrangian
## [1] 0 1
## 
## $iact
## [1] 2

Hasil:

  • Solusi: \(b = \begin{bmatrix} 4.5 \\ 2 \end{bmatrix}\)
  • Nilai fungsi: \(f(b) = -31.75\)

Interpretasi:
Solusi optimal tetap memenuhi kendala \(x_1 + x_2 \geq 5\) dan \(x_1 \geq 4.5\), sambil meminimalkan fungsi objektif.

Kasus Dengan Kendala (\(\leq\))

Fungsi objektif dengan kendala:
\[ x_1 + x_2 \leq 5, \quad x_1 \leq 3 \]

Langkah-Langkah:

  1. Ubah kendala menjadi bentuk \(-A \geq -b_0\):
    \[ -x_1 - x_2 \geq -5, \quad -x_1 \geq -3 \]

  2. Matriks kendala:
    \[ A = \begin{bmatrix} -1 & -1 \\ -1 & 0 \end{bmatrix}, \quad b_0 = \begin{bmatrix} -5 \\ -3 \end{bmatrix} \]

  3. Gunakan solve.QP:

A <- matrix(c(-1, -1, -1, 0), 2, 2, byrow = TRUE)
b0 <- c(-5, -3)

solve.QP(D, d, A, b0)
## $solution
## [1] 3 2
## 
## $value
## [1] -31
## 
## $unconstrained.solution
## [1] 4 2
## 
## $iterations
## [1] 2 0
## 
## $Lagrangian
## [1] 0 2
## 
## $iact
## [1] 2

Hasil:

  • Solusi: \(b = \begin{bmatrix} 3 \\ 2 \end{bmatrix}\)
  • Nilai fungsi: \(f(b) = -31\)

Interpretasi:
Solusi optimal berada di dalam batas kendala yang diberikan, yaitu \(x_1 + x_2 \leq 5\) dan \(x_1 \leq 3\).

OLS (Ordinary Least Squares)

Fungsi Objektif:
Tujuan OLS adalah meminimalkan Residual Sum of Squares (RSS):
\[ \text{RSS} = \epsilon^T \epsilon = (y - X\beta)^T(y - X\beta) \]

Dapat dituliskan dalam bentuk QP:
\[ f(\beta) = -2y^T X\beta + \beta^T X^T X\beta \]

Maka:
\[ D = 2(X^T X), \quad d = 2X^T y \]

Kode R:

y <- as.matrix(mtcars$mpg)
X <- as.matrix(cbind(1, mtcars[, 2:7]))

D <- 2 * t(X) %*% X
d <- 2 * t(y) %*% X
solve.QP(D, d, A = diag(0, ncol(X)), b = rep(0, ncol(X)))
## $solution
## [1] 26.30735899 -0.81856023  0.01320490 -0.01792993  1.32040573 -4.19083238
## [7]  0.40146117
## 
## $value
## [1] -13878.83
## 
## $unconstrained.solution
## [1] 26.30735899 -0.81856023  0.01320490 -0.01792993  1.32040573 -4.19083238
## [7]  0.40146117
## 
## $iterations
## [1] 1 0
## 
## $Lagrangian
## [1] 0 0 0 0 0 0 0
## 
## $iact
## [1] 0

Hasil: Sama seperti menggunakan lm().

LASSO (Least Absolute Shrinkage and Selection Operator)

Definisi:
LASSO adalah teknik regresi yang memperkenalkan regularisasi \(L_1\) untuk menyusutkan beberapa koefisien regresi ke nol. Hal ini sangat berguna untuk seleksi variabel (feature selection) dalam model dengan banyak variabel prediktor.

Fungsi optimasi LASSO adalah:
\[ \text{Minimalkan } \text{RSS} + \lambda \sum_{j=1}^p |\beta_j| \] dengan:
- \(\text{RSS} = \sum_{i=1}^n (y_i - \hat{y}_i)^2\): Residual Sum of Squares.
- \(\lambda\): Parameter regularisasi yang mengontrol tingkat penyusutan.
- \(\sum_{j=1}^p |\beta_j|\): Penalti \(L_1\).

Parameter \(\lambda\) menentukan keseimbangan antara akurasi model (fit) dan sederhana model (sparsity).
- Jika \(\lambda = 0\): Model sama dengan OLS (tidak ada penalti).
- Jika \(\lambda\) besar: Banyak koefisien \(\beta_j\) menjadi nol, menghasilkan model yang lebih sederhana.

Formulasi LASSO dalam QP

Regresi LASSO dapat diformulasikan sebagai masalah Quadratic Programming (QP) dengan kendala:
\[ \sum_{j=1}^p |\beta_j| \leq s \] dimana \(s\) adalah batas kendala yang menggantikan parameter \(\lambda\).

Jika terdapat \(p\) variabel prediktor, maka akan ada \(2^p\) kendala, yang dihasilkan dari kombinasi tanda \(\pm\) pada koefisien \(\beta_j\).

Sebagai contoh:
- Untuk \(p = 2\):
\[ |\beta_1| + |\beta_2| \leq s \quad \Rightarrow \quad \begin{cases} \beta_1 + \beta_2 \leq s \\ -\beta_1 + \beta_2 \leq s \\ \beta_1 - \beta_2 \leq s \\ -\beta_1 - \beta_2 \leq s \end{cases} \]

  • Matriks \(A\) dan \(b_0\) direpresentasikan sebagai:
    \[ A = \begin{bmatrix} -1 & -1 \\ 1 & -1 \\ -1 & 1 \\ 1 & 1 \end{bmatrix}, \quad b_0 = \begin{bmatrix} -s \\ -s \\ -s \\ -s \end{bmatrix} \]

Contoh Penerapan LASSO dalam Dataset mtcars

Langkah-Langkah:

  1. Formulasi Masalah:
    Gunakan dataset mtcars dengan 6 variabel prediktor (\(x_1, x_2, \ldots, x_6\)) untuk memprediksi \(y = \text{mpg}\). Dalam kasus ini:
    • \(p = 6\), sehingga ada \(2^6 = 64\) kendala.
y<-as.matrix(mtcars$mpg)
x<-as.matrix(mtcars[,2:7])
  1. Menyusun Matriks Kendala:
    Matriks \(A\) dibangun dari semua kombinasi tanda (\(-1\) dan \(1\)) pada setiap \(\beta_j\).
ols.tb<-lm(y~x-1)

A<-as.matrix(expand.grid(rep(list(c(-1,1)),6)));A
##       Var1 Var2 Var3 Var4 Var5 Var6
##  [1,]   -1   -1   -1   -1   -1   -1
##  [2,]    1   -1   -1   -1   -1   -1
##  [3,]   -1    1   -1   -1   -1   -1
##  [4,]    1    1   -1   -1   -1   -1
##  [5,]   -1   -1    1   -1   -1   -1
##  [6,]    1   -1    1   -1   -1   -1
##  [7,]   -1    1    1   -1   -1   -1
##  [8,]    1    1    1   -1   -1   -1
##  [9,]   -1   -1   -1    1   -1   -1
## [10,]    1   -1   -1    1   -1   -1
## [11,]   -1    1   -1    1   -1   -1
## [12,]    1    1   -1    1   -1   -1
## [13,]   -1   -1    1    1   -1   -1
## [14,]    1   -1    1    1   -1   -1
## [15,]   -1    1    1    1   -1   -1
## [16,]    1    1    1    1   -1   -1
## [17,]   -1   -1   -1   -1    1   -1
## [18,]    1   -1   -1   -1    1   -1
## [19,]   -1    1   -1   -1    1   -1
## [20,]    1    1   -1   -1    1   -1
## [21,]   -1   -1    1   -1    1   -1
## [22,]    1   -1    1   -1    1   -1
## [23,]   -1    1    1   -1    1   -1
## [24,]    1    1    1   -1    1   -1
## [25,]   -1   -1   -1    1    1   -1
## [26,]    1   -1   -1    1    1   -1
## [27,]   -1    1   -1    1    1   -1
## [28,]    1    1   -1    1    1   -1
## [29,]   -1   -1    1    1    1   -1
## [30,]    1   -1    1    1    1   -1
## [31,]   -1    1    1    1    1   -1
## [32,]    1    1    1    1    1   -1
## [33,]   -1   -1   -1   -1   -1    1
## [34,]    1   -1   -1   -1   -1    1
## [35,]   -1    1   -1   -1   -1    1
## [36,]    1    1   -1   -1   -1    1
## [37,]   -1   -1    1   -1   -1    1
## [38,]    1   -1    1   -1   -1    1
## [39,]   -1    1    1   -1   -1    1
## [40,]    1    1    1   -1   -1    1
## [41,]   -1   -1   -1    1   -1    1
## [42,]    1   -1   -1    1   -1    1
## [43,]   -1    1   -1    1   -1    1
## [44,]    1    1   -1    1   -1    1
## [45,]   -1   -1    1    1   -1    1
## [46,]    1   -1    1    1   -1    1
## [47,]   -1    1    1    1   -1    1
## [48,]    1    1    1    1   -1    1
## [49,]   -1   -1   -1   -1    1    1
## [50,]    1   -1   -1   -1    1    1
## [51,]   -1    1   -1   -1    1    1
## [52,]    1    1   -1   -1    1    1
## [53,]   -1   -1    1   -1    1    1
## [54,]    1   -1    1   -1    1    1
## [55,]   -1    1    1   -1    1    1
## [56,]    1    1    1   -1    1    1
## [57,]   -1   -1   -1    1    1    1
## [58,]    1   -1   -1    1    1    1
## [59,]   -1    1   -1    1    1    1
## [60,]    1    1   -1    1    1    1
## [61,]   -1   -1    1    1    1    1
## [62,]    1   -1    1    1    1    1
## [63,]   -1    1    1    1    1    1
## [64,]    1    1    1    1    1    1
  1. Normalisasi Data:
    Data \(x\) dan \(y\) harus dinormalisasi untuk memastikan penalti \(\lambda\) bersifat adil terhadap semua variabel.
sigma.beta<-sum(abs(ols.tb$coefficients))
s<-0.5*sigma.beta #misalnya saja
b0<-rep(-s,2^6)

sdata<-as.data.frame(scale(data.frame(y,x)))
yscale<-as.matrix(sdata$y);yscale
##              [,1]
##  [1,]  0.15088482
##  [2,]  0.15088482
##  [3,]  0.44954345
##  [4,]  0.21725341
##  [5,] -0.23073453
##  [6,] -0.33028740
##  [7,] -0.96078893
##  [8,]  0.71501778
##  [9,]  0.44954345
## [10,] -0.14777380
## [11,] -0.38006384
## [12,] -0.61235388
## [13,] -0.46302456
## [14,] -0.81145962
## [15,] -1.60788262
## [16,] -1.60788262
## [17,] -0.89442035
## [18,]  2.04238943
## [19,]  1.71054652
## [20,]  2.29127162
## [21,]  0.23384555
## [22,] -0.76168319
## [23,] -0.81145962
## [24,] -1.12671039
## [25,] -0.14777380
## [26,]  1.19619000
## [27,]  0.98049211
## [28,]  1.71054652
## [29,] -0.71190675
## [30,] -0.06481307
## [31,] -0.84464392
## [32,]  0.21725341
  1. Matriks \(D\), \(d\), dan Kendala \(b_0\):
    • \(D = 2(X^T X)\), dengan \(X\) adalah matriks prediktor.
    • \(d = 2X^T y\), dengan \(y\) adalah vektor target.
    • \(b_0 = -s\), dengan \(s = 0.5 \times \text{total penalti}\).
xscale<-as.matrix(sdata[,2:7])
D<-2*t(xscale)%*%xscale
d<-2*t(yscale)%*%xscale
  1. Solusi dengan solve.QP:
solve.QP(D,d,t(A),b0)$solution
## [1] -0.2425580  0.2715466 -0.2039718  0.1171394 -0.6803694  0.1190301

Kesimpulan Akhir

  1. Quadratic Programming (QP):
    • QP adalah metode fleksibel untuk menyelesaikan optimasi fungsi kuadrat dengan kendala linear.
    • Dapat digunakan dalam berbagai kasus, termasuk regresi (OLS) dan regularisasi (LASSO).
  2. OLS dan LASSO:
    • OLS mencari koefisien yang meminimalkan error, tetapi tidak memiliki regularisasi, sehingga rawan overfitting.
    • LASSO menambahkan penalti \(L_1\), yang memungkinkan seleksi variabel otomatis dan menghasilkan model yang lebih sederhana.
  3. Penerapan:
    • Implementasi dalam R melalui fungsi solve.QP memungkinkan analisis QP untuk masalah kompleks, termasuk regresi dengan banyak kendala.
  4. Rekomendasi:
    Untuk data besar atau kasus dengan banyak variabel, gunakan regularisasi seperti LASSO untuk menghasilkan model yang lebih robust dan efisien.