Konveks Problemi İçin Algoritmalar
En Dik İniş Yöntemi
Bu yönteme Gradient yöntemi veya Cauchy yöntemi de denir. Bu yöntem aşağıdaki terminolojileri içerir -
$$ x_ {k + 1} = x_k + \ alpha_kd_k $$
$ d_k = - \ bigtriangledown f \ left (x_k \ right) $ veya $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ sağ)} {\ left \ | \ bigtriangledown f \ left (x_k \ sağ) \ sağ \ |} $
$ \ Phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $ olsun
$ \ Phi $ 'ı farklılaştırarak ve sıfıra eşitleyerek, $ \ alpha $ elde edebiliriz.
Bu nedenle algoritma aşağıdaki gibidir -
$ X_0 $, $ \ varepsilon_1 $, $ \ varepsilon_2 $ 'ı başlatın ve $ k = 0 $ ayarlayın.
$ D_k = - \ bigtriangledown f \ left (x_k \ right) $ veya $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ sağ \ |} $.
$ \ alpha_k $, $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $ 'ı en aza indirecek şekilde bulun.
$ X_ {k + 1} = x_k + \ alpha_kd_k $ olarak ayarlayın.
$ \ Left \ | x_ {k + 1-x_k} \ sağ \ | <\ varepsilon_1 $ veya $ \ left \ | \ bigtriangledown f \ left (x_ {k + 1} \ sağ) \ sağ \ | \ leq \ varepsilon_2 $, 6. adıma gidin, aksi takdirde $ k = k + 1 $ ayarlayın ve 2. adıma gidin.
En uygun çözüm $ \ hat {x} = x_ {k + 1} $ 'dır.
Newton Yöntemi
Newton Yöntemi aşağıdaki ilkeye göre çalışır -
$ f \ left (x \ sağ) = y \ left (x \ sağ) = f \ left (x_k \ sağ) + \ left (x-x_k \ sağ) ^ T \ bigtriangledown f \ left (x_k \ sağ) + \ frac {1} {2} \ left (x-x_k \ sağ) ^ TH \ left (x_k \ sağ) \ left (x-x_k \ sağ) $
$ \ bigtriangledown y \ left (x \ right) = \ bigtriangledown f \ left (x_k \ sağ) + H \ left (x_k \ sağ) \ left (x-x_k \ sağ) $
$ X_ {k + 1}, \ bigtriangledown y \ left (x_ {k + 1} \ right) = \ bigtriangledown f \ left (x_k \ right) + H \ left (x_k \ right) \ left (x_ {k +1} -x_k \ sağ) $
$ X_ {k + 1} $ 'ın optimum çözüm olması için $ \ bigtriangledown y \ left (x_k + 1 \ right) = 0 $
Böylece, $ x_ {k + 1} = x_k-H \ left (x_k \ right) ^ {- 1} \ bigtriangledown f \ left (x_k \ right) $
Burada $ H \ left (x_k \ right) $ tekil olmamalıdır.
Dolayısıyla algoritma aşağıdaki gibidir -
Step 1 - $ x_0, \ varepsilon $ 'ı başlatın ve $ k = 0 $ ayarlayın.
Step 2 - $ H \ left (x_k \ right) \ bigtriangledown f \ left (x_k \ right) $ 'ı bulun.
Step 3 $ H \ left (x_k \ right) h \ left (x_k \ right) = \ bigtriangledown f \ left (x_k \ right) $ için $ h \ left (x_k \ right) $ doğrusal sistemi için çözün.
Step 4 - $ x_ {k + 1} = x_k-h \ left (x_k \ right) $ 'ı bulun.
Step 5- $ \ left \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon $ veya $ \ left \ | \ bigtriangledown f \ left (x_k \ sağ) \ sağ \ | \ leq \ varepsilon $ sonra 6. adıma gidin, aksi takdirde $ k = k + 1 $ ayarlayın ve 2. adıma gidin.
Step 6 - En uygun çözüm $ \ hat {x} = x_ {k + 1} $ 'dır.
Eşlenik Gradyan Yöntemi
Bu yöntem, aşağıdaki türlerdeki sorunları çözmek için kullanılır -
$ min f \ left (x \ sağ) = \ frac {1} {2} x ^ T Qx-bx $
burada Q, pozitif tanımlı bir nXn matrisidir ve b sabittir.
$ X_0, \ varepsilon, $ compute $ g_0 = Qx_0-b $ verildiğinde
$ K = 0,1,2, ..., $ için $ d_0 = -g_0 $ ayarlayın
$ \ Alpha_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Q d_k} $ ayarla
$ X_ {k + 1} = x_k + \ alpha_kd_k $ hesaplayın
$ G_ {k + 1} = g_k + \ alpha_kd_k $ olarak ayarlayın
$ \ Beta_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Qd_k} $ hesaplayın
$ X_ {k + 1} = x_k + \ alpha_kd_k $ hesaplayın
$ G_ {k + 1} = x_k + \ alpha_kQd_k $ olarak ayarlayın
$ \ Beta_k = \ frac {g_ {k + 1} ^ {T} g_ {k + 1}} {g_ {k} ^ {T} gk} $ hesaplayın
$ D_ {k + 1} = - g_ {k + 1} + \ beta_kd_k $ olarak ayarlayın.