凸問題のアルゴリズム

最急降下の方法

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

$$ 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} $です。

共役勾配法

この方法は、次のタイプの問題を解決するために使用されます-

$ min f \ left(x \ right)= \ frac {1} {2} x ^ T Qx-bx $

ここで、Qは正定値のnXn行列で、bは定数です。

$ x_0、\ varepsilon、$が与えられると、$ g_0 = Qx_0-b $を計算します

$ k = 0,1,2、...、$に$ d_0 = -g_0 $を設定します

$ \ alpha_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Q d_k} $を設定します

$ x_ {k + 1} = x_k + \ alpha_kd_k $を計算します

$ g_ {k + 1} = g_k + \ alpha_kd_k $を設定します

$ \ beta_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Qd_k} $を計算します

$ x_ {k + 1} = x_k + \ alpha_kd_k $を計算します

$ g_ {k + 1} = x_k + \ alpha_kQd_k $を設定します

$ \ beta_k = \ frac {g_ {k + 1} ^ {T} g_ {k + 1}} {g_ {k} ^ {T} gk} $を計算します

$ d_ {k + 1} = -g_ {k + 1} + \ beta_kd_k $を設定します。