Quadratic Programming

1,954 Views

Sinopis Simple Quadratic Programing

Pada persoalan Non Linear Programming ditandai dengan adanya f(x) yaitu fungsi subjekti dan kendalanya melibatkan non linear seperti mempunyai pangkat orde n. Pembahasan Quadratic Programming merupakan salah satunya yaitu fungsi objektif melibatkan variabel kuadrat dan mempunyai kendala berupa pertidaksamaan linear. Contoh soal Quadratic Programming yaitu

fungsi objektif/tujuan

$z = -x_1-x_2+\frac{1}{2}x_1^2+x_2^2-x_1x_2$

dengan kendala

$x_x+x_2\leq 3$

$2-x_1-3x_2\leq -6$

$x_1,x_2\geq0$

Kalian pelajari saja Quadratic Programming yang merupakan pemecahan masalah pada Support Vector Machine. Quadratic Programming dalam bentuk umum yaitu

$\underset{\chi}{min} \: \:\frac{1}{2}\chi^TH\chi+f^T\chi$

kendala

$A\chi\leq b$

$A_{eq}\chi=b{eq}$

$lower\leq\chi\leq upper$

Quadratic Programming bisa kalian selesaikan menggunakan function $quadprog$ dengan paramater $fH,f,A,b,A_{eq},b_{eq},l,ug,H$ . Seperti pada contoh berikut

$\underset{x,y}{min} \; \frac{1}{2}x^2+3x+4y$

dengan kendala

$x,y\geq 0$

$x+3y\geq 15$

$2x+5y\leq100$

$3x+4y\leq80$

maka langkah yang harus kalian lakukan adalah mengubah ke bentuk persamaan umum Quadratic Programming

$\underset{x,y}{min} \; \frac{1}{2} \begin{pmatrix} x \\ y \\ \end{pmatrix}^{T} \begin{pmatrix} 1 & 0\\ 0 & 0\\ \end{pmatrix} \begin{pmatrix} x \\ y \\ \end{pmatrix} + \begin{pmatrix} 3\\ 4\\ \end{pmatrix}^{T} \begin{pmatrix} x\\ y\\ \end{pmatrix}$

$\begin{pmatrix} -1 & -3\\ 2 & 5\\ 3 & 4\\ \end{pmatrix} \begin{pmatrix} x\\ y\\ \end{pmatrix} \leq \begin{pmatrix} -15\\ 100\\ 80\\ \end{pmatrix}$

$\begin{pmatrix} 0\\ 0\\ \end{pmatrix} \leq x$

clc;clear all;close all;
H = diag([1; 0]);
f = [3; 4];
A = [-1 -3; 2 5; 3 4];
b = [-15; 100; 80];
l = zeros(2,1);
Aeq = [];
Beq = [];
u = [];
x0 = [];
options = optimset('Algorithm','interior-point-convex');
[x,fval] = quadprog(H,f,A,b,Aeq,Beq,l,u,x0,options);

hasil

>> x

x =

    0.0000
    5.0000

>> fval

fval =

   20.0000

>>

Kita dapat menyimplkan bahwa nilai optimal yaitu $x=0$ dan $y=5$ dengan hasil $20$