Mínimo local. Optimización sin restricciones. Cálculo numérico.
Aproximar con una iteración el mínimo de la función $f\left(x,y\right)=x^{2}+3y^{2}$ comenzando por el punto inicial $(2,1)$ y utilizando
- El método del gradiente:
- Con el descenso más pronunciado.
- Con tasa de aprendizaje 0.1.
- El método de Newton.
- Utilizar el método de la sección áurea para optimizar el paso de la primera iteración del descenso más pronunciado.
El método del gradiente¶
Los métodos de gradiente son un conjunto de métodos que, como su nombre indica, se basan en el uso del gradiente de la función en cada punto.
Veamos un par de ejemplos
Descenso más pronunciado¶
Busquemos el mínimo de una función. Pensemos en una función de dos variables y por lo tanto estamos sobre una superficie
- Nos situamos en un punto inicial $(x_0,y_0).$
- Buscamos la dirección del gradiente.
- Nos orientamos en sentido contrario al gradiente, puesto que el gradiente se orienta en sentido creciente de la función, hacia arriba, y nosostros buscamos un mínimo y queremos ir hacia abajo.
- Avanzamos en línea recta. Tenemos que ir bajando.
- En el momento que encontremos el mínimo que está sobre nuestra trayectoria recta (cuando empezamos a subir otra vez), paramos. Estaremos en $(x_1,y_1).$
- Buscamos de nuevo la dirección del gradiente y repetimos los pasos anteriores hasta que se cumpla una condición de parada (por ejemplo, hacer $n$ iteraciones).
Este proceso está ilustrado en los gráficos siguientes
- En el primer gráfico vemos una superficie que tiene un mínimo en $(0,0).$ Es un paraboloide.
- En el el segundo gráfico vemos los gradientes en algunos puntos de la superficie. Podemos observar que para cada punto
- Se orientan en la dirección de máximo crecimiento de la función.
- Su módulo depende de cuánto crece la función. A mayor crecimiento mayor módulo.
- El tercer gráfico ilustra el método del Descenso Más Pronunciado empezando en el punto $(2,1).$
- El cuarto gráfico da la altura de la primera trayectoria recta en función de $h.$ Descendemos hasta que llegamos al punto rojo, que es el punto de mínima altura dentro de nuestra trayectoria.
Utilizando el método del gradiente, vamos a aproximar el mínimo de la función $f\left(x,y\right)=x^{2}+3y^{2}$ utilizando como punto inicial $(2,1).$
Realizaremos una iteración por el método del gradiente usando la fórmula
$$ \left(\begin{array}{c} x_{1}\\ y_{1} \end{array}\right)=\left(\begin{array}{c} x_{0}\\ y_{0} \end{array}\right)-h\nabla f\left(x_{0},y_{0}\right)\qquad (1) $$y buscaremos $h$ para que
$$ g(h)=f\left(x_{0}-h\,f_{x}(x_0,y_0),y_{0}-h\,f_{y}(x_0,y_0)\right) $$tenga un valor mínimo.
Tenemos que
$$ \nabla f=\left(f_{x},f_{y}\right)=\left(2x,6y\right) $$y sustituyendo el valor del punto inicial
$$ \nabla f\left(x_{0},y_{0}\right)=\nabla f\left(2,1\right)=\left(4,6\right). $$y sustituyendo el valor del punto inicial y del gradiente en el punto inicial en la función $g$
$$ g(h)=f\left(x_{0}-h\,f_{x}(x_0,y_0),y_{0}-h\,f_{y}(x_0,y_0)\right)=f\left(2-4h,1-6h\right)=\left(2-4h\right)^{2}+3\left(1-6h\right)^{2} $$Calculemos el mínimo de esta función teniendo en cuenta que la condición necesaria de mínimo es que $g'(h)=0$
$$ g'(h)=2(-4)\left(2-4h\right)+6(-6)\left(1-6h\right)=248h-52=0\Longrightarrow h=0.2097\approx 0.21 $$y usando este valor en la ecuación (1)
$$ \left(\begin{array}{c} x_{1}\\ y_{1} \end{array}\right)=\left(\begin{array}{c} 2\\ 1 \end{array}\right)-0.21\left(\begin{array}{c} 4\\ 6 \end{array}\right)=\left(\begin{array}{r} 1.16\\ -0.26 \end{array}\right) $$Hemos mejorado porque $f\left(x_{0},y_{0}\right)=f(2,1)=7$ y $f\left(x_{1},y_{1}\right)=f(1.16,-0.26)=1.55$ que es un valor menor.
La siguiente iteración se realizaría usando la fórmula
$$ \left(\begin{array}{c} x_{2}\\ y_{2} \end{array}\right)=\left(\begin{array}{c} x_{1}\\ y_{1} \end{array}\right)-h\nabla f\left(x_{1},y_{1}\right)\qquad (2) $$para lo cual habría que recalcular $h$ de forma análoga a la primera iteración, calculándola para que
$$ g(h)=f\left(x_{1}-h\,f_{x}(x_1,y_1),y_{1}-h\,f_{y}(x_1,y_1)\right) $$sea mínimo y sustituyendo entonces este $h$ en (2).
Con tasa de aprendizaje 0.1¶
En este caso no optimizamos el paso, es decir, no buscamos el punto mínimo de nuestra trayectoria recta, sino que usamos siempre el mismo $h$ y entonces a este parámetro se le llama $\eta$ o tasa de aprendizaje y hay que fijarlo. Si es demasiado pequeño, el algoritmo convergerá demasiado despacio y si es demasiado grande puede no converger.
Este método tiene la ventaja de su sencillez y el inconveniente de que hay que buscar un $\eta$ adecuado.
En cada paso usamos la fórmula
$$ \left(\begin{array}{c} x_{1}\\ y_{1} \end{array}\right)=\left(\begin{array}{c} x_{0}\\ y_{0} \end{array}\right)-\eta\nabla f_{\left(x_{0},y_{0}\right)} $$Como
$$ \nabla f=\left(f_{x},f_{y}\right)=\left(2x,6y\right) $$tenemos
$$ \left(\begin{array}{c} x_{1}\\ y_{1} \end{array}\right)=\left(\begin{array}{c} x_{0}\\ y_{0} \end{array}\right)-\eta \left(\begin{array}{c} 2x_{0}\\ 6y_{0} \end{array}\right) \quad \quad \left(\begin{array}{c} x_{1}\\ y_{1} \end{array}\right)=\left(\begin{array}{c} 2\\ 1 \end{array}\right)-0.1 \left(\begin{array}{c} 2(2)\\ 6(1) \end{array}\right)= \left(\begin{array}{c} 1.6\\ 0.4 \end{array}\right) $$$$ f(1.6,0.4)= 3.04 $$$$ \left(\begin{array}{c} x_{2}\\ y_{2} \end{array}\right)=\left(\begin{array}{c} x_{1}\\ y_{1} \end{array}\right)-\eta \left(\begin{array}{c} 2x_{1}\\ 6y_{1} \end{array}\right) \quad \quad \left(\begin{array}{c} x_{2}\\ y_{2} \end{array}\right)=\left(\begin{array}{c} 1.6\\ 0.4 \end{array}\right)-0.1 \left(\begin{array}{c} 2(1.6)\\ 6(0.4) \end{array}\right)= \left(\begin{array}{c} 1.28\\ 0.16 \end{array}\right) $$$$ f(1.28, 0.16)= 1.7152 $$$$ \left(\begin{array}{c} x_{3}\\ y_{3} \end{array}\right)=\left(\begin{array}{c} x_{2}\\ y_{2} \end{array}\right)-\eta \left(\begin{array}{c} 2x_{2}\\ 6y_{2} \end{array}\right) \quad \quad \left(\begin{array}{c} x_{3}\\ y_{3} \end{array}\right)=\left(\begin{array}{c} 1.28\\ 0.16 \end{array}\right)-0.1 \left(\begin{array}{c} 2(1.28)\\ 6(0.16) \end{array}\right)= \left(\begin{array}{c} 1.024\\ 0.064 \end{array}\right) $$$$ f(1.024, 0.064)= 1.060864 $$
El método de Newton¶
Introducción¶
Recordamos el método de Newton para encontrar una raíz de la ecuación no lineal $f(x)=0$. Partiendo de un valor inicial $x_0$, usando la fórmula
$$ x_{k+1} = x_k-\frac{f(x_k)}{f'(x_k)} $$y obtenemos
$$ x_{1} = x_0-\frac{f(x_0)}{f'(x_0)},\qquad x_{2} = x_1-\frac{f(x_1)}{f'(x_1)}, \qquad x_{3} = x_2-\frac{f(x_2)}{f'(x_2)},\quad \ldots \quad \rightarrow \quad \alpha $$Si quisieramos encontrar un máximo o un mínimo de la función $f$, si $f$ es suficientemente regular, la condición necesaria de extremo es
$$ f'(x)=0 $$Es decir, buscamos una raíz de esta ecuación y, usando Newton, podríamos resolverlo, tomando un valor inicial $x_0$, y usando la fórmula
$$ x_{k+1} = x_k-\frac{f'(x_k)}{f''(x_k)} $$De forma análoga, para funciones de $n$ variables $f:\Omega\subset \mathbb{R}^n\to \mathbb{R}$, teniendo en cuenta que las componentes del vector gradiente de una función $\nabla f(\mathbf{x})$ son sus derivadas parciales primeras, y las componentes de la matriz Hessiana $H(\mathbf{x})$ son las derivadas parciales segundas, podemos formular Newton partiendo de un valor inicial $\mathbf{x}_0$
$$ \mathbf{x}_{k+1} = \mathbf{x}_{k}-H^{-1}(\mathbf{x}_{k}) \cdot \nabla f(\mathbf{x}_{k}) $$Esto no es una demostración. Tanto en el caso unidimensional como en el multidimensional se puede construir el método de Newton a partir de la fórmula de Taylor correspondiente, y esa sería la demostración formal.
Como nuestra función es de dos variables, realizaremos una iteración por el método de Newton usando la fórmula
$$ \left(\begin{array}{c} x_{1}\\ y_{1} \end{array}\right)=\left(\begin{array}{c} x_{0}\\ y_{0} \end{array}\right)-H^{-1}\left(x_{0},y_{0}\right)\cdot\nabla f\left(x_{0},y_{0}\right) $$Si consideramos que
$$ H\left(x_{0},y_{0}\right)\left(\begin{array}{c} c_{1}\\ c_{2} \end{array}\right)=\nabla f\left(x_{0},y_{0}\right)\qquad (1) $$entonces
$$ \left(\begin{array}{c} c_{1}\\ c_{2} \end{array}\right)=H^{-1}\left(x_{0},y_{0}\right)\cdot\nabla f\left(x_{0},y_{0}\right) $$y escribiremos
$$ \left(\begin{array}{c} x_{1}\\ y_{1} \end{array}\right)=\left(\begin{array}{c} x_{0}\\ y_{0} \end{array}\right)-\left(\begin{array}{c} c_{1}\\ c_{2} \end{array}\right)\qquad (2) $$donde $\left(c_{1},c_{2}\right)^{T}$ es la solución del sistema (1). En general, tiene más sentido resolver el sistema (1) que calcular la matriz inversa de $H$ y luego multiplicarla por el gradiente, porque calcular la inversa de una matriz equivale a resolver $n$ sistemas (aunque con la misma matriz de coeficientes) y de esta forma estamos resolviendo solo un sistema.
Ejercicio¶
La función a minimizar es $f\left(x,y\right)=x^{2}+3y^{2}$ y empezaremos con el punto inicial $(2,1)$
Tenemos que
$$ \nabla f=\left(\frac{\partial f(x,y)}{\partial x},\frac{\partial f(x,y)}{\partial y}\right)=\left(2x,6y\right) $$y
$$ \nabla f\left(x_{0},y_{0}\right)=\nabla f\left(2,1\right)=\left(4,6\right). $$Además
$$ H=\left(\begin{array}{cc} \dfrac{\partial^{2}f(x,y)}{\partial x\,\partial x} & \dfrac{\partial^{2}f(x,y)}{\partial x\,\partial y}\\ \dfrac{\partial^{2}f(x,y)}{\partial y\,\partial x} & \dfrac{\partial^{2}f(x,y)}{\partial y\,\partial y} \end{array}\right)=\left(\begin{array}{cc} 2 & 0\\ 0 & 6 \end{array}\right) $$y
$$ H\left(x_{0},y_{0}\right)=H\left(2,1\right)=\left(\begin{array}{cc} 2 & 0\\ 0 & 6 \end{array}\right) $$El sistema (1) es
$$ \left(\begin{array}{cc} 2 & 0\\ 0 & 6 \end{array}\right)\left(\begin{array}{c} c_{1}\\ c_{2} \end{array}\right)=\left(\begin{array}{c} 4\\ 6 \end{array}\right) $$y resolviéndolo
$$ \left(\begin{array}{c} c_{1}\\ c_{2} \end{array}\right)=\left(\begin{array}{c} 2\\ 1 \end{array}\right). $$Por lo tanto (2) es
$$ \left(\begin{array}{c} x_{1}\\ y_{1} \end{array}\right)=\left(\begin{array}{c} 2\\ 1 \end{array}\right)-\left(\begin{array}{c} 2\\ 1 \end{array}\right)=\left(\begin{array}{c} 0\\ 0 \end{array}\right). $$Hemos mejorado porque $f\left(x_{0},y_{0}\right)=f(2,1)=7$ y $f\left(x_{1},y_{1}\right)=f(0,0)=0$ que es menor.
En este caso, hemos llegado al mínimo con una sola iteración.
El método de la sección áurea¶
Vamos a optimizar una función $g$ de una sola variable. El método de la sección áurea es un método de intervalo. Si la función alcanza un único mínimo en el intervalo, el método convergerá a dicho mínimo.
Si la función alcanza un único mínimo en $[a,b]$ y tenemos dos puntos interiores $x_1$ y $x_2$ de forma que $a \lt x_1 \lt x_2 \lt b$ teniendo en cuenta los valores de la función $g$ en $x_1$ y $x_2$, podemos descartar $[a,x_1)$ o $(x_2,b]$ manteniendo el mínimo dentro del intervalo.
Escogemos los puntos de forma que estén a una fracción $\phi$ y $1-\phi$ de uno de los extremos, con $\phi\in(0.5,1].$ Y con la condición de que, si descartamos $(x_2,b]$ el siguiente $x_2$ sea igual que el antiguo $x_1$. Y si descartamos $[a,x_1)$ el siguiente $x_1$ sea el antiguo $x_2.$ Así, en cada iteración, solo tendremos que evaluar la función en un nuevo punto.
Sin perder generalidad, podemos suponer que el intervalo inicial $[a,b]$ es $[0,1]$ y que en la primera iteración descartamos el intervalo de la derecha.
En la primera iteración, y teniendo en cuenta que $\phi\in(0.5,1]$, vemos la disposición de los puntos $a$, $x_1$, $x_2$ y $b$ y sus valores.
Si descartamos $(x_2,b]$, la nueva disposición de los puntos es la de la segunda iteración, donde los puntos $x_1$ y $x_2$ son $1-\phi$ y $\phi$ multiplicados por $\phi$ porque el intervalo ya no tiene longitud $1$ sino longitud $\phi.$
Para que se cumpla que el nuevo $x_2$ es igual al antiguo $x_1$ se tendrá que verificar que $$\phi^2=1-\phi\qquad\Longrightarrow \qquad \phi = \frac{\sqrt{5}-1}{2}\approx 0.618034$$
Algoritmo¶
- Sea $a_1=a$, $b_1=b$ y $\phi = \dfrac{\sqrt{5}-1}{2}$
- Para $k=1,2,\ldots,\mathrm{MaxNumIter}$
- Calcular los puntos
- $x_1=a_k+(1-\phi)(b_k-a_k)$
- $x_2=a_k+\phi(b_k-a_k)$
- si $g(x_1) \gt g(x_2)$ entonces:
$ a_{k+1}=x_1,$ $ b_{k+1}=b_k,$
- en otro caso:
$ a_{k+1}=a_{k},$ $ b_{k+1}=x_2.$
- Si se satisface el criterio de parada, parar.
La idea es que el mínimo siempre esté dentro del intervalo.
Vamos a aplicarlo a calcular el mínimo de la función
Iteración 1
- En la primera iteración calculamos $x_1$ y $x_2.$
- Como $g(x_1)\lt g(x_2)$ quiere decir que el mínimo está a la izquierda:
- Nos deshacemos del intervalo de la derecha.
- El $x_1$ se convierte en el nuevo $x_2.$
- Calculamos el nuevo $x_1.$
Iteración 2
- Como $g(x_1)\lt g(x_2)$ quiere decir que el mínimo está a la izquierda:
- Nos deshacemos del intervalo de la derecha.
- El $x_1$ se convierte en el nuevo $x_2.$
- Calculamos el nuevo $x_1.$
Iteración 3
- Como $g(x_1)\gt g(x_2)$ quiere decir que el mínimo está a la derecha:
- Nos deshacemos del intervalo de la izquierda.
- El $x_2$ se convierte en el nuevo $x_1.$
- Calculamos el nuevo $x_2.$
Y así sucesivamente.
De los dos últimos $x_1$ y $x_2$ tomaremos como aproximación aquel en el que la función tiene menor valor que es $$\fbox{0.2098}$$