Hay que empezar por entender que el análisis asintótico tradicional de la convergencia sublineal/lineal/superlineal/cuadrática de los algoritmos de optimización no es directamente comparable con el análisis no asintótico de los métodos de primer orden en términos del número de iteraciones necesarias para obtener una solución óptima epsilon (por ejemplo $O(1/\epsilon)$ ), o la reducción que puede obtenerse tras $k$ iteraciones (por ejemplo $O(1/k)$ .)
El análisis asintótico trata de lo que ocurre en el límite como $x^{(k)}$ se acerca a $x^{*}$ . El otro tipo de análisis se refiere a lo que ocurre después de un número relativamente pequeño de iteraciones, mucho antes de que el algoritmo haya mostrado su comportamiento límite.
Los métodos Quasi-Newton y Newton tienen tasas de convergencia asintótica que son al menos superlineales (cuadráticas para el método de Newton.) En la práctica, solemos ejecutar estos algoritmos hasta que han convergido a la máxima precisión disponible de la aritmética de punto flotante (normalmente de doble precisión) que se utiliza. Como resultado, solemos ver el comportamiento asintótico límite de estos métodos. Por ejemplo, en el método de Newton, es común ver que el número de dígitos precisos en la solución se duplica en cada una de las últimas iteraciones hasta que se alcanzan los límites de la aritmética de punto flotante. Cualquier algoritmo superlineal o cuadráticamente convergente que se acerque al comportamiento límite tendrá una solución totalmente precisa en unas pocas iteraciones.
En comparación, en el valiente nuevo mundo de los métodos de primer orden para problemas convexos a gran escala pero no suaves, rara vez podemos lograr más de 3-4 dígitos de precisión en la solución. Los algoritmos suelen detenerse mucho antes de la convergencia total. No nos interesa especialmente la tasa de convergencia asintótica (que suele ser sublineal) porque nunca nos acercaremos al comportamiento límite. Más bien nos interesa saber cuántas iteraciones son necesarias para encontrar una solución adecuada a nuestros propósitos.
En particular, definimos un $\epsilon$ solución aproximada para ser una solución $\hat{x}$ con $f(\hat{x})-f(x^{*}) \le \epsilon$ . Para un $\epsilon$ podemos analizar cuántas iteraciones son necesarias para obtener un $\epsilon$ solución aproximada y mostrar que (por ejemplo) nuestro algoritmo puede encontrar una $\epsilon$ solución aproximada en $O(1/\epsilon)$ iteraciones. Alternativamente, podríamos analizar nuestro algoritmo para mostrar que después de $k$ iteraciones, la diferencia $f(x^{(k)})-f(x^{*})$ es (por ejemplo) $O(1/k)$ . En este caso, la constante oculta por el $O()$ implicaría la distancia de $x^{(0)}$ a $x^{*}$ .
Es posible que dos métodos de primer orden tengan ambos una convergencia asintótica sublineal en el límite como $x^{(k)}$ se acerca a $x^{*}$ pero tienen $O(1/k)$ y $O(1/k^{2})$ la convergencia, respectivamente, medida por $f(x^{(k)})-f(x^{*})$ . Evidentemente, el $O(1/k^{2})$ aunque la convergencia asintótica es sublineal en ambos casos.
Un último comentario es que nada de esto se relaciona con la complejidad en tiempo polinómico de los métodos de punto interior para LP, SOCP y SDP. Esa es otra forma de analizar la convergencia de algunos algoritmos de optimización. Es importante desde el punto de vista de la práctica computacional en la resolución de problemas de optimización a muy gran escala que el tiempo polinómico a veces no es suficiente . En el caso de los problemas realmente grandes, es posible que ni siquiera se pueda completar una iteración en el tiempo disponible. Del mismo modo, un algoritmo de convergencia superlineal no sirve de mucho si no se puede ejecutar durante suficientes iteraciones para ver la convergencia superlineal asintótica.
Algunas lecturas adicionales:
Beck, Amir. First-Order Methods in Optimization. Filadelfia : SIAM-Sociedad de Matemática Industrial y Aplicada, 2017.
Bertsekas, Dimitri P. Algoritmos de optimización convexa. 1 edición. Belmont, Massachusetts: Athena Scientific, 2015.
Nesterov, Yurii. Lectures on Convex Optimization. 2nd ed. New York, NY: Springer, 2018.
