Algoritmos para problema convexo
Método de descida mais íngreme
Este método também é chamado de método do gradiente ou método de Cauchy. Este método envolve as seguintes terminologias -
$$ x_ {k + 1} = x_k + \ alpha_kd_k $$
$ d_k = - \ bigtriangledown f \ left (x_k \ right) $ ou $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $
Seja $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $
Diferenciando $ \ phi $ e igualando-o a zero, podemos obter $ \ alpha $.
Portanto, o algoritmo é o seguinte -
Inicialize $ x_0 $, $ \ varepsilon_1 $, $ \ varepsilon_2 $ e defina $ k = 0 $.
Defina $ d_k = - \ bigtriangledown f \ left (x_k \ right) $ ou $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $.
encontre $ \ alpha_k $ de forma que minimize $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $.
Defina $ x_ {k + 1} = x_k + \ alpha_kd_k $.
Se $ \ left \ | x_ {k + 1-x_k} \ right \ | <\ varejpsilon_1 $ ou $ \ left \ | \ bigtriangledown f \ left (x_ {k + 1} \ right) \ right \ | \ leq \ varepsilon_2 $, vá para a etapa 6, caso contrário, defina $ k = k + 1 $ e vá para a etapa 2.
A solução ótima é $ \ hat {x} = x_ {k + 1} $.
Método Newton
O Método de Newton trabalha com o seguinte princípio -
$ 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) $
Em $ 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) $
Para $ x_ {k + 1} $ ser a solução ótima $ \ bigtriangledown y \ left (x_k + 1 \ right) = 0 $
Assim, $ x_ {k + 1} = x_k-H \ left (x_k \ right) ^ {- 1} \ bigtriangledown f \ left (x_k \ right) $
Aqui $ H \ left (x_k \ right) $ deve ser não singular.
Portanto, o algoritmo funciona da seguinte forma -
Step 1 - Inicialize $ x_0, \ varepsilon $ e defina $ k = 0 $.
Step 2 - encontre $ H \ left (x_k \ right) \ bigtriangledown f \ left (x_k \ right) $.
Step 3 - Resolva para o sistema linear $ H \ left (x_k \ right) h \ left (x_k \ right) = \ bigtriangledown f \ left (x_k \ right) $ para $ h \ left (x_k \ right) $.
Step 4 - encontre $ x_ {k + 1} = x_k-h \ left (x_k \ right) $.
Step 5- Se $ \ left \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon $ ou $ \ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ | \ leq \ varepsilon $ então vá para a etapa 6, caso contrário, defina $ k = k + 1 $ e vá para a etapa 2.
Step 6 - A solução ótima é $ \ hat {x} = x_ {k + 1} $.
Método do gradiente conjugado
Este método é usado para resolver problemas dos seguintes tipos -
$ min f \ left (x \ right) = \ frac {1} {2} x ^ T Qx-bx $
onde Q é uma matriz nXn definida positiva e b é constante.
Dado $ x_0, \ varepsilon, $ compute $ g_0 = Qx_0-b $
Defina $ d_0 = -g_0 $ para $ k = 0,1,2, ..., $
Defina $ \ alpha_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Q d_k} $
Calcule $ x_ {k + 1} = x_k + \ alpha_kd_k $
Defina $ g_ {k + 1} = g_k + \ alpha_kd_k $
Calcule $ \ beta_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Qd_k} $
Calcule $ x_ {k + 1} = x_k + \ alpha_kd_k $
Defina $ g_ {k + 1} = x_k + \ alpha_kQd_k $
Calcule $ \ beta_k = \ frac {g_ {k + 1} ^ {T} g_ {k + 1}} {g_ {k} ^ {T} gk} $
Defina $ d_ {k + 1} = - g_ {k + 1} + \ beta_kd_k $.