Algoritmos para problemas convexos

Método de descenso más empinado

Este método también se denomina método de gradiente o método de Cauchy. Este método implica las siguientes terminologías:

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

$ d_k = - \ bigtriangledown f \ left (x_k \ right) $ o $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $

Sea $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $

Al diferenciar $ \ phi $ y equipararlo a cero, podemos obtener $ \ alpha $.

Entonces, el algoritmo es el siguiente:

• Inicialice $ x_0 $, $ \ varepsilon_1 $, $ \ varepsilon_2 $ y establezca $ k = 0 $.

• Establecer $ d_k = - \ bigtriangledown f \ left (x_k \ right) $ o $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $.

• encuentra $ \ alpha_k $ de manera que minimice $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $.

• Establezca $ x_ {k + 1} = x_k + \ alpha_kd_k $.

• Si $ \ left \ | x_ {k + 1-x_k} \ right \ | <\ varepsilon_1 $ o $ \ left \ | \ bigtriangledown f \ left (x_ {k + 1} \ right) \ right \ | \ leq \ varepsilon_2 $, vaya al paso 6; de lo contrario, configure $ k = k + 1 $ y vaya al paso 2.

• La solución óptima es $ \ hat {x} = x_ {k + 1} $.

Método Newton

El método Newton funciona según el siguiente principio:

$ 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) $

En $ 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 que $ x_ {k + 1} $ sea la solución óptima $ \ bigtriangledown y \ left (x_k + 1 \ right) = 0 $

Por lo tanto, $ x_ {k + 1} = x_k-H \ left (x_k \ right) ^ {- 1} \ bigtriangledown f \ left (x_k \ right) $

Aquí $ H \ left (x_k \ right) $ no debería ser singular.

Por lo tanto, el algoritmo es el siguiente:

Step 1 - Inicialice $ x_0, \ varepsilon $ y establezca $ k = 0 $.

Step 2 - encuentra $ H \ left (x_k \ right) \ bigtriangledown f \ left (x_k \ right) $.

Step 3 - Resuelva para el sistema lineal $ H \ left (x_k \ right) h \ left (x_k \ right) = \ bigtriangledown f \ left (x_k \ right) $ para $ h \ left (x_k \ right) $.

Step 4 - encuentra $ x_ {k + 1} = x_k-h \ left (x_k \ right) $.

Step 5- Si $ \ left \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon $ o $ \ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ | \ leq \ varepsilon $ luego vaya al paso 6, de lo contrario configure $ k = k + 1 $ y vaya al paso 2.

Step 6 - La solución óptima es $ \ hat {x} = x_ {k + 1} $.

Método de gradiente conjugado

Este método se utiliza para resolver problemas de los siguientes tipos:

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

donde Q es una matriz nXn definida positiva y b es constante.

Dado $ x_0, \ varepsilon, $ compute $ g_0 = Qx_0-b $

Establezca $ d_0 = -g_0 $ para $ k = 0,1,2, ..., $

Establecer $ \ alpha_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Q d_k} $

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

Establecer $ g_ {k + 1} = g_k + \ alpha_kd_k $

Calcular $ \ beta_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Qd_k} $

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

Establecer $ g_ {k + 1} = x_k + \ alpha_kQd_k $

Calcular $ \ beta_k = \ frac {g_ {k + 1} ^ {T} g_ {k + 1}} {g_ {k} ^ {T} gk} $

Establezca $ d_ {k + 1} = - g_ {k + 1} + \ beta_kd_k $.