kelompok 5 metode newton multi variabel 2013

Nughthoh Arfawi Kurdhi, M.Sc Department of Mathematics FMIPA UNS

OPTIMASI FUNGSI MULTIVARIABLE TANPA KENDALA DENGAN METODE NEWTON

Susi Ranangga [M0108067] , Aeroni Dwijayanti [M0108078] Hamdani Citra P. [M0110031],

Nafi Nur Khasana [M0110058]

1. Pendahuluan

Dalam kehidupan sehari-hari baik disadari maupun tidak, sebenarnya orang selalu melakukan optimasi untuk memenuhi kebutuhannya. Tetapi optimasi yang dilakukan masyarakat awam lebih banyak dilandasi oleh intuisi daripada teori optimasi. Dalam masalah optimasi terdapat dua bentuk optimasi yaitu fungsi optimasi tanpa kendala dan dengan kendala. Banyak aplikasi dari pemodelan matematika yang berbentuk linear atau nonlinear dalam optimasi fungsi yang mensyaratkan beberapa kendala ataupun tanpa kendala untuk diperoleh suatu solusi optimal. Permasalahan ini berfungsi untuk mencari nilai ektrim dari fungsi tujuan. Persoalan dengan model nonlinear yang tidak disertai kendala dinamakan optimasi nonlinear tanpa kendala. Optimasi merupakan masalah yang berhubungan dengan keputusan yang terbaik, maksimum, minimum dan memberikan cara penentuan solusi yang memuaskan.

Terdapat beberapa metode dalam mencari optimasi multivariable tanpa kendala. Diantaranya metode Univariate, Steepest Descent, dan Newton. Dalam metode Univariate membutuhkan iterasi yang banyak dalam mencari nilai optimasinya. Begitu pula dengan metode Steepest Descent yang nilai iterasinya tergantung pada pemilihan nilai , semaki kecil semakin banyak iterasi yang dibutuhkan. Dari berbagai masalah itu metode Newton memberikan alternatif yang lebih bagus. Dalam makalah ini akan dijelaskan tentang metode Newton beserta contoh kasusnya.

2. Pembahasan

Fungsi Multivariable tanpa Kendala Cara analitis yang diterapkan pada permaslahan optimasi satu variable dapat diterapkan pada permasalahan multivariable. Dalam makalah ini akan dibahas masalah optimasi untuk fungsi lebih dari satu variabel. Seperti masalah minimisasi pada satu variabel;

푚푖푛푖푚푢푚푘푎푛:푧 = 푓(푥 ,푥 , … ,푥 ). Sedangkan bentuk umum dari fungsi multivariable:

푚푖푛푖푚푢푚푘푎푛: 푧 = 푓(푥) =푥푥⋮푥

∈ 푅

Merupakan fungsi dari n variabel 푓:푅 → 푅 tranpose dari matriks 푥 ditulis dengan 푥 = [푥 ,푥 , … ,푥 ]

Penggunaan turunan sebagai syarat perlu dan cukup: ∇푓(푥) = 0 Dan ∇ 푓(푥) definit positif. Sering ada problem yang gagal memenuhi syarat-syarat tersebut tetapi 푓(푥) masih mempuyai optimum, misal 푓(푥) = |푥|.

Metode Newton Dalam analisis numerik, metode Newton juga dikenal dengan metode Newton Rapshon

yang mendapat nama dari Isaac Newton (1669) dan Joseph Rapshon (1690), merupakan suatu metode yang cukup dikenal untuk mencari pendekatan terhadap akar fungsi riil. Metode Newton Rapshon sering konvergen dengan cepat, terutama bila dimulai cukup dekat dengan akar yang diinginkan. Namun, bila iterasi dimulai jauh dari akar yang dicari, metode ini dapat melesat tanpa peringatan.Implementasi metode ini biasanya mendeteksi dan mengatasi kegagalan konvergensi.


