makalah teori optimisasi - fungsi kuasikonveks dan optimalisasinya
TRANSCRIPT
TUGAS KULIAH TEORI OPTIMISASI
FUNGSI KUASIKONVEKS DAN OPTIMALISASINYA
Disusun oleh :
Yuan Aeni Fathonah 13/347910/PA/15391
Umnia Syahida Zulfa 13/347969/PA/15405
Reynaldo Christian 13/350258/PN/13396
Mega Pangastuti 13/348018/PA/15421
Agus Putantri 13/347950/PA/15401
Dosen Pengampu : Dr. Salmah, M.Si
DEPARTEMEN MATEMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS GADJAH MADA
2016
I. PENDAHULUAN
A. Latar Belakang
Pada dasarnya, fungsi kuasikonveks merupakan generalisasi dari fungsi konveks.
Kuasikonveksitas merupakan perluasan dari konsep unimodalitas (sifat matematika yang
memiliki mode unik) menjadi konsep yang lebih multidimensi dan memperbolehkan
adanya tipe saddle point (titik pelana) tertentu, yang merupakan masalah dalam
optimimisasi turunan pertama seperti metode gradient descent (Hazan et al,2014). Sifat
konveks juga dimiliki oleh fungsi kuasikonveks, tetapi apabila fungsi merupakan
kuasikonveks, belum tentu fungsi tersebut bersifat konveks. Sifat konveks yang diminati
adalah sifat titik optimum lokalnya yang juga merupakan titik optimum global, artinya
titik optimum global dari suatu fungsi hampir bisa dipastikan untuk ditemukan melalui
pencarian titik minimum lokalnya. Sifat tersebut terkadang di dapat ditemukan pada
fungsi kuasikonveks, yang merupakan fungsi dengan persyaratan yang lebih longgar dan
meluas dibandingkan dengan fungsi konveks. Permasalahan optimisasi di kehidupan
sehari β sehari tentunya akan sulit untuk memenuhi persyaratan fungsi konveks, sehingga
akan lebih mudah untuk melakukan optimisasi pada fungsi kuasikonveks.
Penerapan fungsi kuasikonveks dan optimalisasinya dapat dilakukan untuk mesh
smoothing (langkah penting dalam banyak permasalahan komputasi yang dapat
persamaan difrensialnya digunakan untuk menjelaskan aliran udara, perpindahan panas,
penerangan global, dan permasalahan yang serupa), pembentukan grafik, gamut warna
yang dioptimalkan, statistic robust, dan lain-lain (Eppstein,2005).
B. Rumusan Masalah
Rumusan Masalah
1. Himpunan Konveks, Fungsi Konveks, Epigraph, dan Sub-level.
2. Fungsi Kuasikonveks.
3. Contoh dari fungsi kuasikonveks
4. Hubungan Antara Fungsi Konveks dan Fungsi Kuasikonveks
II. PEMBAHASAN
A. Himpunan Konveks, Epigraph, dan Himpunan Level Bawah
1. Himpunan Konveks
DEFINISI 1
a. Himpunan S β βn konveks jika setiap titik pada ruas garis yang menghubungkan
sebarang dua titik di dalam juga berada di dalam S. Atau dapat dituliskan juga
dalam bentuk b di bawah ini.
b. Himpunan S β βn konveks jika diambil dua titik sebarang di dalam himpunan S
kombinasi konveksnya juga berada di dalam S. Diberikan π β [0,1]
(βx1 , x2 β S) (1 - π) x1 + π x2 β S S himpunan konveks
Himpunan Konveks
Himpunan Non Konveks
2. Fungsi Konveks
DEFINISI 2
Fungsi Ζ : S β β dikatakan konveks pada himpunan konveks S β βn jika
Ζ (ππ₯ + (1 β π)π¦) β€ π Ζ(x) + (1 - π) Ζ(y)
untuk semua π π [0,1] dan x, y π π.
3. Epigraph
DEFINISI 3
Epigraph dari fungsi Ζ : S β β, S β βn himpunan konveks, didefinisikan sebagai
Epi Ζ = {(x,z)|f(x) β€ π§}
Dengan x π π πππ π§ π β.
4. Himpunan Sublevel
DEFINISI 4
Himpunan level bawah dari fungsi Ζ : S β β, S β βn himpunan konveks,
didefinisikan sebagai
LπΌ = {x| x π π, Ζ(x) β€ πΌ},
Untuk sebarang πΌ π β.
B. Fungsi Kuasikonveks
1. Fungsi Kuasikonveks
DEFINISI 5
Suatu fungsi π: π π β π adalah kuasikonveks jika setiap himpunan sublevel
ππΌ = { x β dom f |f(x) β€ Ξ± }
adalah konveks.
Fungsi kuasikonveks mempunyai banyak fitur sama dengan fungsi konveks, namun juga
sejumlah perbedaan penting. Sifat-sifat kuasikonveks berikut membantu dalam
menentukan kekuasikonvekskan:
1. π kuasikonveks jika dan hanya jika π kuasi konveks pada garis, yaitu π(π₯0 + π‘h)
kuasikonveks dalam π‘ untuk setiap π₯0, h
2. Modifikasi Ketaksamaan Jensen: π kuasikonveks βΊ untuk setiap π₯, π¦ β πππ π,
π β [0,1],
(ππ₯ +(1 β π) π¦) β€ max {π(π₯), π(π¦)};
3. Untuk π terdiferensial, π kuasikonveks βΊ untuk semua π₯, π¦ β πππ π
(π¦) β€ π(π₯) βΉ (π¦ β π₯)π βπ(π₯) β€ 0
4. Perkalian positif
π kuasikonveks, πΌ β₯ 0 βΉ πΌπ kuasikonveks.
5. Supremum sepotong-sepotong: π1, π2 kuasikonveks βΉ max {π1, π2}
kuasikonveks. (merupakan perluasan ke supremum atas sebarang himpunan).
6. Transformasi affine dari domain, π kuasikonveks βΉ (π΄π₯ + π) kuasikonveks.
7. Transformasi fraksional linear dari domain, π kuasikonveks βΉ f((Ax+b)/(c^T
x+d)) kuasikonveks pada c^T x+d > 0.
8. Komposisi dengan fungsi naik monoton: π kuasikonveks, π monoton naik βΉ
(π(π₯)) kuasikonveks.
9. Jumlahan fungsi kuasikonveks secara umum bukan fungsi kuasikonveks.
10. π kuasikonveks dalam π₯,π¦ βΉ π(π₯) = infπ¦π(π₯,π¦) kuasikonveks dalam π₯.
2. Fungsi kuasikonveks di R
Dianggap fungsi bersifat kontinu, dikarnakan kondisi awal pada kondisi umum
diaanggap memberatkan dan tidak efisien. Sebuah fungsi π: π β π bersifat
quasiconvex jika dan hanya jika setidaknya mengikuti satu dari kondisi berikut:
π bersifat tidak menurun (nondecreasing)
π bersifat tidak menaik (nonincreasing)
Ada sebuah titik π π π ππ π sehingga untuk π‘ < π (πππ π‘ π π ππ π). π
bersifat nonincreasing dan untuk untuk π‘ β₯ π (πππ π‘ π π ππ π). π bersifat
nondecreasing.
Titik c dapat dipilih dari titik mananpun yang merupakan optimim global π.
Grafik. Sebuah Fungsi quasiconvex di R. Fungsi bersifat nonincreasing untuk π‘ β€ π
dan non decreasing di π‘ β₯ π
2. Fungsi Kuasikonkaf dan Fungsi Kuasilinear
Suatu fungsi π: π π β π adalah kuasikonkaf jika β π kuasikonveks, yaitu himpunan
superlevel {π₯| π(π₯) β₯ πΌ} konveks.
Suatu fungsi yang merupakan fungsi kuasikonveks dan kuasikonkaf disebut
kuasilinear.
CONTOH 6
Logarithm. π(π₯) = log π₯ , x β R+
Karena setiap himpunan sublevel ππΌ = { x β dom π | π(π₯) = log π₯ β€ Ξ± }
merupakan himpunan konveks, maka fungsi π(π₯) = log π₯ kuasikonveks.
Karena setiap himpunan superlevel ππΌ = { x β dom π | π(π₯) = log π₯ β₯ Ξ± }
merupakan himpunan konveks, maka fungsi π(π₯) = log π₯ kuasikonkaf.
Karena π(π₯) = log π₯ kuasikonveks dan kuasikonkaf, maka π(π₯) = log π₯
kuasilinear.
3. Contoh Fungsi Kuasikonveks
1. Diketahui Fungsi : π: β+ β β
π(π₯) {
π₯3 ππ 0 β€ π₯ β€ 1,1 ππ 1 β€ π₯ β€ 2
π₯3 ππ π₯ > 2
Diketahui bahwa π bersifat tidak menurun (non-decreasing), sehingga dikatakan
kuasikonfeks dan kuasikonkaf di β. Tetapi π bersifat diskontinu di x = 2. Sehingga
π konstan di (1,2) dan setiap titik dialam interval terbuka tersebut merupakan lokal
minimum sekaligus merupakan lokal maksimum. Tetapi tidak ada titik pada (1,2)
yang merupakan maksimum global maupun minimum lokal. Apabila diturunkan
πβ²(0) = 0, sedangkan nilai 0 bukan merupakan minimum maupun maksimum
lokal.
2. β|π₯| merupakan kuasikonfeks di β , tetapi tidak konveks
0
2
4
6
8
10
12
14
16
18
0 0.5 1 1.5 2 2.5 3
Contoh 1
3. Internal Rate of Return adalah satuan yang digunakan dalam anggaran modal untuk
mengukur keuntungan dari sebuah investasi . IRR merupakan angka pemotong
(discount rate) yang dapat mengurangi NPV dari seluruh aliran kas suatu proyek
menjadi 0. Misalkan π₯ = (π₯0π₯1 β¦ π₯π) merupakan serangkaian aliran kas yang terjadi
pada periode n, dimana π₯π > 0 berarti terjadi pendapatan pada periode i, sedangkan
π₯π < 0 berarti terjadi pengeluaran pada periode i. Dapat didefiniskan present value
dari aliran kas dengan bunga π β₯ 0 sebagai berikut
ππ(π₯,π) = β(1 + π)βπ
π
π=0
π₯π
(Faktor (1 + π)βπ merupakan faktor pengurang untuk pembayaran dari pihak lain
maupn pihak sendiri dalam periode i).
Anggap aliran kas untuk π₯0 < 0 dan (π₯0π₯1 β¦ π₯π) > 0, artinya dimulai investasi |π₯0|
pada periode 0 dan jumlah dari aliran kas lainya, π₯1 + β― π₯π (tanpa adanya faktor
pengurang pada jumlahnya) , melebihi investasi awal.
0
0.2
0.4
0.6
0.8
1
1.2
1.4
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
Contoh 2
Keadaan aliran kas tersebut dapat dituliskan dengan ππ(π₯, 0) > 0 πππ ππ(π₯, π) β
π₯0 < 0 dengan π β β, artinya untuk setidaknya satu π β₯ 0, maka didapatkan
ππ(π₯, π) = 0. Dapat didefinikan IRR untuk aliran kas sebagai bunga terkecil π β₯ 0
untuk nilai present value sama dengan 0, dengan persamaan :
πΌπ π (π₯) = inf {π β₯ 0|ππ(π₯, π) = 0}
IRR dapat dibilang fungsi quasiconcave x (dibatasi dengan π₯0 < 0, (π₯0π₯1 β¦ π₯π) > 0)
. Untuk mengetahuinya, fungsi dituliskan
πΌπ π (π₯) β₯ π β ππ(π₯, π) > 0, π’ππ‘π’π 0 β€ π β€ π
Bagian kiri fungsi menyatakan himpunan R-superlevel dari IRR. Sedangkan sisi
kanan fungsi merupakan perpotongan dari himpunan {π₯|ππ(π₯, π) > 0} , dengan
index oleh r, dalam interval 0 β€ π β€ π . Untuk setiap r, ππ(π₯, π) > 0 didefinikan
sebagai halfspace terbuka, sehingga sisi kanan fungsi menggambarkan sifat fungsi
konveks.
4. Sifat β Sifat Fungsi Kuasikonveks
a. Hubungan Fungsi Konveks dan Fungsi Kuasikonveks
TEOREMA 7
Jika fungsi π: π β π konveks pada himpunan konveks π β βπ, maka f kuasikonveks
di π.
Bukti :
Diketahui f konveks, artinya
π(π + (1 β π)π¦) β€ ππ(π₯) + (1 β π)π(π¦)
Ketaksamaan di atas dapat ditulis sebagai berikut
ππ(π₯) + (1 β π)π(π¦) β€ ππππ₯{π(π₯), π(π¦)} + (1 β π)πππ₯{π(π₯), π(π¦)}
Misal
π(π₯) β₯ π(π¦) ππ‘ππ’ πππ₯{π(π₯), π(π¦)} = π(π₯)
Maka
ππππ₯{π(π₯), π(π¦)} + (1 β π){π(π₯), π(π¦)} = ππ(π₯) + (1 β π)π(π₯)
= ππ(π₯) + π(π₯) β ππ(π₯)
= π(π₯)
= πππ₯{π(π₯), π(π¦)}
Artinya
ππ(π₯) + (1 β π)π(π¦) β€ ππππ₯{π(π₯), π(π¦)}
Untuk setiap π β [0,1].
Jadi, terbukti fungsi f kuasikonveks β
CONTOH 8
π(π₯) = ln π₯ dengan π: (0, β) β β adalah fungsi kuasikonveks, namun bukan fungsi
konveks.
Dari gambar di atas terlihat jelas bahwa fungsi π(π₯) = ln π₯ merupakan fungsi
kuasikonveks namun bukan fungsi konveks.
b. Hubungan Fungsi Kuasikonveks dengan Himpunan Sublevel
TEOREMA 9
Fungsi π: π β β dikatakan kuasikonveks pada himpunan konveks π β βπ jika dan
hanya jika himpunan level bawahnya, yaitu
πΏπΌ = {π₯|π(π₯) β€ πΌ},
Konveks untuk setiap π₯ β π πππ πΌ β β.
Bukti :
(βΉ) Diketahui f kuasikonveks
Misal π₯, π¦ β πΏπΌ, artinya π(π₯) β€ πΌ ππππ(π¦) β€ πΌ, maka kita punya
π(ππ₯ + (1 β π)π¦) β€ πππ₯{π(π₯), π(π¦)} β€ πΌ.
Sehingga ππ₯ + (1 β π)π¦ β πΏπΌ
Jadi, terbukti πΏπΌ himpunan konveks.
(βΈ) Diketahui πΏπΌ konveks.
Tanpa menghilangkan keumuman, asumsikan πππ₯{π(π₯), π(π¦)} = π(π₯) dan pandang
bentuk himpunan level bawah πΏπΌ dengan πΌ = π(π₯), yaitu
πΏπ(π₯) = {π’|π(π’) β€ π(π₯)}.
Jelas, π¦ β πΏπ(π₯),
Karena πΏπ(π₯) ππππ£πππ .
π₯ + π(π¦ β π₯) β πΏπ(π₯)
Untuk semua π β [0,1], yaitu
π(π₯ + π(π¦ β π₯)) β€ π(π₯) = πππ₯{π(π₯), π(π¦)}.
Jadi, terbukti fungsi f kuasikonveks. β
c. Keterdiferensialan Funsi Kuasikonveks
TEOREMA 10
Misal f terdiferensial satu kali di βπ. Maka f kuasikonveks di βπ jika dan hanya
jika π(π¦) β€ π(π₯) menunjukkan bahwa βπ(π₯)π(π¦ β π₯) β€ 0.
Bukti :
βf adalah gradien dari f
βf = (βf
βπ₯1, β¦ ,
βf
βπ₯π )
βπ(π₯)π = πβ²(π₯)
(βΉ) Diketahui f terdiferensialkan satu kali di βπ πππ f kuasikonveks.
Misalkan π(π¦) β€ π(π₯), karena f kuasikonveks artinya f memenuhi ketaksamaan
berikut ini.
π(ππ¦ + (1 β π)π₯) β€ π(π₯)
Untuk setiap π₯, π¦ β π β βπ πππ π β [0,1].
Bagi kedua sisi dengan π
π(π₯ + π(π¦ β π₯)) β π(π₯)
πβ€ 0
Ambil limit π βΆ 0, didapat
limπβΆ0
π(π₯ + π(π¦ β π₯)) β π(π₯)
π= πβ²(π₯)(π¦ β π₯) β€ 0
Jadi, terbukti
βπ(π₯)π(π¦ β π₯) β€ 0
(β) Diketahui f adalah fungsi yang terdiferensialkan satu kali di βπ dan memenuhi
π(π¦) β€ π(π₯), sedemikian sehingga
πβ²(π₯)(π¦ β π₯) β€ 0
β limπβΆ0
π(π₯ + π(π¦ β π₯)) β π(π₯)
πβ€ 0
βπ(π₯ + π(π¦ β π₯)) β π(π₯)
πβ€ 0
β π(π₯ + π(π¦ β π₯)) β π(π₯) β€ 0
β π(π₯ + π(π¦ β π₯)) β€ π(π₯)
Karena π(π¦) β€ π(π₯), ππππ
π(π₯ + π(π¦ β π₯)) β€ πππ₯{π(π₯), π(π¦)}
Jadi, terbukti fungsi f kuasikonveks. β
5. Optimalisasi Fungsi Konveks dan Fungsi Kuasikonveks
Perhatikan fungsi konveks pada β berikut ini. Fungsi tersebut memiliki titik optimal lokal
x1 karena fβ(x1) = 0 (kondisi optimalitas pada fungsi konveks).
Pada fungsi konveks, titik optimal local pastilah merupakan titik optimal global. Sehingga
titik x1 pada fungsi di atas merupakan optimal global.
Lalu apakah kondisi optimalitas yang berlaku pada fungsi konveks juga pasti berlaku pada
fungsi kuasikonveks?
Perhatikan fungsi kuasikonveks pada β berikut ini.
Gambar Fungsi Kuasikonveks pada β
Fungsi kuasikonveks di atas memiliki titik optimum local di x. Namun titik x1
bukanlah titik optimum global. Hal ini menunjukkan bahwa kondisi optimalitas fβ(x)
= 0 hanya berlaku untuk fungsi konveks dan tidak berlaku pada fungsi
kuasikonveks.
CONTOH 11
Diberikan suatu fungsi π βΆ β β β dengan definisi sebagai berikut
π(π₯) {
π₯3 ππ 0 β€ π₯ β€ 1,1 ππ 1 β€ π₯ β€ 2
π₯3 ππ π₯ > 2
Fungsi π merupakan fungsi kuasikonveks. Berikut grafiknya
Perhatikan bahwa :
Fungsi π merupakan fungsi naik.
Fungsi π konstan (πβ²(π₯) = 0) pada interval (1,2] , tetapi setiap titik pada interval
tersebut bukanlah titik maksimum global atau titik minimum global.
πβ²(0) = 0 padahal titik π₯ = 0 bukanlah titik maksimum local atau titik minimum
local.
Dari uraian dan contoh di atas didapat bahwa :
1. Kondisi optimalitas fungsi konveks yakni πβ²(π₯) = 0 tidak berlaku untuk fungsi
kuasikonveks.
2. Titik minimum/maksimum local pada fungsi kuasikonveks belum tentu
merupakan titik minimum/maksimum global.
DAFTAR PUSTAKA
Luenberger, D.G. 1969. Optimization by Vector Space Methods. John Wiley and Sons.
Mangasarian, O. 1994. Nonlinear Programming. Society for Industrial and Applied
Mathematics.
Hazan,E., K.Y. Levy, and S. Shalev-Shwartz.2014. Beyond Convexity: Stochastic Quasi-Convex
Optimization. https://arxiv.org/pdf/1507.02030.pdf. Diakses pada 6 Mei 2016.
Eppstein, David. 2005. Quasiconvex Programming. Combinational and Computational
Geometry Vol.25
Boyd,S.,Vndenberghe,L. 2004. Convex Optimization. Cambridge University Press.