¿Por qué se definen los algoritmos de optimización en términos de otros problemas de optimización?

Question

Estoy investigando algunas técnicas de optimización para el aprendizaje automático, pero me sorprende encontrar que un gran número de algoritmos de optimización están definidos en función de otros problemas de optimización. Ilustro algunos ejemplos a continuación.

Por ejemplo https://arxiv.org/pdf/1511.05133v1.pdf

Todo parece bien hasta que aparece este $\text{argmin}_x$ en la actualización de $z^{k+1}$....entonces ¿cuál es el algoritmo que resuelve el $\text{argmin}$? No lo sabemos, y no lo dice. Así que mágicamente tenemos que resolver otro problema de optimización que es encontrar el vector minimizador de modo que el producto interno sea el mínimo - ¿cómo se puede hacer esto?

Tomemos otro ejemplo: https://arxiv.org/pdf/1609.05713v1.pdf

Todo parece bien hasta que te encuentras con ese operador proximal en medio del algoritmo, ¿cuál es la definición de ese operador?

Boom:

Ahora, por favor, ¿cómo se resuelve este $\text{argmin}_x$ en el operador proximal? No lo dice. En cualquier caso, ese problema de optimización parece difícil (NP DIFÍCIL) dependiendo de lo que sea $f$.

¿Alguien puede iluminarme acerca de:

1. ¿Por qué tantos algoritmos de optimización están definidos en función de otros problemas de optimización?

(¿No sería esto una especie de problema del huevo y la gallina: para resolver el problema 1, necesitas resolver el problema 2, usando el método para resolver el problema 3, que se basa en resolver el problema ...)

2. ¿Cómo se resuelven estos problemas de optimización que están incrustados en estos algoritmos? Por ejemplo, $x^{k+1} = \text{argmin}_x \text{función de pérdida realmente complicada}$, ¿cómo encontrar el minimizador en el lado derecho?

3. En última instancia, estoy desconcertado acerca de cómo estos algoritmos se pueden implementar numéricamente. Reconozco que sumar y multiplicar vectores son operaciones fáciles en python, pero ¿qué pasa con $\text{argmin}_x$, hay alguna función (script) que te dé mágicamente el minimizador de una función?

(Recompensa: ¿alguien puede referenciar un documento en el cual los autores aclaren el algoritmo para el subproblema incrustado en el algoritmo de optimización de alto nivel?)

Answer 1

Estás viendo diagramas de flujo de algoritmos de nivel superior. Algunos de los pasos individuales en el diagrama de flujo pueden merecer sus propios diagramas de flujo detallados. Sin embargo, en los trabajos publicados con énfasis en la brevedad, a menudo se omiten muchos detalles. Los detalles de problemas de optimización interna estándar, considerados como "vieja escuela", a menudo no se proporcionan en absoluto.

La idea general es que los algoritmos de optimización pueden requerir la solución de una serie de problemas de optimización generalmente más fáciles. No es raro tener 3 o incluso 4 niveles de algoritmos de optimización dentro de un algoritmo de nivel superior, aunque algunos de ellos son internos para optimizadores estándar.

Incluso decidir cuándo terminar un algoritmo (en uno de los niveles jerárquicos) puede requerir resolver un problema de optimización adicional. Por ejemplo, un problema de mínimos cuadrados lineales con restricciones no negativas podría resolverse para determinar los multiplicadores de Lagrange utilizados para evaluar la puntuación de optimalidad de KKT utilizada para decidir cuándo declarar optimalidad.

Si el problema de optimización es estocástico o dinámico, puede haber aún más niveles jerárquicos de optimización.

Aquí tienes un ejemplo. Programación Cuadrática Secuencial (SQP). Un problema de optimización inicial se trata resolviendo de forma iterativa las condiciones de optimalidad de Karush-Kuhn-Tucker, comenzando desde un punto inicial con un objetivo que es una aproximación cuadrática del Lagrangiano del problema, y una linealización de las restricciones. Se resuelve el Programa Cuadrático resultante (QP). El QP que se resolvió tiene restricciones de región de confianza, o se realiza una búsqueda en línea desde el iterado actual hasta la solución del QP, que es en sí mismo un problema de optimización, para encontrar el próximo iterado. Si se utiliza un método Quasi-Newton, se debe resolver un problema de optimización para determinar la actualización Quasi-Newton a la Hessiana del Lagrangiano, generalmente esto es una optimización en forma cerrada utilizando fórmulas en forma cerrada como BFGS o SR1, pero podría ser una optimización numérica. Luego se resuelve el nuevo QP, etc. Si el QP es siempre infactible, incluyendo al inicio, se resuelve un problema de optimización para encontrar un punto factible. Mientras tanto, puede haber uno o dos niveles de problemas de optimización internos que se llaman dentro del solucionador de QP. Al final de cada iteración, se podría resolver un problema de mínimos cuadrados lineales no negativos para determinar la puntuación de optimalidad. Etc.

Si se trata de un problema de enteros mixtos, entonces todo este rollo podría realizarse en cada nodo de ramificación, como parte de un algoritmo de nivel superior. De manera similar para un optimizador global, se usa un problema de optimización local para producir una cota superior en la solución óptima global, luego se realiza una relajación de algunas restricciones para producir un problema de optimización de cota inferior. Se podrían resolver miles o incluso millones de problemas "fáciles" de optimización de ramificación y acotamiento para resolver un problema de optimización mixto o global.

