Introducción

Uno de los métodos de descenso más anunciados es el método de gradiente más simple . Se proponen resultados muy importantes para el análisis de la búsqueda de líneas exactas a lo largo de cada dirección de descenso a pensar de que convergen lentamente. Existen métodos que no son monótonos por que lo que se dificulta la generalización para funciones no lineales . En este apartado se encuentran fórmulas de tamaño por pasos que permiten una rápida convergencia y poseen propiedad monótona. Para la resolución se porponen tamaño de pasos de \(\alpha_{k}\) para el método de descenso más pronunciado , además se presentan resultados numéricos que nos ayudaa encontrar la solución dentro de 3 iteraciones. De la misma manera presentamos la versión modificada del método el cuál es comparable con el método de Barzilar-Borwein .

El método de descenso más pronunciado es el método de gradiente más simple para la optimización sin restricciones de \(\text{min}f(x)\) , dónde \(f(x)\) es una función continua diferenciable . El método tiene la forma \(x_{k+1}=x_{k}+ \alpha_{k}(-g_{k})\) , dónde \(g_{k}=\nabla f(x_{x})\) es el gradiente del vector de \(f(x)\) en el punto de iteración actual \(x_{k}\) y dónde \(\alpha_{k}>0\) es el tamaño por pasos .

El tamaño de \(\alpha_{k}\) se tiene por búsqueda lineal exacta así:

\[\alpha _{k}=\text{argmin}{f(x_{x}+\alpha (-g_{k}))}\] El método de descenso más pronunciado es siempre convergente , en otras palabras el método no terminará a menos que se encuentre un punto estacionario. No obstante , cuando la función objetivo \(f(x)=g^{T}x+\frac{1}{2}x^{T}Hx\) es cuadrática estrictamente convexa , el método de descenso más pronunciado puede no ser muy eficiente y aunque se puede mostrar que el método converge linealmente, la tasa de convergencia es lenta, especialmente cuando \(H\) es muy grande.

Un resultado fue dado por Barzilai y Borwein donde da fórmulas para el tamaño de \(\alpha _{k}\) que llevan a la covergencia superlineal, utilizando la información de la información anterior para decir el tamaño de la iteración actual. Esta iteración ; \[x_{k+1}=x_{k}-D_{kg_{k}}\] Dónde la matriz \(D\) cumple con algunas propiedades concluyendose que se obtiene dos medidas: \[\alpha_{k}=\frac{s_{k-1}^{T}y_{k-1}}{||y_{k-1}||_{2}^{2}}\] y\[\alpha_{k}=\frac{||s_{k-1}||_{2}^{2}}{s_{k-1}^{T}y_{k-1}}\]

El método BB funciona bastante bien para problemas de alta dimensión pero no es monótono por ende no se puede generalizar a funciones no lineales, por tanto es muy conveniente encontrar una fórmula de tamaño por pasos que permite una rápida convergencia y posea la propiedad monótona.

Gracias a los resultados de Forsythe, el comportamiento del método de descenso más pronunciado para problemas de dimensiones superiores es igual para problemas de dos dimensiones. Por tanto, obtenemos nuestra fórmula para \(\alpha_{k}\) basada en nuestro análisis en problemas de dos dimensiones.

En el siguiente apartado derivamos la nueva fórmula para \(\alpha_{k}\) y damos algunas condiciones equivalentes.

Un nuevo tamaño de paso

Tomamos como función objetivo la siguiente: \[f(x)=g^{T}X+x^{T}Hx\]

Lo que se quiere es encontrar el minimizador único de \(f(x)\) del método. Además asumiremos la búsqueda de línea exacta en la primera iteración, ya que no queremos descartar la solución cuando el algoritmo se encuentre en la primera iteración . Así se tiene el siguiente algoritmo:

\[x_{2}=x_{1}-\alpha_{1}^{*}g_{1}\] \[x_{3}=x_{2}-\alpha_{2}^{*}g_{2}\] \[x_{4}=x_{3}-\alpha_{3}^{*}g_{3}\] Dónde \(\alpha_{1}^{*}\) y \(\alpha_{3}^{*}\) se obtienen por búsqueda lineal exacta y \(x_{4}\) es el resultado. Necesitamos encontrar una fórmula para \(\alpha_{2}\) de tal forma que \(x_{4}\) sea el minimizador de la función objetivo. Para simplificar el análisis solo se estudiará el caso cuando \(g_{1}\) y \(g_{2}\) son los dos ejes y son ortogonales. Por lo tanto podemos expresar todos los vectores \(x\) por combinaciones lineales de \(g_{1}\) y \(g_{2}\) .Considerando la función.

\[f(x_{2}+t\frac{g_{1}}{||g_{1}||_{2}}+u\frac{g_{2}}{||g_{2}||_{2}})= \left(\begin{array}{c} 0\\ ||g_{2}||_{2} \end{array}\right)^{T} \left(\begin{array}{c} t\\ u \end{array}\right)\]

