볼록 문제에 대한 알고리즘
가파른 하강 방법
이 방법은 Gradient 방법 또는 Cauchy의 방법이라고도합니다. 이 방법은 다음 용어를 포함합니다-
$$ 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 $를 미분하고 0과 같게하면 $ \ 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) 설정 \ 오른쪽 \ |} $.
$ \ alpha_k $를 찾아 $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $를 최소화합니다.
$ x_ {k + 1} = x_k + \ alpha_kd_k $를 설정합니다.
$ \ 왼쪽 \ | x_ {k + 1-x_k} \ 오른쪽 \ | <\ 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 \ 오른쪽) $
$ 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) h \ left (x_k \ right) = \ bigtriangledown f \ 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 $를 설정합니다.