¿Todas las optimizaciones no convexas son heurísticas?

Question

La optimización convexa es un campo matemáticamente riguroso y bien estudiado. En la programación lineal, toda una serie de métodos manejables permiten obtener los óptimos globales en un tiempo récord. La programación cuadrática es casi igual de fácil, y hay una buena cantidad de métodos de programación semidefinida, cónica de segundo orden e incluso de programación entera que pueden funcionar bastante bien en muchos problemas.

Sin embargo, la optimización no convexa (y en particular las formulaciones extrañas de ciertos problemas de programación entera y optimización combinatoria) son generalmente heurísticas como la "optimización de colonias de hormigas". Básicamente, todos los algoritmos generalizables de optimización no convexa que he encontrado son una combinación (a menudo inteligente, pero aún así) de descenso de gradiente y algoritmos genéticos.

Puedo entender por qué es así -en superficies no convexas la información local es mucho menos útil- pero me imagino que al menos habría un algoritmo que aprendiera de forma demostrable para una amplia clase de funciones si las características locales indican un óptimo global cercano o no. También, tal vez, teorías generales sobre si se puede proyectar una superficie no convexa en dimensiones superiores para hacerla convexa o casi convexa, y cómo hacerlo.

Edición: Un ejemplo. Un polinomio de grado k conocido sólo necesita k + 1 muestras para ser reconstruido - ¿te da esto también el mínimo dentro de un rango dado de forma gratuita, o todavía tienes que buscarlo manualmente? Para cualquier clase más general de funciones, ¿la "capacidad de reconstruir" se traslada a la "capacidad de encontrar óptimos globales"?

Answer 1

Pues bien, existe al menos un problema no convexo, que podemos resolver de forma exacta y rápida: la aproximación de rango inferior. Encontrar la matriz $B$ tal que $rank(B)=k$ "más cercano" a la matriz $A$ de rango $m>k$ . Ese problema se puede resolver con la SVD.

Answer 2

Por supuesto, generalmente la optimización es NP-dura. Sin embargo, hay un par de trucos que se pueden utilizar en el caso no convexo. En primer lugar, si $d$ es la dimensión del dominio, la probabilidad de que, por ejemplo, el descenso por gradiente se atasque en un mínimo local disminuye exponencialmente a medida que $d \rightarrow \infty$ Por lo tanto, el principal obstáculo son, en este caso, los puntos de silla de montar.

Para escapar de los puntos de silla se puede utilizar el método de Newton modificado, que, en lugar de dar pasos $-\alpha H^{-1}\nabla f$ toma medidas de $-\alpha |H|^{-1}\nabla f.$

Este es el llamado Newton sin silla de montar, que requiere $O(d^3)$ tiempo para dar un paso (la inversión de la matriz es lenta). Se puede utilizar una versión que aproxime el subespacio que contiene los vectores propios correspondientes a los valores propios más grandes (en valor absoluto) con una técnica similar al procedimiento de Lanzchos. La restricción de tiempo se convierte en $O(kd)$ para alguna constante $k.$

Ambos métodos fueron introducidos y probados en este artículo: https://arxiv.org/abs/1406.2572

En cuanto a la aplicación pública, aquí hay una: https://github.com/smdrozdov/saddle_free_newton