\[+\frac{1}{2}\left(\begin{array}{c} t\\ u \end{array}\right)^{T}\left(\begin{array}{cc} g_{1}^{T}Hg_{1}/||g_{1}||_{2}^{2}& g_{1}^{T}Hg_{2}/||g_{1}||_{2} ||g_{2}||_{2} \\ g_{1}^{T}Hg_{2}/||g_{1}||_{2} ||g_{2}||_{2} & g_{2}^{T}Hg_{2}/||g_{2}||_{2}^{2} \end{array}\right) \left(\begin{array}{c} t\\ u \end{array}\right) \] Debido a la búsqueda de línea exacta en la primera iteración vemos que el minimizador de la función objetivo debe ser: \[\left(\begin{array}{c} t^{*}\\ u^{*} \end{array}\right) =-\frac{||g_{1}||_{2}||g_{2}||_{2}}{||g_{1}||_{2}/\alpha_{2}^{*}-||g_{2}||_{2}/\alpha_{1}^{*}}\left(\begin{array}{c} ||g_{2}||_{2}\\ ||g_{1}||_{2} \end{array}\right)\]

así se tiene \[x_{4}=x_{2}+t^{*}g_{1}/||g_{2}||_{2}+u^{*}g_{2}/||g_{2}||_{2}\]

Se necesita la dirección de gradiente \(g_{3}\) paralela al vector residual \(x_{4}\)y \(x_{5}\) . Resolviendo el sistema se tiene \[1-\alpha_{2}(1/\alpha_{2}^{*}-||g_{2}||_{2}^{2}/\alpha_{1}^{*}||g_{1}||_{2}^{2})=\alpha_{1}^{*}/\alpha_{2}-\alpha_{1}^{*}/\alpha_{2}^{*}\] la solución \(\alpha_{2}\) se puede escribir de la siguiente manera: \[\alpha_{2}=\frac{2}{\sqrt{(1/\alpha_{1}^* -1/\alpha_{2}^*)^{2}+4\parallel g_{2} \parallel _{2}^{2}/\parallel s_{1}\parallel _{2}^{2} + 1/\alpha_{1}^*+1/\alpha_{2}^*}}\] dónde \(s_{1}=x_{2}-x_{1}=-\alpha_{1}^{*}g_{1}\) , por lo tanto, hemos encontrado la fórmula para \(\alpha_{2}\) que garantiza que el método encuentre la solución después de tres iteraciones.

Para funciones cuadráticas convexas en \((n>2)\) espacios dimensionales, en base a las ecuaciones planteadas anteriormente sugerimos el siguiente método.

Algoritmo 2.1

Algoritmo 2.2 (Versión modificada de nuestro nuevo método de descenso más pronunciado)

• 1. Dado un punto inicial \(x_1\), Calcular \(g_1\), dado \(k=1\).
• 2. Calcular la línea exacta de búsqueda del paso \(\alpha_{2k-1}^*\); dado: \[x_{2k}=x_{2k-1}-\alpha_{2k-1}^*g_{2k-1}\]
• 3. Si \(g_{2k-1}=0\) entonces para;
• 4. Definimos \(\bar{s}_{2k}=-\alpha_{2k-1}^* g_{2k}\). Calcular \(g(x_{2k}+\bar{s}_{2k})\) y dado \[\beta=\frac{g(x_{2k}+\bar{s}_{2k})^T g_2}{\parallel g_{2k} \parallel _2 ^2}\].

Calcular \[\alpha_{2k}=\frac{2}{\frac{1}{\alpha_{2k-1}^*}(2-\beta)+\sqrt{\frac{(\beta)^2}{(\alpha_{2k-1})^2}+4\frac{\parallel g_{2k} \parallel _2 ^2}{\parallel s_{2k-1} \parallel _2 ^2}}}\] y \[x_{2k+1} = x_{2k} - \alpha_{2k}g_{2k}\]. Si \(g_{2k+1}=0\) entonces para; - 5. \(k:=k+1\), ir a paso 2. El tamaño del paso \(\alpha_{2k}\) es el mismo en el paso 2 del alg. 2.1 si la función objetivo es cuadrática convexa. Para generalizar el funcionamiento en funciones no lineales se impone la siguiente condición de búsqueda: \[(1-\frac{\alpha_2k}{\alpha_{2k-1}^*})\frac{g(x_{2k}-\alpha_{2k}g_{2k})^T g_{2k}}{\parallel g_{2k}\parallel _{2}^2}=\frac{\parallel g_{2k}\parallel _{2}^2}{\parallel s_{2k-1}\parallel _{2}^2}\alpha_{2k}^2\], y \(g(x_{2k}-\alpha_{2k}g_{2k})^T g_{2k} >0\). Es fácil ver que tal \(\alpha_{2k}\) existe en un intervalo entre cero y el punto estacionario positivo más pequeño de \(f(x_{2k}-\alpha g_{2k})\).

Resultados Numéricos

