Algoritmos para resolver un problema convexo
AREAtutorial » Tutoriales de IngenierÃa » Algoritmos para resolver un problema convexo
Este método también se denomina método de gradiente o método de Cauchy. Este método incluye los siguientes términos:
$$ 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 $ 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 |
La solución óptima es $ hat {x} = x_ {k + 1} $.
El método de Newton funciona de acuerdo con 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) $
B $ 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 $
Entonces $ 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:
Paso 1 – Inicialice $ x_0, varepsilon $ y establezca $ k = 0 $.
Paso 2 – encuentra $ H \left (x_k \right) bigtriangledown f \left (x_k \right) $.
Paso 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) $.
Paso 4 – encuentra $ x_ {k + 1} = x_k-h \left (x_k \right) $.
Paso 5 – Si $ left | x_ {k + 1} -x_k right |
PASO 6 – Solución óptima: $ hat {x} = x_ {k + 1} $.
Este método se utiliza para resolver los siguientes tipos de problemas:
$ min f \left (x \right) = \frac {1} {2} x ^ T Qx-bx $
donde Q es una matriz nXn definida positiva y b es una 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 $.
🚫