Esto debería empezar a darte una idea.

Edición: En respuesta a la pregunta de la gallina y el huevo que se añadió a la pregunta después de mi respuesta: Si hay un problema de la gallina y el huevo, entonces no es un algoritmo práctico bien definido. En los ejemplos que di, no hay ningún problema de la gallina y el huevo. Los pasos del algoritmo de nivel superior invocan solucionadores de optimización, que están definidos o ya existen. SQP invoca de forma iterativa un solucionador de QP para resolver subproblemas, pero el solucionador de QP resuelve un problema más fácil, QP, que el problema original. Si hay un algoritmo de optimización global de nivel aún más alto, puede invocar un solucionador SQP para resolver subproblemas de optimización no lineales locales, y a su vez, el solucionador SQP llama a un solucionador de QP para resolver subproblemas de QP. Ningún problema de la gallina y el huevo.

Nota: Las oportunidades de optimización están "en todas partes". Los expertos en optimización, como aquellos que desarrollan algoritmos de optimización, son más propensos a ver estas oportunidades de optimización, y a percibirlas como tales, que el ciudadano promedio. Y siendo propensos a la formulación algorítmica, es bastante natural que vean oportunidades para construir algoritmos de optimización a partir de algoritmos de optimización de nivel inferior. La formulación y solución de problemas de optimización sirven como bloques de construcción para otros algoritmos de optimización (de nivel superior).

Edición 2: En respuesta a la solicitud de recompensa que acaba de añadir el OP. El documento que describe el optimizador no lineal SQP SNOPT https://web.stanford.edu/group/SOL/reports/snopt.pdf menciona específicamente el solucionador de QP SQOPT, que está documentado por separado, como utilizado para resolver subproblemas de QP en SNOPT.

Answer 2

Me gusta la respuesta de Mark, pero quería mencionar "Recocido Simulado", que básicamente puede ejecutarse en la parte superior de cualquier algoritmo de optimización. A alto nivel, funciona así:

Tiene un parámetro de "temperatura" que comienza caliente. Mientras esté caliente, se aleja frecuentemente (y aún más lejos) de donde apunta el algoritmo de optimización subordinado. A medida que se enfría, sigue más de cerca el consejo del algoritmo subordinado y, en cero, lo sigue hasta llegar a un óptimo local.

La intuición es que buscará ampliamente en el espacio al principio, buscando "lugares mejores" para encontrar óptimos.

Sabemos que no hay una solución general real para el problema del óptimo local/global. Cada algoritmo tendrá sus puntos ciegos, pero híbridos como este parecen dar mejores resultados en muchos casos.

Answer 3

Creo que una referencia que podría satisfacer tu deseo está aquí. Ve a la sección 4 - Optimización en la Computación Bayesiana Moderna.

TL;DR - discuten métodos proximales. Una de las ventajas de dichos métodos es la división: puedes encontrar una solución optimizando subproblemas más fáciles. Muchas veces (o, al menos, a veces) puedes encontrar en la literatura un algoritmo especializado para evaluar una función proximal específica. En su ejemplo, hacen desenfoque de imagen. Uno de los pasos es un algoritmo muy exitoso y muy citado por Chambolle.

Answer 4

Esto es bastante común en muchos documentos de optimización y tiene que ver con la generalidad. Los autores suelen escribir los algoritmos de esta manera para mostrar que funcionan técnicamente para cualquier función f. Sin embargo, en la práctica, solo son útiles para funciones muy específicas donde estos subproblemas se pueden resolver eficientemente.

Por ejemplo, y ahora estoy hablando solo del segundo algoritmo, cada vez que se ve un operador proximal (que como mencionaste es otro problema de optimización que puede ser realmente difícil de resolver) normalmente implícito que tiene una solución en forma cerrada para que el algoritmo sea eficiente. Esto es así para muchas funciones de interés en el aprendizaje automático como la norma l1, las normas de grupo, y así sucesivamente. En esos casos, reemplazarías los subproblemas por la fórmula explícita del operador proximal, y no hay necesidad de un algoritmo para resolver ese problema.

En cuanto a por qué están escritos de esta manera, solo ten en cuenta que si tuvieras que idear otra función y quisieras aplicar ese algoritmo, verificarías, primero, si el proximal tiene una solución en forma cerrada o se puede calcular eficientemente. En ese caso, solo ingresas la fórmula en el algoritmo y listo. Como se mencionó antes, esto garantiza que el algoritmo sea lo suficientemente general como para aplicarse a funciones futuras que puedan surgir después de que se publique el algoritmo por primera vez, junto con sus expresiones proximales de algoritmos eficientes para calcularlos.

Finalmente, como ejemplo, toma el papel original del algoritmo FISTA clásico. Derivan el algoritmo para dos funciones muy específicas, la pérdida cuadrada y la norma l1. Sin embargo, señalan que se puede aplicar a cualquier función siempre que cumpla con algunos requisitos previos, uno de ellos es que el proximal del regularizado se pueda calcular eficientemente. Esto no es un requisito teórico sino práctico.

Esta compartimentalización no solo hace que el algoritmo sea general sino también más fácil de analizar: siempre que existan algoritmos para los subproblemas que tengan estas propiedades, entonces el algoritmo propuesto tendrá esta tasa de convergencia o lo que sea.