Этот метод также называется методом градиента или методом Коши. Этот метод включает в себя следующие термины —
Xк+1=xk+ alphakdk
dk=− bigtriangledownf left(xk right) или $ d_k = — \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $
Пусть phi left( alpha right)=f left(xk+ alphadk right)
Дифференцируя phi и приравнивая его к нулю, мы можем получить alpha.
Таким образом, алгоритм выглядит следующим образом —
-
Инициализируйте x0, varepsilon1, varepsilon2 и установите k=0.
-
Установите dk=− bigtriangledownf left(xk right) или dk=− frac bigtriangledownf left(xk right) left | bigtriangledownf left(xk right) right |.
-
найдите alphak таким образом, чтобы минимизировать phi left( alpha right)=f left(xk+ alphadk right).
-
Установите xk+1=xk+ alphakdk.
-
Если $ \ 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.
-
Оптимальным решением является hatx=xk+1.
Инициализируйте x0, varepsilon1, varepsilon2 и установите k=0.
Установите dk=− bigtriangledownf left(xk right) или dk=− frac bigtriangledownf left(xk right) left | bigtriangledownf left(xk right) right |.
найдите alphak таким образом, чтобы минимизировать phi left( alpha right)=f left(xk+ alphadk right).
Установите xk+1=xk+ alphakdk.
Если $ \ 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.
Оптимальным решением является hatx=xk+1.
Метод Ньютона
Метод Ньютона работает по следующему принципу —
f left(x right)=y left(x right)=f left(xk right)+ left(x−xk right)T bigtriangledownf left(xk right)+ frac12 left(x−xk right)TH left(xk right) left(x−xk right)
bigtriangledowny left(x right)= bigtriangledownf left(xk right)+H left(xk right) left(x−xk right)
При xk+1, bigtriangledowny left(xk+1 right)= bigtriangledownf left(xk right)+H left(xk right) left(xk+1−xk right)
Для xk+1 быть оптимальным решением bigtriangledowny left(xk+1 right)=0
Таким образом, xk+1=xk−H left(xk right)−1 bigtriangledownf left(xk right)
Здесь H left(xk right) должен быть неособым.
Следовательно, алгоритм выглядит следующим образом:
Шаг 1 — Инициализируйте x0, varepsilon и установите k=0.
Шаг 2 — найдите H left(xk right) bigtriangledownf left(xk right).
Шаг 3 — Решите для линейной системы H left(xk right)h left(xk right)= bigtriangledownf left(xk right) для h left(xk right).
Шаг 4 — найдите xk+1=xk−h left(xk right).
Шаг 5 — Если $ \ left \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon или \ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ | \ leq \ varepsilon ,затемперейдитекшагу6,впротивномслучаеустановите k = k + 1 $ и перейдите к шагу 2.
Шаг 6 — Оптимальным решением является hatx=xk+1.
Метод сопряженных градиентов
Этот метод используется для решения задач следующих типов —
minf left(x right)= frac12xTQx−bx
где Q — положительно определенная матрица nXn, а b — постоянная.
Учитывая x0, varepsilon, compute g0=Qx0−b
Установите d0=−g0 для k=0,1,2,...,
Установить alphak= fracgTkgkdTkQdk
Вычислить xk+1=xk+ alphakdk
Установите gk+1=gk+ alphakdk
Вычислить betak= fracgTkgkdTkQdk
Вычислить xk+1=xk+ alphakdk
Установите gk+1=xk+ alphakQdk
Вычислить betak= fracgTk+1gk+1gTkgk
Установите dk+1=−gk+1+ betakdk.