Comparamos el rendimiento numérico de nuestro algoritmo con el método de Barzilar-Borwein (BB), el método de gradiente de tamaño de escalera alternativo (AS) de Dai y el método de minimización alternativo (AM) de Dai y Yuan. Se comparan dos versiones del método BB. El método de gradiente de tamaño de paso alternativo utiliza la búsqueda de línea exacta en iteraciones impares y el tamaño de paso BB (1.10) en iteraciones pares. El método de minimización alternativa realiza búsquedas de línea exactas en iteraciones impares y minimiza la norma del gradiente en iteraciones uniformes. Se debe saber que \[\alpha_k ^{AM}={\{}\begin{aligned} \frac{\parallel g_k \parallel _2^2}{g_k^T Hg_k}\quad k \quad es \quad impar,\\ \frac{g_k^T Hg_k}{g_k^T H^2g_k}\quad k \quad es \quad par,\end{aligned}\]

Para nuestro nuevo método, también implementamos dos versiones. La versión A es la versión no modificada del algoritmo 2.1. Mientras que la versión B usa un tamaño de paso \(\alpha_{2k}\) después de cada dos búsquedas de línea exactas. El algoritmo modificado eligió los tamaños de paso de tal forma que

\[\alpha_{3k-2}=\alpha_{3k-2}^*\] \[\alpha_{3k-1}=\alpha_{3k-1}^*\] \[\alpha_{3k}=\frac{2}{\sqrt{(1/\alpha_{3k-1}^*-1/\alpha_{3k}^*)^2+4\parallel g_{3k}\parallel _2^2/\parallel s_{3k-1}\parallel _2^2}+1/\alpha{3k-1}^*+1/\alpha_{3k}^*}\] El problema que usamos para comparar los algoritmos es el siguiente \[f(x)=(x-x^*)^T Diag(\sigma_1,...,\sigma_n) (x-x^) \hspace{1 cm} x \in \mathbb{R}^n\] Consideramos los casos en los que \(n = 2, 3, 10, 100, 1000, 10000\). El vector de solución \(x_i^* (i = 1, ..., n)\) \(\in\) \((−5, 5)\) se genera aleatoriamente. Dejamos que \(\sigma_1 = 1\) y \(\sigma_n = Cond (= 10, 100, 1000, 10000)\) que es el número de condición de la Heissiana de la función \(f(x)\). \(\sigma_i (i = 2,..., n-1)\) se eligen aleatoriamente en el intervalo \((1, \sigma_n)\). Para todos los problemas, el punto inicial es el vector cero \((0,..., 0)^T\) y la condición de parada es \(||gk|| \leq 10^{−8}\).

Los resultados numéricos expuestos para cada uno de los casos vienen dados en la siguiente tabla:

Tabla 1

Los resultados numéricos confirmaron que el nuevo tamaño de la escalera asegura que la solución se encuentre dentro de 3 iteraciones. Los resultados también mostraron que el nuevo método es muy eficiente para problemas de pequeña escala. Para problemas a gran escala, el nuevo método también es tan eficiente como los métodos BB si el número de condición de la arpillera de la función objetivo no es grande. Si el número de condición del Hessiano de la función objetivo es muy grande, especialmente para problemas a gran escala, el nuevo método es mucho peor que el método BB. La versión modificada de nuestro algoritmo funcionó bastante bien. Es comparable al método BB para problemas a gran escala y mejor para problemas a pequeña escala. Tenga en cuenta que ambas versiones de nuestro nuevo método tienen la propiedad monótona que el método BB no tiene.

Discusión

En este documento, hemos sugerido un nuevo tamaño de paso para el método de descenso más profundo. Se propone un algoritmo con este nuevo tamaño de paso en iteraciones uniformes y búsqueda lineal exacta en iteraciones impares. La mejora de la versión modificada de nuestro nuevo método sobre la versión no modificada es inesperada. Podría interesarle investigar otras posibilidades, como tomar un paso \(\alpha_{2k}\) (similar al algoritmo 2.1) después de cada \(m\) iteración de búsqueda de línea exacta. Otra posibilidad es sugerir una fórmula de tamaño de paso para \(\alpha_k\) que depende de los dos pasos de búsqueda lineal exactos \(\alpha_{k-1}^*\) y \(\alpha_{k-2}^*\)

Conclusiones

El objetivo del método del descenso y del descenso más profundo es minimizar una función \(f(x)\) tal que \(x\in \mathbb{R^n}\), así se fija \(x_{k+1}=x_k+\alpha(-g_k)\) con inicio en \(k:=k+1\)

• Los dos métodos paran cuando el gradiente de la función es cero, a diferencia del método más profundo pues hace que la matriz \(D_k\) caracterizada por ser Quasi-Newton, es decir, que en cada iteración se mejora su inversa. Realizando \(O(n^2)\) operaciones.

• Pero una desventaja del método es la pérdida de convergencia cuadrática.

• Además se realiza una búsqueda lineal exacta en ambos métodos para tener soluciones de \(x_k\), donde primero se busca un \(\alpha_2\) como combinación lineal cuando \(g_1\)y \(g_2\) tienen gradientes ortogonales, y seescoge el más pequeño después de haber realizado 3 iteraciones, y así se propone un paso de longitud para el método dedescenso más pronunciado.