¿Puede aplicarse el descenso de gradiente a funciones no convexas?

Question

Estoy aprendiendo sobre optimización y tengo problemas para entender la diferencia entre optimización convexa y no convexa. Según tengo entendido, una función convexa es aquella en la que "el segmento de línea entre dos puntos cualesquiera de la gráfica de la función está por encima o sobre la gráfica". En este caso, se podría utilizar un algoritmo de descenso de gradiente, porque hay un único mínimo y los gradientes siempre le llevará a ese mínimo.

Sin embargo, ¿qué ocurre con la función de esta figura?

Aquí, el segmento de línea azul cruza por debajo de la función roja. Sin embargo, la función sigue teniendo un único mínimo, por lo que el descenso gradiente seguiría llevándole a este mínimo.

Así que mis preguntas son:

1) ¿Es la función de esta figura convexa o no convexa?

2) Si no es convexa, ¿pueden aplicarse los métodos de optimización convexa (descenso del gradiente)?

Answer 1

La función que has representado no es convexa. Sin embargo, es cuasiconvexo .

El descenso gradiente es un método genérico de optimización continua, por lo que puede aplicarse, y se aplica muy comúnmente, a funciones no convexas. Con una función suave y un tamaño de paso razonablemente seleccionado, generará una secuencia de puntos $x_1, x_2, \ldots$ con valores estrictamente decrecientes $f(x_1) > f(x_2) > \ldots$ .

El descenso gradiente acabará convergiendo a un punto estacionario de la función, independientemente de la convexidad. Si la función es convexa, se tratará de un mínimo global, pero si no lo es, podría ser un mínimo local o incluso un punto de silla de montar.

Las funciones cuasiconvexas son un caso interesante. Cualquier mínimo local de una función cuasiconvexa es también un mínimo global, pero las funciones cuasiconvexas pueden tener también puntos estacionarios que no son mínimos locales (tomemos $f(x) = x^3$ por ejemplo). Así que es teóricamente posible que el descenso por gradiente se atasque en un punto estacionario y no progrese hacia un mínimo global. En tu ejemplo, si el hombro de la izquierda del gráfico se nivelara perfectamente, el descenso gradiente podría quedarse atascado allí. Sin embargo, variantes como el método de la bola pesada podrían "pasar" y alcanzar el mínimo global.

Answer 2

Paul ya ha mencionado un punto importante:

• si f es convexa no hay puntos de silla y todos los mínimos locales son también globales. Por tanto, se garantiza que GD (con un tamaño de paso adecuado) encuentra un minimizador global.

Lo que hace difícil la optimización no convexa es la presencia de puntos de silla y mínimos locales, donde el gradiente es (0,...,0) y que tienen un valor objetivo arbitrariamente malo.

Encontrar el minimizador global en un entorno de este tipo es generalmente NP-difícil y en su lugar uno se conforma con el objetivo de encontrar un minimizador local.

Sin embargo, tenga en cuenta que:

• La probabilidad de que GD se atasque en un sillín es en realidad 0 ( ver aquí ).
• Sin embargo, la presencia de puntos de inflexión puede ralentizar mucho el avance de los DG, ya que las direcciones de baja curvatura se explotan con demasiada lentitud ( ver aquí )

Dependiendo de la dimensionalidad del problema, puede ser aconsejable utilizar una rutina de optimización de segundo orden.