¿Por qué los problemas convexos son fáciles de optimizar?

Motivado por esta respuesta principal a la pregunta: ¿Por qué la convexidad es más importante que la cuasi convexidad en la optimización? , Ahora espero entender por qué los problemas convexos son fáciles de optimizar (o al menos más fáciles que los problemas cuasiconvexos ).

¿Cuáles son algunos de los algoritmos más eficientes para la optimización convexa y por qué no se pueden usar de manera efectiva en problemas cuasiconvexos ?

optimization convex-optimization Amelio Vazquez-Reina
fuente

Una propiedad extremadamente agradable es que si dibuja una línea / plano / hiperplano tangente al gráfico de una función convexa, todo el gráfico se ubicará a un lado de la línea, lo que no funciona para las funciones cuasiconvexas.

Kirill

Respuestas:

La mayoría de los mejores métodos modernos para la optimización a gran escala implican hacer una aproximación cuadrática local a la función objetivo, avanzar hacia el punto crítico de esa aproximación y luego repetir. Esto incluye el método de Newton, L-BFGS, etc.

Una función solo puede ser localmente bien aproximada por un cuadrático con un mínimo si el hessiano en el punto actual es positivo definido. Si el hessiano es indefinido, entonces

La aproximación cuadrática local es una buena aproximación local a la función objetivo y, por lo tanto, es una superficie de silla de montar. Luego, el uso de esta aproximación cuadrática sugeriría moverse hacia un punto de silla de montar, que probablemente esté en la dirección incorrecta, o
La aproximación cuadrática local se ve obligada a tener un mínimo por construcción, en cuyo caso es probable que sea una mala aproximación a la función objetivo original.

(El mismo tipo de problemas surgen si el Hessian es negativo definido, en cuyo caso localmente parece un cuenco al revés)

Por lo tanto, estos métodos funcionarán mejor si el Hessian es positivo definido en todas partes, lo que es equivalente a la convexidad para funciones suaves.

Por supuesto, todos los buenos métodos modernos tienen salvaguardas para garantizar la convergencia al moverse a través de regiones donde el Hessian es indefinido: por ejemplo, búsqueda de línea, regiones de confianza, detención de una solución lineal cuando se encuentra una dirección de curvatura negativa, etc. Sin embargo, en En tales regiones indefinidas, la convergencia es generalmente mucho más lenta, ya que no se puede utilizar la información de curvatura completa sobre la función objetivo.

Nick Alger
fuente

Discrepar. Las regiones de confianza pueden manejar cuadráticas indefinidas. Incluso los métodos de búsqueda de línea pueden encontrar y hacer búsquedas de línea en direcciones de curvatura negativa. Por otro lado, si su algoritmo está desnudo, sin una región de confianza o una búsqueda de línea adecuada para protegerlo, entonces estaría en problemas. Pero también puede estar en problemas con tal imprudencia incluso con una función estrictamente convexa.

Mark L. Stone

@ MarkL.Stone Por supuesto, esto es cierto y debatí mencionarlo al escribir la publicación. Sin embargo, el punto es que sí, puede hacer que el método converja haciendo un manejo especial (como lo hacen todos los buenos códigos modernos), pero la convergencia es considerablemente más lenta. Por ejemplo, un método de región de confianza es equivalente al descenso de gradiente si la región de confianza es pequeña.

Nick Alger

Puede intentar aplicar un algoritmo de optimización convexo a un problema de optimización no convexo, e incluso podría converger a un mínimo local, pero al tener solo información local sobre la función, nunca podrá concluir que de hecho Encontré el mínimo global. La propiedad teórica más importante de los problemas de optimización convexa es que cualquier mínimo local (de hecho, cualquier punto estacionario) también es un mínimo global.

Los algoritmos para la optimización global de problemas no convexos deben tener algún tipo de información global (por ejemplo, continuidad de Lipschitz de la función) para demostrar que una solución es un mínimo global.

Para responder a su pregunta específica sobre por qué un algoritmo de optimización convexo podría fallar en un problema cuasi convexo, suponga que su algoritmo de optimización convexo se inicia en un "punto plano" en el gráfico de la función objetivo. No hay información local en el gradiente que le indique a dónde ir después. Para un problema convexo, simplemente puede detenerse, sabiendo que ya estaba en un punto mínimo local (y, por lo tanto, global).

Brian Borchers
fuente

No creo que esto responda la pregunta sobre convexidad versus cuasiconvexidad. Si el problema es simplemente evitar gradientes planos, se podría suponer que los métodos convexos eficientes funcionan igualmente bien para funciones estrictamente cuasiconvexas , lo cual no creo que sea el caso.

Amelio Vazquez-Reina

y = x^{3}

$y=x^{3}$

x = 0

$x=0$

x = 0

$x=0$

Hay un teorema estándar que dice que si se usa un método de descenso con una búsqueda de línea que satisfaga las condiciones de Armijo, entonces se obtiene la convergencia global a un mínimo local. (He omitido algunas hipótesis técnicas aquí.) Entonces, sí, podría lograr la convergencia global al mínimo para su clase de funciones cuasi convexas sin puntos críticos no óptimos. Véase, por ejemplo, el Teorema 3.2 en la segunda edición del texto de Nocedal y Wright.

Brian Borchers, el

Con respecto a "tan fácil de optimizar", debe ir más allá del tema de la convergencia global a un minimizador y considerar las tasas de convergencia. El análisis de muchos métodos para la optimización convexa (por ejemplo, la convergencia cuadrática del método de Newton o la convergencia rápida de algunos métodos recientes de primer orden acelerados para la optimización convexa) depende de la convexidad, por lo que estos métodos podrían fallar en su clase de funciones cuasiconvexas. Por ejemplo, una función cuasiconvexa podría tener un punto crítico único pero tener puntos donde el hessiano es singular, y esto podría romper el método de Newton.

Brian Borchers, el

También tenga en cuenta que es común que las personas que hablan de problemas de optimización convexa sean "fáciles de resolver", generalmente están hablando de algunas clases de problemas de optimización convexa (LP, Convex QP, SOCP, SDP, etc.) para los cuales el polinomio existen algoritmos de tiempo y eso se puede resolver fácilmente en la práctica. Los problemas más generales de optimización convexa pueden ser mucho más difíciles de resolver en la práctica.

Brian Borchers, el