¿Cuál es la definición de un método de primer orden?

Question

El término "método de primer orden" se usa frecuentemente para categorizar un método de optimización numérica, por ejemplo para minimización restringida, y de manera similar para un "método de segundo orden".

Me pregunto cuál es la definición exacta de un método de primer (o segundo) orden.

¿Este término se refiere a la tasa de convergencia del método o al hecho de que se utilizan explícitamente las primeras (o segundas) derivadas de la función a minimizar?

Más particularmente, Newton es considerado un método de segundo orden. Utiliza las segundas derivadas (la Hessiana) y tiene una tasa de convergencia cuadrática. Pero ¿qué pasa si por ejemplo la energía no es convexa? En este caso, la Hessiana debe ser modificada para ser (simétricamente) definida positiva. En tal caso, se utilizan las segundas derivadas pero no está claro cuál es exactamente la tasa de convergencia. Puede ser lineal dependiendo de la modificación real de la Hessiana. Así que, ¿es ese un método de segundo orden o de primer orden?

Answer 1

Diferencia entre el algoritmo de 1er y 2do orden:

Cualquier algoritmo que requiere al menos una primera derivada/gradiante es un algoritmo de primer orden. En el caso de un problema de optimización de suma finita, puede usar solo el gradiente de una muestra, pero aún así es de primer orden porque necesita al menos un gradiente.

Un algoritmo de segundo orden es cualquier algoritmo que utilice alguna segunda derivada, en el caso escalar. Para elaborar, el paso de Newton requiere el uso del Hessiano que tiene segundas derivadas de orden i.e. $H_{i,j} = \partial_i \partial_j f(x)$.

En general, un algoritmo puede clasificarse como de optimización de orden $n^{th}$ si utiliza un tensor de rango $n$.

Diferenciación importante:

Cuando un algoritmo utiliza una versión aproximada de la información de segundo orden (Hessiano) para la optimización, puede o no ser un algoritmo de segundo orden. Estoy enfatizando esto porque, por ejemplo, puede aproximar el Hessiano por el producto externo del gradiente $H = \nabla f(x) \nabla f(x)^T$. En este caso, está usando únicamente información de primer orden, por lo que esto se consideraría un algoritmo de primer orden. Por otro lado, si está aproximando el Hessiano calculando solo los elementos diagonales $\partial_i \partial_i f(x)$, esto sería un algoritmo de segundo orden.

El orden de un algoritmo puede considerarse como el orden de error resultante de la aproximación de la derivada. Recuerde la definición de una derivada: $$\partial_i f(x) \approx \frac{f(x + \epsilon \Delta x_i) - f(x)}{\epsilon}$$

y la segunda derivada: $$\partial_{ij} f(x) \approx \frac{\partial_j f(x + \epsilon \Delta x_i) - \partial_j f(x)}{\epsilon},$$

donde $x_i$ es igual a $x$ solo en la coordenada $i^{th}$ y $0$ en otros lugares. Por lo tanto, si utiliza una aproximación de $\epsilon$ para cada cálculo de derivada, obtendrá inherentemente un error de $\epsilon^2$ en su algoritmo de optimización.

Porque de alguna forma está incluido en su pregunta, me gustaría agregar que los algoritmos de primer orden no necesariamente convergen linealmente. El Descenso de Gradiente Estocástico (SGD) converge de forma sub-lineal y muchos algoritmos de segundo orden no convergen de forma cuadrática.

Answer 2

"Primer orden", en el término "método de primer orden", no se refiere a la tasa de convergencia del método. Se refiere al hecho de que solo se utilizan derivadas de primer orden en el método.

Answer 3

Por lo que sé, no existe un término exacto y preciso. Personalmente, me refiero a los métodos de primer orden como aquellos que utilizan primeras derivadas y métodos de segundo orden como aquellos que utilizan información de segundas derivadas. También tiendo a considerar como métodos de segundo orden aquellos que utilizan información de segundas derivadas, pero no la derivada de segundo orden completa. Esto significa que algo como una aproximación de Gauss-Newton a la Hessiana de un problema de mínimos cuadrados sería considerado un método de segundo orden. Por ejemplo, si tenemos el problema $$J(x) = \frac{1}{2}\|g(x)\|^2$$ donde la Hessiana exacta es: $$\nabla^2 J(x)\partial x= (g^{\prime\prime}(x)\partial x)^*g(x) + g^\prime(x)^*g^\prime(x)\partial x$$ Seguiría considerando un método de Newton basado en la aproximación de la Hessiana $$H = g^\prime(x)^*g^\prime(x)\partial x$$ como un método de segundo orden. Técnicamente, solo vemos primeras derivadas aquí, pero para obtener esta expresión, necesitamos información sobre cómo se construye la segunda derivada de $J$ y no solo de $g$. Además, bajo las correctas suposiciones, podemos obtener convergencia superlineal con esta aproximación.

Dicho esto, no es correcto decir que necesitamos una Hessiana que sea positiva definida en todas partes para obtener convergencia cuadrática. Si cumplimos con las condiciones suficientes de segundo orden, sabemos que la Hessiana será positiva definida cerca de la solución óptima, por lo que podemos obtener convergencia cuadrática localmente. Realmente, el método de Newton solo está garantizado a converger cuadráticamente dentro de un cierto radio, a menos que tengamos algo bueno como una función autoconcordante, por lo que el análisis de la tasa de convergencia generalmente no aplica cuando estamos lejos de la solución. Una estrategia de globalización bien diseñada, como un método de región de confianza o de búsqueda en línea, debería garantizar la convergencia a un punto estacionario desde un punto de inicio arbitrario, pero generalmente no dicen nada sobre la tasa de convergencia y no requieren que la Hessiana sea positiva definida en todas partes.

Realmente, el truco es depender de la globalización para acercarnos a la solución óptima y luego permitir que el método de Newton se haga cargo y no interferir con estas iteraciones. Dado que las condiciones de optimalidad de segundo orden nos dicen que cerca de la solución la Hessiana será positiva definida, entonces podemos depender de nuestro análisis de la tasa de convergencia bajo esta suposición.