凸問題のアルゴリズム

最急降下の方法

この方法は、勾配法またはコーシー法とも呼ばれます。この方法には、次の用語が含まれます-

$$ x_ {k + 1} = x_k + \ alpha_kd_k $$

$ d_k =-\ bigtriangledown f \ left（x_k \ right）$または$ d_k =-\ frac {\ bigtriangledown f \ left（x_k \ right）} {\ left \ | \ bigtriangledown f \ left（x_k \ right）\ right \ |} $

$ \ phi \ left（\ alpha \ right）= f \ left（x_k + \ alpha d_k \ right）$とします。

$ \ phi $を微分してゼロに等しくすることにより、$ \ alpha $を取得できます。

したがって、アルゴリズムは次のようになります-

$ x_0 $、$ \ varepsilon_1 $、$ \ varepsilon_2 $を初期化し、$ k = 0 $に設定します。
$ d_k =-\ bigtriangledown f \ left（x_k \ right）$または$ d_k =-\ frac {\ bigtriangledown f \ left（x_k \ right）} {\ left \ | \ bigtriangledown f \ left（x_k \ right）を設定します\ right \ |} $。
$ \ phi \ left（\ alpha \ right）= f \ left（x_k + \ alpha d_k \ right）$を最小化するように$ \ alpha_k $を見つけます。
$ x_ {k + 1} = x_k + \ alpha_kd_k $を設定します。
$ \ left \ |の場合 x_ {k + 1-x_k} \ right \ | <\ varepsilon_1 $または$ \ left \ | \ bigtriangledown f \ left（x_ {k + 1} \ right）\ right \ | \ leq \ varepsilon_2 $、ステップ6に進みます。それ以外の場合は、$ k = k + 1 $を設定して、ステップ2に進みます。
最適なソリューションは$ \ hat {x} = x_ {k + 1} $です。

ニュートン法

ニュートン法は次の原理で機能します-

$ f \ left（x \ right）= y \ left（x \ right）= f \ left（x_k \ right）+ \ left（x-x_k \ right）^ T \ bigtriangledown f \ left（x_k \ right）+ \ frac {1} {2} \ left（x-x_k \ right）^ TH \ left（x_k \ right）\ left（x-x_k \ right）$

$ \ bigtriangledown y \ left（x \ right）= \ bigtriangledown f \ left（x_k \ right）+ H \ left（x_k \ right）\ left（x-x_k \ right）$

$ 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 \ right）$

$ x_ {k + 1} $が最適解であるために$ \ bigtriangledown y \ left（x_k + 1 \ right）= 0 $

したがって、$ x_ {k + 1} = x_k-H \ left（x_k \ right）^ {-1} \ bigtriangledown f \ left（x_k \ right）$

ここで、$ H \ left（x_k \ right）$は特異ではないはずです。

したがって、アルゴリズムは次のようになります-

Step 1 − $ x_0、\ varepsilon $を初期化し、$ k = 0 $を設定します。

Step 2 − $ H \ left（x_k \ right）\ bigtriangledown f \ left（x_k \ right）$を見つけます。

Step 3 −線形システム$ H \ left（x_k \ right）h \ left（x_k \ right）= \ bigtriangledown f \ left（x_k \ right）$を$ h \ left（x_k \ right）$について解きます。

Step 4 − $ x_ {k + 1} = x_k-h \ left（x_k \ right）$を見つけます。

Step 5− $ \ left \ |の場合 x_ {k + 1} -x_k \ right \ | <\ varepsilon $または$ \ left \ | \ bigtriangledown f \ left（x_k \ right）\ right \ | \ leq \ varepsilon $次にステップ6に進みます。それ以外の場合は、$ k = k + 1 $を設定して、ステップ2に進みます。

Step 6 −最適解は$ \ hat {x} = x_ {k + 1} $です。