Cara Menyusun Persamaan Quadratic Programming (QP) untuk metode Optimasi

By | January 31, 2025
332 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 dan x\geq 0

  • Q: matriks simetris positif semi-definit (definisi fungsi kuadratik).
  • c: vektor koefisien linear.
  • : matriks batasan linier.
  • : 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}:

See also  Beberapa Bentuk Bangun Dasar Rumus Luas dan Keliling

    \[ \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, dan
  • 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

Kode python akan tampil jika telah login

Existing Users Log In




Enter Captcha Here :

See also  Beberapa Bentuk Bangun Dasar Rumus Luas dan Keliling
   

Kasus Quadratic Programming yang lain

    \[ f(x) = \frac{1}{2}x_1^2+x_2^2+x_1x_2-3x_1-4x_2 \]

dengan batasan

    \[ x_1+x_2\leq4 \]

    \[ x_1\geq0 \]

    \[ x_2\geq0 \]

Jawab
Fungsi Objektif Q dan c yaitu

Login terlebih dahulu jika ingin mendapatkan jawaban lebih lanjut

Existing Users Log In




Enter Captcha Here :