Algoritma untuk Masalah Cembung
Metode Penurunan Paling Curam
Metode ini juga disebut metode Gradien atau metode Cauchy. Metode ini melibatkan terminologi berikut -
$$ x_ {k + 1} = x_k + \ alpha_kd_k $$
$ d_k = - \ bigtriangledown f \ left (x_k \ right) $ atau $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $
Misalkan $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $
Dengan membedakan $ \ phi $ dan menyamakannya dengan nol, kita bisa mendapatkan $ \ alpha $.
Jadi algoritme berjalan sebagai berikut -
Inisialisasi $ x_0 $, $ \ varepsilon_1 $, $ \ varepsilon_2 $ dan setel $ k = 0 $.
Setel $ d_k = - \ bigtriangledown f \ left (x_k \ right) $ atau $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ kanan \ |} $.
temukan $ \ alpha_k $ sedemikian rupa sehingga meminimalkan $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $.
Setel $ x_ {k + 1} = x_k + \ alpha_kd_k $.
Jika $ \ meninggalkan \ | x_ {k + 1-x_k} \ kanan \ | <\ varepsilon_1 $ atau $ \ left \ | \ bigtriangledown f \ kiri (x_ {k + 1} \ kanan) \ kanan \ | \ leq \ varepsilon_2 $, lanjutkan ke langkah 6, jika tidak setel $ k = k + 1 $ dan lanjutkan ke langkah 2.
Solusi optimal adalah $ \ hat {x} = x_ {k + 1} $.
Metode Newton
Metode Newton bekerja berdasarkan prinsip berikut -
$ f \ kiri (x \ kanan) = y \ kiri (x \ kanan) = f \ kiri (x_k \ kanan) + \ kiri (x-x_k \ kanan) ^ T \ bigtriangledown f \ kiri (x_k \ kanan) + \ frac {1} {2} \ kiri (x-x_k \ kanan) ^ TH \ kiri (x_k \ kanan) \ kiri (x-x_k \ kanan) $
$ \ bigtriangledown y \ kiri (x \ kanan) = \ bigtriangledown f \ kiri (x_k \ kanan) + H \ kiri (x_k \ kanan) \ kiri (x-x_k \ kanan) $
Pada $ x_ {k + 1}, \ bigtriangledown y \ left (x_ {k + 1} \ right) = \ bigtriangledown f \ left (x_k \ right) + H \ left (x_k \ right) \ kiri (x_ {k +1} -x_k \ kanan) $
Untuk $ x_ {k + 1} $ menjadi solusi optimal $ \ bigtriangledown y \ kiri (x_k + 1 \ kanan) = 0 $
Jadi, $ x_ {k + 1} = x_k-H \ left (x_k \ right) ^ {- 1} \ bigtriangledown f \ left (x_k \ right) $
Di sini $ H \ left (x_k \ right) $ harus non-singular.
Karenanya algoritme berjalan sebagai berikut -
Step 1 - Inisialisasi $ x_0, \ varepsilon $ dan setel $ k = 0 $.
Step 2 - temukan $ H \ kiri (x_k \ kanan) \ bigtriangledown f \ left (x_k \ right) $.
Step 3 - Selesaikan sistem linier $ H \ left (x_k \ right) h \ left (x_k \ right) = \ bigtriangledown f \ left (x_k \ right) $ sebesar $ h \ left (x_k \ right) $.
Step 4 - temukan $ x_ {k + 1} = x_k-h \ kiri (x_k \ kanan) $.
Step 5- Jika $ \ meninggalkan \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon $ atau $ \ kiri \ | \ bigtriangledown f \ kiri (x_k \ kanan) \ kanan \ | \ leq \ varepsilon $ lalu lanjutkan ke langkah 6, jika tidak atur $ k = k + 1 $ dan lanjutkan ke langkah 2.
Step 6 - Solusi optimal adalah $ \ hat {x} = x_ {k + 1} $.
Metode Gradien Konjugasi
Metode ini digunakan untuk memecahkan masalah dari jenis berikut -
$ min f \ kiri (x \ kanan) = \ frac {1} {2} x ^ T Qx-bx $
dimana Q adalah matriks nXn pasti positif dan b konstan.
Diberikan $ x_0, \ varepsilon, $ menghitung $ g_0 = Qx_0-b $
Setel $ d_0 = -g_0 $ untuk $ k = 0,1,2, ..., $
Setel $ \ alpha_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Q d_k} $
Hitung $ x_ {k + 1} = x_k + \ alpha_kd_k $
Setel $ g_ {k + 1} = g_k + \ alpha_kd_k $
Hitung $ \ beta_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Qd_k} $
Hitung $ x_ {k + 1} = x_k + \ alpha_kd_k $
Setel $ g_ {k + 1} = x_k + \ alpha_kQd_k $
Hitung $ \ beta_k = \ frac {g_ {k + 1} ^ {T} g_ {k + 1}} {g_ {k} ^ {T} gk} $
Setel $ d_ {k + 1} = - g_ {k + 1} + \ beta_kd_k $.