El Trabajo Práctico consta de dos consignas. Para cada una, deberán entregar el código de una implementación en Python que la resuelva y un breve informe con los resultados y las conclusiones obtenidas.
Puede realizarse en grupos de $n$ personas, con $1\leq n\leq 3$.
Fecha de entrega: Domingo 12/05
Random restart es una técnica básica que usualmente se utiliza para intentar hallar el mínimo global, o por lo menos un buen mínimo local, de una función. Consiste en generar $k$ puntos al azar en el dominio de la función y aplicar a cada uno cierto método de optimización. Esto lleva a la obtención de supuestos minimizadores locales $\mathcal{A}=\{x_1, \dots, x_k\}$, de los cuales nos quedaremos con el que logre el menor valor de la función objetivo: $$x^\ast = \underset{x\in \mathcal{A}}{\mathrm{argmin}}\; f(x)$$
Dada la función de Langermann en $\mathbb{R}^2$: $$f(x) = \sum_{i=1}^5 c_i\exp\left(-\frac{1}{\pi} \sum_{j=1}^2(x_j-A_{ij})^2\right)\cos\left(\pi\sum_{j=1}^2(x_j-A_{ij})^2\right)$$ donde $c=(1,2,5,2,3)$ y: $$A = \begin{pmatrix} 3 & 5 \\ 5 & 2 \\ 2 & 1 \\ 1 & 4 \\ 7 & 9 \end{pmatrix}$$
Aplicar la técnica de Random restart con el método del gradiente con Armijo, con el método de gradientes conjugados y con el método de cuasi-Newton. Para cada uno de estos métodos, utilizar Sección Áurea para calcular la longitud del paso. Es decir, para cada uno de esos métodos, aplicar el siguiente procedimiento:
Para cada uno de los métodos, registrar el resultado y el tiempo que toma correr Random restart en una tabla. Observar cuál es el que obtuvo el mejor resultado y cuál es el que registró mejor tiempo.
Función de Langermann: ya está implementada en el archivo con funciones que está en la página de la materia. Sólo deben importarla desde dicho archivo.
Generación de puntos aleatorios: la función np.random.rand(n) genera un vector de longitud $n$ cuyas componentes se encuentran en el intervalo $[0,1)$. Aplicar las modificaciones necesarias para que las componentes de $p$ se encuentren en el intervalo $[-5,5)$
Registro de tiempo: para registrar el tiempo que toma correr Random restart se puede utilizar la función time de la librería homónima. El output viene dado en segundos.
from timeit import default_timer as time
inicio = time()
# parte del código a la que le queremos registrar el tiempo de cómputo
fin = time()
print(fin - inicio)
Realizar los siguientes perfiles de desempeño. En cada caso, calcular la eficiencia y la robustez de cada uno de los algoritmos y obtener algunas conclusiones sobre el desempeño de cada uno. Añadir en el informe los gráficos de ambos perfiles.
$S = \{\text{método del gradiente con Armijo, método de Newton-LM con Armijo, región de confianza, gradientes conjugados con Wolfe}\}$
$P = \text{funciones del archivo f_tp_1.py (los puntos iniciales para cada función están en el código)}$
$c = \text{tiempo de cómputo}$
$M = 10^{8}$
Consideraremos que un algoritmo no logra resolver cierto problema si alcanza el máximo de 1000 iteraciones o si el valor del minimizador obtenido es tal que $\lVert x^\ast \rVert > 10^{5}$.
Para todos los algoritmos debe usarse $k_{MAX}=1000$ y $\varepsilon = 10^{-5}$
Compararemos el desempeño de la región de confianza para distintos valores de $\Delta_0$ y $\eta$. De esta manera, cada algoritmo será el método de región de confianza con distintos valores de esos parámetros:
$$\begin{array}{rl}A_0\colon & \Delta_0 = 1, \; \eta=0.2 \\ A_1\colon & \Delta_0 = 1.55, \; \eta=0.3 \\ A_2\colon & \Delta_0 = 0.55, \; \eta=0.15 \\ A_3\colon & \Delta_0 = 2, \; \eta=0.01 \end{array}$$$S = \{A_1,\,A_2,\, A_3,\, A_4\}$
$P = \text{funciones del archivo f_tp_2.py (los puntos iniciales para cada función están en el código)}$
$c = \text{cantidad de iteraciones}$
$M = 10^8$
Consideraremos que un algoritmo no logra resolver cierto problema si alcanza el máximo de iteraciones. Para todos los algoritmos debe usarse $k_{MAX}=300$ y $\varepsilon = 10^{-7}$
Al momento de buscar un paso $t$ que cumpla con las condiciones de Wolfe, es importante que el gradiente de $f$ esté calculado con mucha precisión. Por eso es recomendable, en la función derivada_parcial, utilizar un valor de tolerancia no mayor a $10^8$. (Explicación más detallada, la próxima clase)
Otra posible solución es utilizar la función $\varphi$ y la función derivar (que implementamos hace tiempo para calcular la derivada de una función de una variable). En el método de Wolfe definimos $\varphi(t) = f(x+t*d)$, por ejemplo de la siguiente manera:
phi = lambda t: f(x+t*d)
y utilizamos las condiciones de Wolfe en términos de $\varphi$: $$\begin{array}{rl} \varphi(t) &\leq \varphi(0) + c_1t\varphi'(0) \\ \varphi'(t) &\geq c_2\varphi'(0)\end{array}$$ La próxima clase se explicarán algunas ventajas de utilizar $\varphi$
En el algoritmo de Cuasi-Newton se puede añadir la condición de parada $\lVert x^{k+1} - x^k\rVert > \varepsilon$. De esta manera evitamos tener las advertencias de división por cero. Sin embargo, en otras situaciones puede ocurrir que esa condición de parada provoque que el algoritmo termine cuando podría haber llegado a un mínimo, es decir, que el algoritmo termine demasiado pronto (por ejemplo, esto ocurre si se aplica Cuasi-newton sobre la función de Rosenbrock).
Recordar que los np.array son mutables, así que para copiarlos lo más seguro es utilizar el .copy(). Esto puede resultar útil, por ejemplo, si queremos guardar el valor de la iteración anterior. Supongamos que queremos almacenar el valor de x en y:
import numpy as np
# Forma correcta: a y le asignamos una copia de x. De esta manera, si modificamos x no cambia y
x = np.array([1,2])
y = x.copy() # Escribir esto es más seguro que escribir y = x
x = x + 2*np.array([1,1]) # Podemos modificar x tranquilamente, sabiendo qye el valor de y no se alterará
Cuidado al escribir las operaciones que involucren al operador @. Usar paréntesis para asegurarse de realizar las operaciones en orden. Por ejemplo, si se desea calcular $d^TAd$:
# Forma correcta:
d@(A@d) # o d.T@(A@d)
# Forma poco segura y posiblemente incorrecta:
d@A@d
En el método de Cuasi-Newton, prestar atención a los productos externos.