Optimización convexa (7): método de Newton
La optimización convexa se estudia principalmente en el libro "Convex Optimization" (traducido por Stephen Boyd et al., Wang Shuning et al.) [1]. Durante el proceso de aprendizaje, a veces me confundía la comprensión de su contenido, por lo que también consultaba otros libros y materiales. El autor hizo todo lo posible para organizar esta parte del conocimiento de manera tan concisa y clara como esta serie de notas.
Utilice la expansión de Taylor de segundo orden de la función objetivo para aproximar la función objetivo y resuelva la dirección de búsqueda de optimización convexa resolviendo el valor mínimo de esta función cuadrática.
Esto revela desde otra perspectiva por qué el camino de Newton es una buena dirección de búsqueda.
No busqué el proceso de prueba aquí. Creo que es suficiente conocerlo, porque ayuda a comprender el método de descenso más pronunciado ("Optimización convexa (6) - Método de descenso más pronunciado").
En aplicaciones prácticas, el método de Newton suele requerir menos iteraciones que el método de descenso de gradiente.
2.2 ha demostrado desde una perspectiva que el camino de Newton es una buena dirección de búsqueda.
Preguntas y respuestas de Zhihu "¿Por qué el método de Newton requiere menos iteraciones que el método de descenso de gradiente para resolver problemas de optimización?" "[2] Este artículo también habla de algunos, entre los cuales la cita número uno es de Wiki. "Hablando geométricamente, el método de Newton consiste en utilizar una superficie cuadrática para ajustarse a la superficie local en su ubicación actual y descender el gradiente. El método consiste en utilizar "Por lo general, el ajuste de la superficie cuadrática será mejor que el plano, por lo que la ruta de descenso seleccionada por el método de Newton será más consistente con la ruta de descenso óptima real". Es más convincente. poder y generalidad.
La Figura 2 ilustra vívidamente la diferencia entre el método de Newton y el método de descenso de gradiente. El color rojo es la ruta de búsqueda del método de Newton y el color verde es la ruta de búsqueda del método de descenso de gradiente.
El método de Newton necesita calcular la matriz inversa de la matriz de Hesse de la función objetivo. La complejidad computacional es demasiado alta y la eficiencia del cálculo es muy baja, especialmente cuando la dimensión es grande. La idea central del algoritmo cuasi-Newton es reemplazar la matriz de Hesse inversa con una matriz aproximada.
[1], "Optimización convexa", Stephen Boyd et al., traducido por Wang Shuning et al.
[2], "En problemas de optimización, ¿por qué el método de Newton requiere ¿Más tiempo para resolver que el método de descenso de gradiente? ¿Menos iteraciones? 》
Optimización convexa (1) - Descripción general
Optimización convexa (2) - Conjunto convexo
Optimización convexa (3) - Función convexa
p >Optimización convexa (4) - Resolución de problemas
Optimización convexa (5) - Búsqueda en línea recta hacia atrás
Optimización convexa (6) - Método de descenso más pronunciado
p>
Optimización convexa (7) - Método de Newton
Optimización convexa (8) - Problema dual de Lagrange
2016-08-08 Primera versión