Cara Menyusun Persamaan Quadratic Programming (QP) untuk metode Optimasi

1,045 Views

Quadratic Programming (QP) adalah salah satu metode optimasi matematis yang bertujuan untuk menemukan nilai optimal (maksimum atau minimum) dari sebuah fungsi objektif kuadratik dengan batasan linier. QP adalah kasus khusus dari nonlinear programming yang sering digunakan dalam berbagai bidang seperti pembelajaran mesin, ekonomi, teknik, dan keuangan. Aplikasi Quadratic Programming seperti Optimasi Portofolio Keuangan (Investor menggunakan QP untuk meminimalkan risiko portofolio sambil memaksimalkan return dengan batasan dana yang tersedia); Support Vector Machine (QP digunakan untuk melatih model SVM dalam menemukan hyperplane optimal yang memisahkan dua kelas data); Desain Sistem Kendali (dalam kontrol optimal, QP digunakan untuk menyelesaikan masalah regulasi dan perencanaan jalur); Optimasi Energi (QP membantu mengoptimalkan alokasi sumber daya energi, seperti distribusi daya listrik, dengan meminimalkan biaya operasional) Perencanaan Produksi (QP digunakan untuk memaksimalkan efisiensi produksi dengan batasan kapasitas dan waktu)

Masalah Quadratric Programming secara umum dirumuskan sebagai:

$\min_{x} \frac{1}{2} x^TQx+c^Tx$

dengan batasan:

$Ax\le b$

$Q$ : matriks simetris positif semi-definit (definisi fungsi kuadratik).
$c$ : vektor koefisien linear.
$A$ : matriks batasan linier.
$b$ : vektor batasan linier.
arti tanda $^T$ adalah transpose dari matrix

Contoh Soal Quadratic Progrmming

Misalkan kita ingin menyelesaikan masalah Quadratic Programming berikut

$\min_{x} f(x)=\frac{1}{2} x_1^2+x_2^2$

dengan batasan

$x_1+x_2 \geq 1$
$x_1 \geq 0$ dan $x_2 \geq 0$

Jawab

Cara Menyusun Persamaan Quadratic Programming (QP) untuk metode Optimasi, Mari kita ubah menjadi bentuk seperti berikut, untuk matrix simetris Q yaitu

$Q = \begin{pmatrix} 1 & 0 \\0 & 2 \end{pmatrix}$

Maksud dari diatas yaitu ketika

$\frac{1}{2} x^T Qx = \frac{1}{2} \begin{pmatrix} x_1 & x_2 \end{pmatrix} \begin{pmatrix} 1 & 0 \\0 & 2 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} =\frac{1}{2}x_1^2+x_2^2$

arti tanda $^T$ adalah transpose dari matrix. Mari kita analisis apakah pernyataan tersebut benar. Matriks yang Diberikan:

$\frac{1}{2} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}^T \cdot \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix} \cdot \begin{pmatrix} x_1\\ x_2 \end{pmatrix}$

Langkah-Langkah Perhitungan

1. Misalkan:

$x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \quad \text{dan matriks } Q = \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix}.$

Substitusi menjadi:

$\frac{1}{2} \cdot x^T Q x.$

2. Hitung $Q \cdot x$ :

$Q \cdot x = \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1 \cdot x_1 + 0 \cdot x_2 \\ 0 \cdot x_1 + 2 \cdot x_2 \end{pmatrix} = \begin{pmatrix} x_1 \\ 2x_2 \end{pmatrix}.$

3. Hitung $x^T \cdot (Q \cdot x)$ :

$x^T \cdot Q \cdot x = \begin{pmatrix} x_1 & x_2 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ 2x_2 \end{pmatrix} = x_1 \cdot x_1 + x_2 \cdot 2x_2 = x_1^2 + 2x_2^2.$

4. Kalikan dengan $\frac{1}{2}$ :

$\frac{1}{2} \cdot (x_1^2 + 2x_2^2) = \frac{1}{2}x_1^2 + x_2^2.$

Kesimpulan
Hasil dari operasi tersebut adalah:

$\frac{1}{2}x_1^2 + x_2^2.$

sedangkan untuk

$c^Tx$

yang c karena tidak ada, maka dibuat matrix sebagai berikut

$c=\begin{pmatrix} 0 \\0 \end{pmatrix}$

sedangkan batasan dari

$x_1+x_2 \geq 1$
$x_1 \geq 0$ ,
dan $x_2 \geq 0$

harus kita ubah sesuai QP yaitu

$Ax\le b$
$x\geq 0$

caranya dengan dikali -1

$x_1+x_2 \geq 1 *-1 =-x_1-x_2 \leq -1$

sehingga bila kita ubah menjadi matrix A dan b yaitu

$A=\begin{pmatrix} -1 & -1 \\-1 & 0 \\0 & -1 \end{pmatrix}$

dan

$b=\begin{pmatrix} -1 \\0 \\0 \end{pmatrix}$

mari kita coba maka hasilnya sesuai dengan batasan dari Quadratic Programming

$Ax\leq b$

bila kita jabarkan

$A=\begin{pmatrix} -1 & -1 \\-1 & 0 \\0 & -1 \end{pmatrix}$

dan

$b=\begin{pmatrix} -1 \\0 \\0 \end{pmatrix}$

menjadi
$Ax \leq b$ mari kita uji perkalian antar matrix

$\begin{pmatrix} -1 & -1 \\ -1 & 0 \\0 & -1 \end{pmatrix} \begin{pmatrix} x_1 \\x_2 \end{pmatrix} \leq \begin{pmatrix} -1 \\0 \\0 \end{pmatrix}$

baris pertama menghasilkan

$-x_1-x_2\leq -1$

sedangkan

baris kedua $-x_1 \leq 0$ , dan
baris ketiga $-x_2 \leq 0$

merupakan persamaan yang sama dengan $x_1 \geq 0$ dan $x_2 \geq 0$ sehingga semuanya sudah memenuhi syarat yaitu $x \geq 0$

mari kita tulis menggunakan Python

import numpy as np
from scipy.optimize import minimize

# Definisikan fungsi objektif
def objective(x):
    Q = np.array([[1, 0], [0, 2]])  # Matriks Q
    return 0.5 * np.dot(x.T, np.dot(Q, x))  # (1/2) x^T Q x

# Definisikan batasan
def constraint1(x):
    return x[0] + x[1] - 1  # x1 + x2 >= 1 -> x1 + x2 - 1 >= 0

def constraint2(x):
    return x[0]  # x1 >= 0

def constraint3(x):
    return x[1]  # x2 >= 0

# Titik awal
x0 = np.array([0.5, 0.5])  # Titik awal (arbitrer)

# Batasan
constraints = [
    {"type": "ineq", "fun": constraint1},  # x1 + x2 >= 1
    {"type": "ineq", "fun": constraint2},  # x1 >= 0
    {"type": "ineq", "fun": constraint3},  # x2 >= 0
]

# Optimisasi
solution = minimize(objective, x0, constraints=constraints)

# Output hasil
x_opt = solution.x
print("Solusi optimal:", x_opt)
print("Nilai optimal fungsi objektif:", objective(x_opt))

hasilnya

Solusi optimal: [0.66666667 0.33333333]
Nilai optimal fungsi objektif: 0.3333333333333332

penjelasannya yaitu

Fungsi objektif

fungsi kuadratik $f(x) = \frac{1}{2} x_1^2 + x_2^2$ dihitung sebagai $\frac{1}{2} x^T Q_x$

Batasan

$x_1 + x_2 \geq 1$ diterjemahkan menjadi fungsi batasan $x_1 + x_2 -1 \geq 0$
$x_1 \geq 0$ dan $x_2 \geq 0$ diterjemahkan menjadi $x_1 \geq 0$ dan $x_2 \geq 0$

Visulisasi Grafis

Untuk melakukan visualisasi grafis diatas, $\frac{1}{2} x_1^2+x_2^2$ kalian bisa menggunakan library matplotib. Sumbu Z akan mininum ketika $x_1-0.66$ dan $x_2=0.33$