¿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

Si la pregunta es "¿Existen algoritmos de búsqueda global no convexos con propiedades demostrables?", la respuesta es "Sí, muchos". Los algoritmos que conozco utilizan el análisis de intervalos. Aquí hay un artículo seminal de 1979: Optimización global mediante el análisis de intervalos . Y aquí hay un libro sobre el tema . Los requisitos de la función son que sea Lipschitz o suave hasta cierto orden, y que no tenga una explosión combinatoria de óptimos locales. Estas técnicas no son tan rápidas como la programación lineal o convexa, pero resuelven un problema más difícil, así que no se les puede echar en cara. Y desde un punto de vista práctico, para funciones razonables, convergen bastante rápido.

Answer 2

Creo que le interesarán los trabajos de Parrilo, Lasserre, Putinar, Sturmfels, Nie, Helton, etc., sobre sumas de cuadrados y métodos de momentos para la optimización polinómica. Buscan formas de convertir la optimización general (no convexa) de polinomios con restricciones polinómicas en secuencias de programas semidefinidos (convexos).

La idea general es la siguiente. Supongamos que deseamos minimizar $f$ en $X$ . Supongamos, para simplificar, que $X$ es compacto y $f$ es continua. Podemos convertirlo en un problema convexo extendiéndolo al conjunto de $\Delta(X)$ de medidas de probabilidad de Borel sobre $X$ y definiendo $f(\sigma)=\int f d\sigma$ para $\sigma\in\Delta(X)$ . El problema de optimización resultante es convexo, tiene el mismo valor óptimo global que el problema original, y a partir de cualquier solución óptima $\sigma$ se puede extraer fácilmente una solución óptima al problema original (basta con tomar cualquier elemento del soporte de $\sigma$ ).

El problema, por supuesto, es que nuestro nuevo problema convexo es de dimensiones infinitas. Sin embargo, en el caso de que todos los datos del problema sean polinómicos, hay una serie de buenas maneras de aproximar el problema de dimensión infinita desde el exterior mediante programas semidimensionales. En particular, podemos encontrar secuencias de tales SDP en dimensiones sucesivamente más altas cuyos valores aumentan monotónicamente hasta el valor mínimo global del problema original.

Esto contrasta con los métodos locales en los que intentamos decrecer hacia el valor mínimo, y la no-convexidad asegura más o menos que no podemos hacerlo monótonamente. Además, mientras que los métodos locales proporcionan fácilmente límites superiores al valor mínimo (basta con evaluar f en cualquier lugar para obtener dicho límite), es muy difícil obtener información sobre los límites inferiores que coinciden con los métodos locales.

Por supuesto, el inconveniente es que cuando el SDP te da un valor que es estrictamente inferior al mínimo global, entonces, por definición, no puede darte un $x$ donde se alcanza este valor. Sin embargo, si uno de los SDP de la secuencia da el mínimo global exacto, entonces un valor de $x$ donde se alcanza puede extraerse del SDP dual, en cuyo punto se tienen límites superiores e inferiores coincidentes en el óptimo, por lo que se certifica que este $x$ es óptima. Como alternativa, una vez que se considere que se tiene un "buen" límite inferior, se pueden utilizar métodos locales para tratar de encontrar un $x$ que se aproxima lo suficiente a ese valor para sus propósitos.

Por supuesto, los problemas de exhaustividad NP aseguran que en general no hay mucho que podamos decir sobre la tasa de convergencia de tales procedimientos. Sin embargo, en la práctica funcionan sorprendentemente bien. Explicar esto es un importante problema abierto.

En el OCW del MIT hay una excelente introducción a estas técnicas en forma de apuntes del curso de Parrilo (que es uno de mis directores de tesis).

Answer 3

En cierto sentido, la dificultad fundamental de la optimización no convexa es que se topa rápidamente con la completitud NP. Si $P\ne NP$ Entonces no va a haber ningún eficiente y de uso general para resolver problemas de optimización no convexos o convertirlos en convexos.

