¿Qué significa convergencia de primer y segundo orden [con ecuaciones mínimas] para los métodos de optimización?

Question

Se puede demostrar que el método de Newton tiene convergencia de segundo orden siempre que se satisfagan algunos criterios, y el descenso de gradiente tiene convergencia de primer orden, pero ¿qué significa aquí orden de convergencia?

En métodos numéricos como los esquemas de diferencias finitas, orden de precisión, por ejemplo, precisión de 2º orden: $O(\Delta x^2)$ significa que si se reduce el tamaño del paso a la mitad, por ejemplo, el error se reduce en un factor de 4. ¿Existe un análogo para el orden de convergencia?

Estoy un poco confundido por las diferentes representaciones que he visto para el orden de convergencia. Creo que mi interpretación general es que un método convergente de segundo orden será tal que cada iteración posterior dará lugar a una reducción de un factor de 2 en el error entre el óptimo y la ubicación actual. Así que creo que esto también significa que si se tarda $N$ iteraciones para que un método de primer orden converja a un valor determinado, entonces tardará $\log(N)$ iteraciones para que un método de segundo orden converja al mismo valor? ¿Son correctas estas interpretaciones?

Espero una mínima intuición matemática.

Answer 1

En resumen, se dice que un método iterativo que calcula una secuencia $\mathbf{x}_0, \mathbf{x}_1, \dotsc, \mathbf{x}_n, \dotsc$ que converge a $\mathbf{x}^*$ (posiblemente un vector) es de orden $p$ si los errores $\mathbf{e}_n = \mathbf{x}_n - \mathbf{x}^*$ satisfacer:

$\begin{align*} \lvert \mathbf{e}_{n + 1} \rvert &= c \lvert \mathbf{e}_n \rvert^p + o(\lvert \mathbf{e}_n \rvert^p) \end{align*}$

Es decir, el error de la siguiente estimación es aproximadamente $c \lvert \mathbf{e}_n \rvert^p$ . Más grande $p$ significa una convergencia más rápida. Si su $c$ es, digamos, $0.9$ y $p = 1$ el error se reduce una décima en cada iteración (un dígito más o menos), si $p = 2$ el error se eleva al cuadrado (el doble de cifras correctas en cada ronda). Pero hay que sopesarlo con la complejidad del método. Por ejemplo, en una dimensión método secante es orden $1.6$ aproximadamente, mientras que Método de Newton es de orden 2 (cuadrático). Pero la secante sólo calcula la función en cada vuelta, mientras que Newton calcula la función y su derivada. Suponiendo que el coste de calcular la derivada sea similar al coste de calcular la función, el método secante es más rápido (en tiempo, no en iteraciones).

Puede que quieras echar un vistazo a Brent's Algoritmos de minimización sin derivadas (Dover reedición 2013),