BAB 2
LANDASAN TEORI
Pada bab ini akan dijelaskan mengenai teori – teori yang berhubungan dengan pembahasan ini sehingga dapat dijadikan sebagai landasan berpikir dan akan mempermudah dalam hal pembahasan hasil utama pada bab berikutnya. Adapun teori – teori tersebut mencakup pengertian dari pemrograman nonlinear, fungsi konveks, metode
Lagrange,
metode
Newton,
metode Wolfe,
kondisi
Kuhn-Tucker,
pemrograman kuadratis, dan metode Sequential Quadratic Programming.
2.1 Pemrograman Nonlinear
Menurut Bradley dkk (1976), persoalan umum optimisasi adalah memilih n variabel keputusan
dari daerah fisibel yang diberikan untuk mengoptimasi
(maksimum atau minimum) fungsi tujuan yang diberikan
dari variabel keputusan. Persoalan ini disebut persoalan pemrograman nonlinear jika fungsi tujuannya nonlinear dan atau daerah fisibelnya ditentukan oleh kendala nonlinear. Jadi bentuk minimisasi persoalan pemrograman nonlinear ditulis sebagai:
subject to:
dimana masing-masing fungsi kendala
sampai
diberikan. Batasan nonnegatif
pada variabel dapat dengan menambahkan kendala tambahan:
Universitas Sumatera Utara
Masalah optimisasi di atas dapat ditulis dalam bentuk yang lebih sederhana sebagai berikut:
subject to:
Untuk kendala persamaan dan
dapat ditulis sebagai dua kendala pertidaksamaan . Sebagai tambahan, jika menambahkan variabel slack,
masing-masing kendala pertidaksamaan ditransformasi ke kendala persamaan.
Fokus utama dari pemrograman nonlinear adalah terkait dengan eksistensi dari solusi optimal, karakterisasi dari solusi optimal dan algoritma untuk menghitung solusi optimal. Masalah pemrograman nonlinear mempunyai 2 jenis persoalan yaitu masalah nonlinear berkendala dan nonlinear tidak berkendala. Untuk persoalan nonlinear tidak berkendala dapat dipecahkan dengan metode Newton sedangkan untuk persoalan nonlinear berkendala dapat dipecahkan dengan metode Penalty dan Barrier, Sequential Quadratic Programming (SQP), ataupun Primal-Dual Interior Point (PDIP). Metode Penalty dan Barrier merupakan cara tidak langsung karena prosedur metodenya yaitu mendekati persoalan optimisasi berkendala dengan persoalan yang tidak berkendala. Contoh metode yang menerapkan cara langsung yaitu SQP dan PDIP. (Bertsekas, 2007).
2.2 Optimum Global dan Lokal
Sebuah fungsi tujuan f(x) memiliki sebuah minimum lokal di selang (yang kecil) yang berpusat di
jika terdapat sebuah
sedemikian rupa sehingga
untuk semua x dalam selang ini pada mana fungsi ini dedefinisikan. Jika untuk semua x pada mana fungsi ini didefinisikan, maka minimum di
(di
samping adalah lokal) adalah suatu minimum global. Maksimum lokal dan global didefinisikan dengan cara yang sama tetapi dengan tanda ketidaksamaan yang terbalik (Bronson, 1996).
Universitas Sumatera Utara
Gambar 1.1 Maksimum-minimum lokal dan global Fungsi yang digambarkan di atas secara grafik hanya didefiniskan pada [a,b]. Fungsi ini memiliki minimum lokal di di
dan maksimum global di
; maksimum lokal di
; minimum global
dan b.
Definisi 2.1: Jika
adalah solusi fisibel untuk persoalan maksimisasi dengan
fungsi tujuan f(x). Kita menyebut x: 1. Sebuah global maksimum jika
untuk setiap titik fisibel
2. Sebuah lokal maksimum jika
untuk setiap titik fisibel
cukup dekat dengan x yaitu jika ada sebuah bilangan (sangat kecil) sehingga kapanpun masing-masing variabel yaitu,
dan y fisibel maka
dalam
dari
.
Minimum lokal dan global analog dengan definisi di atas. Untuk beberapa keadaan, maksimum dan minimum lokal disebut global. Gambar 1.2(a) di bawah minimum lokal merupakan global. Fungsi ini disebut konveks. Gambar 1.2(b) di bawah maksimum lokal merupakan maksimum global. Fungsi ini disebut konkaf. Karena alasan ini fungsi konveks selalu diminimumkan sedangkan fungsi konkaf selalu dimaksimumkan (Bradley dkk, 1976).
Universitas Sumatera Utara
Gambar 1.2 Fungsi konveks dan konkaf
2.3 Fungsi Konveks dan Konkaf
Menurut Luenberger (1984), fungsi konveks adalah dimana untuk setiap dua titik y dan z, dapat ditarik garis yang menghubungkan f(y) dan f(z) pada fungsi tersebut. Secara aljabar definisinya sebagai berikut:
Definisi 2.2: Misalkan
. Titik-titik dengan bentuk
untuk
disebut
konveks kombinasi dari y dan z.
Definisi 2.3: Sebuah himpunan maka berlaku
disebut himpunan konveks jika untuk setiap
dan
.
Definisi 2.4: Sebuah fungsi f(x) disebut konveks jika untuk setiap y dan z dan setiap
Disebut strictly konveks jika untuk setiap dua titik berbeda y dan z dan setiap
Definisi 2.5: Sebuah fungsi f(x) disebut konkaf jika untuk setiap y dan z dan setiap
Universitas Sumatera Utara
Disebut strictly konkaf jika untuk setiap dua titik berbeda y dan z dan setiap
Mengalikan fungsi konveks dengan -1 akan menghasilkan fungsi konkaf. Menjumlahkan beberapa fungsi konveks akan menghasilkan fungsi konveks juga. Begitu juga dengan mengalikan dengan pengali nonnegatif akan menghasilkan fungsi konveks.
Teorema 2.1: Perhatikan masalah optimisasi (CP) berikut
Jika S adalah himpunan konveks, minimum lokal untuk masalah (CP) maka
adalah fungsi konveks dan
adalah titik
adalah titik minimum global dari
pada himpunan S. Bukti: Misalkan
bukan titik minimum global, maka terdapat . Sebut
dan y, untuk Karena
yang merupakan kombinasi konveks dari . Hal ini mengakibatkan
, untuk
.
adalah fungsi konveks maka berlaku
Untuk setiap lokal.
yang memenuhi
. Hal ini kontradiksi dengan asumsi bahwa
Dengan
demikian
haruslah
merupakan
titik
adalah minimum minimum
global.
Teorema 2.2: Misalkan S adalah himpunan buka yang konveks dan diferensiabel. Maka
adalah fungsi yang
adalah fungsi konveks jika dan hanya jika memenuhi
kondisi gradient berikut:
Bukti : Misalkan
merupakan fungsi konveks. Maka untuk sebarang
. Berlaku
Universitas Sumatera Utara
Yang mengakibatkan
Selanjutnya ambil
maka diperoleh
Ambil sembarang
dan
. Set
maka diperoleh
dan Ambil kombinasi konveks dari dua persamaan ini maka diperoleh
, Ini menunjukkan bahwa f adalah fungsi konveks.
Teorema 2.3: Misalkan S adalah himpunan buka yang konveks dan
dapat diturunkan dua
kali. Misal H(x) adalah Hessian dari f. Jika f(x) konveks maka H(x) adalah positif semidefit untuk semua Bukti: () Perhatikan jika H(z) positif semidefinit untuk semua
, maka untuk setiap
, deret Taylor orde dua memberikan
Untuk suatu z yang merupakan kombinasi linear dari bahwa
(dengan demikian jelas
). Karena H(z) positif semidefinit maka
Dengan demikian pertidaksamaan gradien terpenuhi dan mengakibatkan f(x) merupakan fungsi konveks. () Jika f(x) konveks dengan cukup kecil,
dan d sebarang arah. Maka untuk
yang
. Dalam hal ini berlaku
dimana
Universitas Sumatera Utara
dengan menggunakan pertidaksamaan gradien maka diperoleh
Bagi pertidaksamaan ini dengan
dan ambil
, maka diperoleh
Maka H(x) adalah positif semidefinit untuk setiap
.
Teorema 2.4: Misalkan
konveks dan dapat diturunkan di X. Jika
minimum global
maka Bukti: Karena
adalah minimum global maka x adalah minimum lokal, dengan demikian
jelas bahwa
Maka jelas bahwa
. Sebaliknya jika
, maka berlaku
adalah titik minimum global.
2.4 Metode Newton
Persoalan nonlinear tidak berkendala mempunyai bentuk umum:
dan X adalah himpunan terbuka. Jika
dimana dikatakan solusi fisibel. Jika
dan meminimumkan
maka x
maka x dikatakan solusi
optimal.
Perhatikan bahwa semua titik minimum lokal
dari suatu fungsi yang
diferensiabel dan kontinu f memenuhi syarat perlu
Persamaan ini merepresentasikan sebuah himpunan dari n buah persamaan nonlinear yang harus diselesaikan sehingga diperoleh .
Universitas Sumatera Utara
Salah satu pendekatan untuk masalah minimisasi f(x) adalah mencari solusi untuk himpunan untuk persamaan
dengan memasukkan suatu cara untuk
menjamin bahwa solusi yang diperoleh tentunya merupakan sebuah minimum lokal. Metode tertua untuk menyelesaikan suatu himpunan persamaan nonlinear adalah metode Newton.
Perhatikan masalah optimisasi tanpa kendala berikut
Pada titik
, f(x) dapat dihampiri dengan
dimana hampiran ini dikenal sebagai ekspansi Taylor Kuadratik pada
, dimana
dan H(x) adalah vektor gradien dan Hessian dari fungsi f.
Perhatikan bahwa h(x) adalah sebuah fungsi yang kuadratik yang dapat diminimisasi dengan menyelesaikan
. Karena gradient dari h(x) adalah
Maka untuk memperoleh solusi cukup diselesaikan
Sehingga diperoleh
Perhatikan bahwa arah
disebut sebagai arah Newton di
Algoritma metode Newton: Step 1 :
Diberikan x0, set k=0
Step 2 :
Set
Step 3 :
Set step size
Step 4 :
Set
. Jika
maka STOP
. Kembali ke step 1
Jika f(x) merupakan fungsi nonkuadratik, metode Newton dapat memberikan solusi yang divergen dan mungkin saja konvergen menuju titik saddle dan titik maksimum yang relatif. Bila hal tersebut terjadi maka metode Newton dapat diimprovisasi dengan mengubah formulasi untuk titik baru
Universitas Sumatera Utara
adalah panjangnya langkah tahapan yang minimum pada arah
dimana
.
Jika kemiringan berubah-ubah pada setiap iterasi sehingga
Gambar 1.3 Metode Newton maka prosedur turunan kedua bisa didapatkan. Dari persamaan di atas kita mendapatkan
Sehingga Jadi, hasil prosedur iterasi sekarang adalah dengan
dan
ada, karena
2.5 Kekonvergenan
Kekonvergenan untuk barisan bilangan riil (Dennis dan Schnabel, 1983): Diberikan sebuah metode iterasi sehingga menghasilkan barisan titik sebuah titik awal diasumsikan bahwa
, ingin diketahui apakah iterasi konvergen ke solusi menyatakan barisan bilangan riil
dari . Jika , maka
definisi berikut menyatakan sifat yang dibutuhkan.
Universitas Sumatera Utara
Definisi 2.6 Jika konvergen ke
maka barisan
dikatakan
jika
Jika dalam tambahan, ada sebuah konstanta
dan sebuah bilangan bulat
sehingga untuk setiap
Teorema Weierstrass untuk barisan Misalkan
adalah barisan tak terbatas (infinit) dari titik-titik dari suatu
himpunan compact F (yaitu himpunan yang tertutup dan terbatas). Maka sebagian subbarisan infinit dati titik-titik
konvergen ke suatu titik di F.
Teorema Weierstrass untuk fungsi Misalkan f(x) adalah fungsi bernilai riil dan kontinu pada suatu himpunan compact yang tidak kosong
. Maka F memuat suatu titik yang dapat meminimumkan
(atau memaksimumkan) f(x) pada himpunan F.
2.6 Metode Pengali Lagrange
Persamaan Lagrange dari persoalan nonlinear seperti yang telah dipaparkan pada bagian 2.1 yaitu sebagai berikut:
dimana
adalah tetapan-tetapan (yang tidak diketahui) yang disebut
pengali Lagrange. Kemudian kita pecahkan sistem n+m persamaan
(Bronson, 1996)
Universitas Sumatera Utara
2.7 Kondisi Karush-Kuhn Tucker
Tabel 1.1 Kondisi Perlu dan Cukup untuk Optimalitas Persoalan
Kondisi perlu untuk
Juga cukup jika
optimalitas Satu variabel tidak
f(x) konkaf
berkendala Banyak variabel tidak
f(x) konkaf
berkendala Berkendala, hanya kendala
f(x) konkaf
nonnegatif (atau
jika
)
Persoalan umum
Kondisi Karush-Kuhn
berkendala
Tucker
f(x) konkaf dan konveks (i=1,2,…,m)
Dari tabel di atas terlihat bahwa untuk kondisi persoalan umum disebut kondisi Karush-Kuhn Tucker (Hillier dan Lieberman,2005). Kondisi perlu dan cukup untuk sebagai solusi optimal untuk persoalan nonlinear berikut (Wallace,2004) :
subject to:
Untuk menggunakan hasil, semua kendala persoalan nonlinear harus kendala .
Kendala
dalam
bentuk
harus
. Kendala dalam bentuk dengan
dan
ditulis
sebagai
harus diganti (Winston
dan
Venkataramanan, 2003). Teorema di bawah ini memberikan kondisi Kuhn-Tucker yang cukup bagi titik
untuk memecahkan persoalan nonlinear di
atas.
Universitas Sumatera Utara
Teorema 2.6: Andaikan persoalan nonlinear di atas adalah persoalan maksimisasi. Jika adalah
solusi
optimal
dari
persoalan
tersebut,
maka
harus memenuhi m kendala dan harus ada pengali yang memenuhi
Teorema 2.7: Andaikan persoalan nonlinear di atas adalah persoalan minimisasi. Jika adalah
solusi
optimal
dari
persoalan
tersebut,
maka
harus memenuhi m kendala dan harus ada pengali yang memenuhi
Skalar
disebut pengali Lagrange. Kondisi
disebut kondisi complementary slackness yang menyatakan dua kemungkinan yaitu: 1. Jika Jika
maka maka kendala
2.8 Pemrograman Kuadratis
Menurut Rao (1977), pemrograman kuadratis merupakan persoalan optimasi nonlinear dimana fungsi tujuannya adalah fungsi minimisasi yang konveks dan semua
Universitas Sumatera Utara
kendalanya berbentuk persamaan atau pertidaksamaan linear. Bentuk umum persoalan pemrograman kuadaratis adalah sebagai berikut: Min. s.t
dimana
d11 d 21 d n1
d12 d 22 dn2
d1n d 2 n d nn
a11 a A = 21 am1
Pada fungsi tujuan di atas yaitu suku
a12 a22 am 2
a1n a2 n amn
menyatakan bagian kuadratis dari fungsi
tujuan dengan D adalah matriks definit positif simetri. Jika D=0 maka menjadi persoalan linear. Karena D adalah matriks definit positif maka f(x) adalah fungsi strictly convex.
Metode untuk menyelesaikan persoalan pemrograman kuadratis yaitu metode Wolfe. Pertama, semua fungsi tujuan dan kendala harus ditambahkan variabel buatan pada masing-masing kendala dengan kondisi Kuhn-Tucker dan variabel basis belum jelas kemudian minimumkan jumlah variabel buatan. Metode wolfe merupakan versi modifikasi dari fase I pada metode simplex dua fase. Untuk menjamin bahwa solusi akhir (dengan variabel buatan sama dengan nol) memenuhi kondisi complementary slackness, metode Wolfe memodifikasi pilihan variabel simplex yang masuk: 1. Tidak diperbolehkan
dari kendala ke-i dan
kedua-duanya sebagai
variabel basis. 2. Tidak diperbolehkan variabel slack atau excess dari kendala ke-i dan kedua-duanya sebagai variabel basis. (Winston dan Venkataramanan, 2003)
Universitas Sumatera Utara
2.9 Metode Sequential Quadratic Programming
Menurut Bertsekas (2007), metode Sequential Quadratic Programming digunakan untuk menyelesaikan persoalan nonlinear yang memiliki kendala dalam bentuk persamaan dengan bentuk umum : Min. f(x) s.t. h(x)=0 Kondisi Karush-Kuhn Tucker (KKT) untuk persoalan ini yaitu sebagai berikut:
dimana
adalah pengali Lagrange dengan kendala yang berbentuk persamaan.
Jika menggunakan persamaan Lagrange
Kondisi Kuhn-Tucker dapat dituliskan sebagai berikut:
Metode Sequential Quadratic Programming menyerupai metode Newton yang digunakan untuk mencari penyelesaian pada optimisasi tidak berkendala.Metode ini menyelesaikan persoalan nonlinear secara langsung daripada mengubah ke barisan persoalan minimisasi yang tidak berkendala. Ide utama dari SQP adalah memodelkan persoalan kendala yang berbentuk persamaan pada titik awal pendekatan
kemudian mencari
dengan subpersoalan pemrograman kuadratis berbentuk:
dimana
Metode Sequential Quadratic Programming atau yang juga dikenal sebagai metode Lagrange-Newton karena metode SQP merupakan penggabungan dari kedua metode tersebut. Algoritmanya secara umum adalah sebagai berikut:
Universitas Sumatera Utara
8. Tentukan 9. Atur k=0 10. Ulang 11. Pecahkan sistem Langrange-Newton untuk menemukan 12. 13. 14. Sampai konvergen Metode SQP merupakan aplikasi dari metode Newton dengan memenuhi kondisi optimal KKT. Menurut Gockenbach (2003), metode SQP memecahkan persoalan nonlinear secara langsung tanpa mengubah ke barisan persoalan minimisasi yang tidak berkendala. Ide dasar analog dengan metode Newton untuk persoalan minimisasi yang tidak berkendala. Metode SQP dapat digunakan untuk menyelesaikan persoalan aplikasi yang kompleksitasnya tinggi (Schittkowski dan Yuan, 2010)
Universitas Sumatera Utara