Gagasan awal metode Newton Rapshon adalah metode yang digunakan untuk mencari akar dari sebuah fungsi riil. Metode ini dimulai dengan memperkirakan satu titik awal dan mendekatinya dengan memperlihatkan slope atau gradient pada titik tersebut. Diharapkan dari titik awal tersebut akan diperoleh pendekatan terhadap akar fungsi yang dimaksud.

Diberikan fungsi푓 ∶ 푅 → 푅

∇ 푓(푥) definit positif untuk semua 푥, jadi 푓 juga konveks. Misal 푥 suatu vektor tertentu (merupakan estimasi untuk (푥∗). Untuk menemukan estimasi baru 푥 sebagai be-rikut. Perhatikan pendekatan kuadratis lewat ekspansi taylor dari fungsi 푓di titik 푥 . 푃(푥) = 푓(푥 ) + (푥 − 푥 ).∇푓(푥 ) + 1/2∇ 푓(푥 )(푥 − 푥 ) 푃(푥 ) = 푓(푥 ) ∇푃(푥) = ∇푓(푥 ) + ∇ 푓(푥 )(푥 − 푥 ) ∇푃(푥 ) = ∇푓(푥 ) ∇ 푃(푥 ) = ∇ 푓(푥 ) Sehingga∇ 푃(푥) definit positif dan푃(푥) adalah konveks. Estimasi baru untuk 푥∗ dapat dengan mencari minimum dari푝(푥), diperoleh

푥 = 푥 − [∇ 푓(푥 )] .∇푓(푥 ).

Algoritma Input 푓 ∶ 푅 → 푅:, ∇푓,∇ 푓 , (definit positif), estimasi awal 푥 ∈ 푅 , toleransi (훼), 푘 = 0. Step: 1. 푥 = 푥 − [∇ 푓(푥 )] .∇푓(푥 )

2. jika‖∇푓(푥 )‖ < 훼 , STOP. 푥∗ = 푥 3. 푘 = 푘 + 1, ulangi step 1.

Contoh Kasus (1) Diketahui: 퐴 = 1 1

1 2 , 푏 = −1−1 , 푐 = 0, 푥 =

푥푥 . Carilah minimum dari fungsi kuadratik 푓(푥)

yang diperoleh dari matriks 퐴,푏,푥푑푎푛푘표푛푠푡푎푛푡푎0di atas, dengan toleransi 훼 = 0.01 dan imulai dari titik awal 푥 = 0

0 . Penyelesaian: 푓(푥 ,푥 ) =

12푥 퐴푥 + 푏 푥 + 푐

=12푥 + 푥 + 푥 푥 − 푥 − 푥

Dengan gambar sbagai berikut.

Gradien dari 푓

∇푓(푥) = 퐴푥 + 푏 = = 푥 + 푥 − 1푥 + 2푥 − 1 .

Diperoleh


∇푓(푥 ) = 0 + 0− 10 + 0− 1 = −1

−1

∇ 푓(푥) =

⎣⎢⎢⎢⎡ 휕 푓휕푥

휕 푓휕푥 푥

휕 푓휕푥 푥

휕 푓휕푥 푥 ⎦

⎥⎥⎥⎤

= 1 11 2

∇ 푓(푥 ) = 1 11 2

∇ 푓(푥) = 퐴 = 1 11 2 ,∆ = 1 > 0,∆ = 1 > 0

Jadi∇ 푓 definit positif.

Iterasi 1: 푘 = 0 푥 = 푥 − [∇ 푓(푥 )] .∇푓(푥 ) = 0

0 − 2 −1−1 1 . −1

−1 = 10

∇푓(푥 ) = 푥 + 푥 − 1푥 + 2푥 − 1 = 1 + 0 − 1

1 + 0 − 1 = 00 ,

‖∇푓(푥 )‖ = √0 + 0 = 0 < 훼 = 0.01. Iterasi berhenti, dan

푥∗ = 푥 = 10 .

(2) Diberikan suatu fungsi 푓(푥 , 푥 ) = 푥 + 푥 + 2푥 + 4푥 + 6, 훼 = 0.01 dan nilai awal 푥 = 0

0 . Penyelesaian:

Gradien dari푓

∇푓(푥) = 퐴푥 + 푏 = 휕푓/휕푥휕푓/휕푥 = 3푥 + 4푥

3푥 + 8푥.

Diperoleh ∇푓(푥 ) = 3.0 + 4.0

3.0 + 8.0 = 00

∇ 푓(푥) =

⎣⎢⎢⎢⎡ 휕 푓휕푥

휕 푓휕푥 푥

휕 푓휕푥 푥

휕 푓휕푥 ⎦

⎥⎥⎥⎤

= 6푥 + 4 00 6푥 + 8

∇ 푓(푥 ) = 6.0 + 4 00 6.2 + 8 = 4 0

0 8

∇ 푓(푥) = 퐴 = 4 00 8 ,∆ = 4 > 0,∆ = 32 > 0.

Jadi ∇ 푓 definit positif.


Iterasi 1: 푘 = 0

푥 = 푥 − [훻 푓(푥 )] .훻푓(푥 ) = 0

0 − 4 00 8 . 0

0

= 00 −

132

8 00 4 . 0

0

= 00 −

14 0

018

. 00

= 00 − 0

0 = 00

훻푓(푥 ) = 3푥 + 4푥3푥 + 8푥

,

훻푓(푥 ) = 훻푓 00 = 3.0 + 4.0

3.0 + 8.0 = 00

‖훻푓(푥 )‖ = √0 +0 = 0 < 훼 = 0.01. Iterasi berhenti, dan 푥 ∗ = 푥 1 = 0

0 . (3) Diberikan suatu fungsi 푓(푥 ,푥 ) = 2푥 + 푥 + 2푥 푥 + 푥 − 푥 , 훼 = 0.01 dengan 푥 = 0

0 .

Penyelesaian: Gradien f

∇푓(푥) = 퐴푥 + 푏 =휕푓/휕푥휕푓/휕푥 = 4푥 + 2푥 + 1

2푥 + 2푥 − 1 Diperoleh

∇푓(푥 ) = 4.0 + 2.0 + 12.0 + 2.0− 1 = 1

−1

∇ 푓(푥) = 퐴 = = 4 22 2 ,∆ = 4 > 0,∆ = 4 > 0.

Jadi ∇ 푓 definit positif.

Iterasi 1: 푘 = 0 푥 = 푥 − [∇ 푓(푥 )] .∇푓(푥 ) = 0

0 − 4 22 2 . 1

−1

= 00 − 2 −2

−2 41−1

= 00 −

12 −

12

−12 1

1−1

= 00 − 1

−3/2 = −13/2

∇푓(푥 ) = 4(−1) + 2(3/2) + 12(−1) + 2(3/2) − 1 = 0

0 , ‖∇푓(푥 )‖ = 0 < 훼 = 0.01. Iterasi berhenti, dan 푥∗ = 푥 = −1

3/2 .


3. Penutup

Kesimpulan yang bisa diambil dari pembahasan adalah : Algoritma atau langkah dari metode Newton adalah 푓 ∶ 푅 → 푅, ∇푓, ∇ 푓, (definit positif), estimasi awal 푥 ∈ 푅 , dengan toleransi (훼), 푘 = 0. Step: 1. 푥 = 푥 − [∇ 푓(푥 )] .∇푓(푥 )

2. jika‖∇푓(푥 )‖ < 훼 , STOP. 푥∗ = 푥 3. 푘 = 푘 + 1, ulangi step

Dari kasus 1, diperoleh f minimum dengan x*= 10 , kasus 2 diperoleh f minimum dengan

x* = 00 dan kasus 3 diperoleh x* = −1

1.5 .

4. DAFTARPUSTAKA Indriati, Diari. (2008). Program Tak Linear, Surakarta. Luknanto, Djoko. (2000). PengantarOptimasi Non Linear, Yogjakarta.

kelompok 5 metode newton multi variabel 2013

Documents