Dicho esto, como escribió Carl, por supuesto que hay muchas cosas interesantes que demostrar sobre la optimización no convexa, ¡si estás dispuesto a renunciar a un algoritmo rápido que siempre funcione! Por ejemplo, garantías de aproximación, convergencia en tiempo exponencial suave...

Answer 4

Hola, me refiero a esto desde el punto de vista de un profesional. Tu pregunta sobre si la optimización no convexa está siempre guiada por la heurística puede responderse de la siguiente manera:

No.

Hay muchas técnicas basadas en el gradiente para la optimización global no convexa que NO dependen de ninguna heurística. Suelen basarse en la partición del espacio de soluciones y en la realización de algún tipo de búsqueda de ramas y límites utilizando relajaciones convexas ajustadas (las relajaciones más ajustadas que se pueden obtener para las funciones no lineales son las relajaciones de McCormick). Como se ha mencionado, estos algoritmos tienen una complejidad exponencial en el peor de los casos, pero son rigurosos (no heurísticos) y son capaces de dar una solución global demostrable.

La optimización global no convexa es un área activa de investigación: http://www.mat.univie.ac.at/~neum/glopt/techniques.html#branch

El conocido software BARON, por ejemplo, puede encontrar rigurosamente el óptimo global de un problema no lineal no convexo.

Otros programas/algoritmos son:

LaGO https://projects.coin-or.org/LaGO

Couenne https://projects.coin-or.org/Couenne

En la literatura abierta se pueden encontrar documentos que proporcionan detalles matemáticos para todos los solucionadores anteriores.

Los profesionales de este ámbito se han dado cuenta de que los procedimientos para encontrar la solución global de un problema general no convexo suelen ser NP-duros (hasta ahora no se ha encontrado ninguna excepción).

Un caso especial de esto puede verse en la programación polinómica, donde un problema de optimización polinómico no convexo puede resolverse descomponiendo sus condiciones KKT (de optimalidad) en su base de Groebner. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.6266

A primera vista, esto parece atractivo porque parecería que cualquier problema de optimización no convexo puede entonces aproximarse como un problema de programación polinómica tomando su expansión de Taylor. Sin embargo, el cálculo de las bases de Groebner es difícil de calcular.

Espero que eso te dé algunas pistas.

Answer 5

Recientemente ha habido una avalancha de nuevos resultados sobre métodos no convexos demostrables que pueden garantizar la convergencia al óptimo global. En otros casos, se demuestra que el propio problema no convexo no tiene óptimos locales espurios. El caso clásico es el de la descomposición del valor singular (SVD), que no es convexo, pero puede resolverse. Esto se debe a que sólo el vector propio superior es el óptimo global y local, y todos los demás vectores propios son puntos de equilibrio (suponiendo que haya un vacío propio). Recientemente hemos estudiado los problemas de SVD de los tensores. Mientras que los tensores generales son difíciles de descomponer, para un tensor ortogonal, no hay óptimos locales espurios y por lo tanto, podemos encontrar la descomposición correcta. Puede consultar nuestro artículo para obtener más detalles.

http://newport.eecs.uci.edu/anandkumar/pubs/AnandkumarEtal_Tensor12.pdf

Para dar más ejemplos de métodos no convexos que pueden ser analizados, hemos demostrado recientemente que el problema del aprendizaje de diccionarios o de la codificación dispersa también puede resolverse correctamente. Este es el problema en el que queremos ajustar los datos como una combinación dispersa de un diccionario desconocido. El régimen desafiante es el escenario sobrecompleto o subdeterminado donde hay más elementos del diccionario que la dimensión de los datos observados. Se pueden encontrar más detalles en

http://newport.eecs.uci.edu/anandkumar/pubs/Anandkumar-COLT2014.pdf

Por último, recientemente hemos demostrado la convergencia global de un método natural no convexo para el ACP robusto. Este es el problema de encontrar una aproximación de bajo rango de los datos después de eliminar las corrupciones dispersas. Recientemente hemos demostrado que nuestro método no convexo está garantizado para trabajar en el mismo régimen que el método convexo, y con una complejidad computacional mucho menor. Los detalles se pueden encontrar en mi sitio web.

Anima Anandkumar U.C. Irvine