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

Question

El término "método de primer orden" se utiliza a menudo para categorizar un método de optimización numérica para, digamos, la minimización restringida, y de forma 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 está relacionado con la tasa de convergencia del método o con el hecho de utilizar explícitamente primeras (o segundas) derivadas de la función que se desea minimizar?

Más concretamente, Newton se considera un método de segundo orden. Utiliza las derivadas de segundo orden (Hessian) y tiene una tasa de convergencia cuadrática. Pero, ¿qué ocurre si, por ejemplo, la energía no es convexa? En este caso, hay que modificar el hessiano para que sea (simétrico) definido positivo. En tal caso, se utilizan las derivadas de segundo orden, pero no está claro cuál es exactamente la tasa de convergencia. Puede ser lineal dependiendo de la modificación real del hessiano. Entonces, ¿se trata de un método de segundo orden o de primer orden?

Answer 1

Diferencia entre algoritmo de primer y segundo orden:

Cualquier algoritmo que requiera al menos una primera derivada/gradiente es un algoritmo de primer orden. En el caso de un problema de optimización de suma finita, puede utilizar sólo el gradiente de una sola muestra, pero esto sigue siendo de primer orden porque se necesita al menos un gradiente.

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

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

Distinción importante:

Cuando un algoritmo utiliza un aproximado versión de la información de segundo orden (hessiana) para la optimización, se puede o no puede sea un algoritmo de segundo orden. Hago hincapié en esto porque, por ejemplo, se puede aproximar el hessiano por el producto exterior del gradiente $H = \nabla f(x) \nabla f(x)^T$ . En este caso sólo utilizando información de primer orden, por lo que se consideraría un algoritmo de primer orden. Por otro lado, si se aproxima el hessiano calculando sólo los elementos diagonales $\partial_i \partial_i f(x)$ se trataría de un algoritmo de segundo orden.

En pedir de un algoritmo puede considerarse el orden de error resultante de la aproximación de la derivada. Recordemos la definición de 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$ sólo en el $i^{th}$ coordinar y $0$ en otro sitio. Por lo tanto, si utiliza un $\epsilon$ aproximación para cada cálculo de la derivada, obtendrá una $\epsilon^2$ error inherente a su algoritmo de optimización.

Dado que está incluido en tu pregunta, me gustaría añadir que los algoritmos de primer orden no convergen necesariamente de forma lineal. El Descenso Gradiente Estocástico (SGD) converge sublinealmente y muchos algoritmos de segundo orden no convergen cuadráticamente.

Answer 2

"De 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 el método sólo utiliza derivadas de primer orden.

Answer 3

Que yo sepa, no existe un término exacto y preciso. Personalmente, me refiero a los métodos de primer orden como aquellos métodos que utilizan primeras derivadas y a los métodos de segundo orden como aquellos que utilizan información de segundas derivadas. También tiendo a considerar métodos de segundo orden a aquellos métodos que utilizan información de la derivada de segundo orden, pero no toda la derivada de segundo orden. Esto significa que algo como una aproximación de Gauss-Newton al hessiano de un problema de mínimos cuadrados se consideraría un método de segundo orden. Por ejemplo, si tenemos el problema $$ J(x) = \frac{1}{2}\|g(x)\|^2 $$ donde el hessiano exacto 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 Newton basado en la aproximación hessiana $$ H = g^\prime(x)^*g^\prime(x)\partial x $$ sea un método de segundo orden. Técnicamente, aquí sólo vemos derivadas de primer orden, pero para obtener esta expresión, necesitábamos información sobre cómo la derivada de segundo orden de $J$ se construye y no sólo $g$ . Además, bajo los supuestos adecuados, podemos obtener una convergencia superlineal con esta aproximación.

Dicho esto, no es correcto afirmar que necesitamos un hessiano que sea definido positivo en todas partes para obtener una convergencia cuadrática. Si satisfacemos las condiciones suficientes de segundo orden, sabemos que el hessiano será positivo definido cerca de la solución óptima, por lo que podemos obtener convergencia cuadrática localmente. En realidad, el método de Newton sólo está garantizado para 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 se aplica cuando estamos lejos de la solución. Una estrategia de globalización bien diseñada, como un método de región fiduciaria o de búsqueda lineal, debería garantizar la convergencia a un punto estacionario desde un punto de partida arbitrario, pero generalmente no dicen nada sobre la tasa de convergencia y no requieren que el hessiano sea definido positivo en todas partes.

Realmente, el juego consiste en confiar en la globalización para acercarnos a la solución óptima y luego dejar que el método de Newton tome el relevo y no interfiera con estos iterados. Dado que las condiciones de optimalidad de segundo orden nos dicen que cerca de la solución el hessiano será definido positivo, podemos confiar en nuestro análisis de la tasa de convergencia bajo este supuesto.