¿Por qué la convexidad es más importante que la cuasi-convexidad en la optimización?

Question

En el optimización matemática En la literatura es habitual distinguir los problemas según sean o no convexos. La razón parece ser que los problemas convexos tienen garantizada la existencia de soluciones globales óptimas, por lo que se pueden utilizar métodos como el descenso de gradiente (steepest) para encontrar dichas soluciones, pero no me convence.

Por ejemplo, la función $|x|^{0.001}$ es no convexo (véase la zona sombreada en amarillo en la imagen de abajo) pero tiene un único minimizador global .

                     

¿Por qué es tan importante la convexidad en la optimización? ¿Por qué, por ejemplo, la cuasiconvexidad ¿a menudo no es suficiente?

Answer 1

Hay muchas razones por las que la convexidad es más importante que la cuasi-convexidad en la teoría de la optimización. Me gustaría mencionar una que las otras respuestas hasta ahora no han cubierto en detalle. Está relacionada con el comentario de Rahul Narain de que la clase de funciones cuasi-convexas no es cerrada bajo adición.

La teoría de la dualidad utiliza mucho las funciones de optimización de la forma $f+L$ sobre todas las funciones lineales $L$ . Si una función $f$ es convexo, entonces para cualquier lineal $L$ la función $f+L$ es convexo, y por tanto cuasi-convexo. Recomiendo demostrar lo contrario como ejercicio: $f+L$ es cuasi-convexa para todas las funciones lineales $L$ si y sólo si $f$ es convexo.

Así, para toda función cuasi-convexa pero no convexa $f$ existe una función lineal $L$ tal que $f+L$ no es cuasi-convexo. Te animo a que construyas un ejemplo de función cuasi-convexa $f$ y una función lineal $L$ tal que $f+L$ tiene mínimos locales que no son mínimos globales.

Así, en cierto sentido, las funciones convexas son la clase de funciones a las que se aplican las técnicas utilizadas en la teoría de la dualidad.

Answer 2

Se han desarrollado sofisticados métodos de optimización para tratar problemas en los que no es evidente cuál es la solución. En general, es posible que no sepamos mucho sobre el comportamiento de la función de costes, por lo que no podemos decidir a priori si existe un mínimo único o no. Necesitamos métodos de optimización para encontrar el o un mínimo.

Para los problemas convexos, el comportamiento global viene determinado por propiedades puramente locales. Si una función es convexa localmente en todas partes, también lo es globalmente. Por lo tanto, para este tipo de problemas bastan las soluciones locales, lo que facilita mucho su tratamiento.

Answer 3

Para su primera pregunta, la respuesta es básicamente sí.

Los métodos de gradiente suelen ser métodos de descenso, por lo que la función de coste disminuye en los puntos que no son óptimos. Muchos de estos métodos también tienen la propiedad de que cualquier punto de acumulación de la secuencia generada no puede tener un gradiente distinto de cero (se denominan métodos de descenso "garantizados"). (Esta incómoda formulación permite que la función de coste sea no diferenciable en un mínimo).

He aquí una condición suficiente que se aplica al problema anterior: Sea el punto inicial $x_0$ y que $L_{x_0} = \{x | f(x) \leq f(x_0) \}$ . Supongamos que $L_{x_0}$ es compacto y el gradiente es distinto de cero en todos los puntos distintos del minimizador. Entonces cualquier método de descenso "garantizado" convergerá al minimizador. (Estoy asumiendo que la función de coste $f$ es $C^1$ en puntos no óptimos). El problema que tienes arriba satisface estas condiciones.

La segunda pregunta es más bien un tema de debate. Algunos puntos a tener en cuenta:

La dualidad es otra gran ventaja para los problemas convexos. Los problemas duales suelen ser más fáciles de resolver.

Los problemas pueden transformarse a menudo en problemas convexos, siendo los posinomios un buen ejemplo.

A menudo, la convexidad de los conjuntos de niveles es el criterio importante. Varias generalizaciones (por ejemplo, la pseudoconvexidad y la cuasi-convexidad) pueden extender la utilidad de la convexidad a entornos más amplios.

Answer 4

Como ha dicho otra persona, los problemas convexos suelen tener un dual, que permite a un algoritmo resolver el problema desde dos lados y declarar la solución cuando la brecha de dualidad está suficientemente cerca de 0 (cuando el límite inferior y superior de la solución convergen). También hay métodos y algoritmos bastante eficientes que pueden resolver problemas convexos canónicos que no se extienden fácilmente a los problemas cuasiconvexos generales.

Para los problemas cuasiconvexos estrictos, un método de descenso de gradiente debería ser suficiente, pero es una cuestión de eficiencia algorítmica. Los algoritmos para los problemas convexos canónicos son mucho más eficientes.

Al menos, esa es mi impresión de por qué hay tanta atención a la convexidad. Sin embargo, se podría argumentar que la cuasiconvexidad a menudo se pasa por alto cuando sería útil...

Answer 5

No soy un experto, pero sólo con mirar tu función puedes ver que el descenso de gradiente no convergería al minimizador global. El descenso por gradiente busca lugares en los que el gradiente (que no es más que la derivada para funciones unidimensionales como la que proporcionas) es cero. En una función convexa, a medida que te acercas al mínimo, el gradiente se acerca a cero (y viceversa). Pero puedes ver que, a medida que te acercas al mínimo en tu función, la derivada se hace más y más de cero.

Si intentas hacer un descenso de gradiente sobre esa función, en realidad te alejarás cada vez más del mínimo, ya que el gradiente se minimiza a medida que te acercas al infinito (positivo o negativo).

Así que al menos una de las razones por las que la convexidad es tan importante en la optimización es que el mínimo global es también el único punto crítico (lugar en el que el gradiente es cero), lo que te permite buscar uno buscando el otro. En cierto sentido, eliges un punto, miras un poco alrededor y te mueves en la dirección que hace que tu gradiente sea menor. Repite esto lo suficiente y llegarás a un gradiente realmente pequeño, que corresponde a estar cerca del mínimo.