Estoy investigando algunas técnicas de optimización para el aprendizaje automático, pero me sorprende descubrir que un gran número de algoritmos de optimización se definen en términos de otros problemas de optimización. Ilustramos algunos ejemplos a continuación.
Por ejemplo https://arxiv.org/pdf/1511.05133v1.pdf
Todo se ve bien y bien, pero luego está este en la actualización de z k + 1 ... entonces, ¿cuál es el algoritmo que resuelve el argmin ? No lo sabemos, y no lo dice. Entonces, mágicamente, debemos resolver otro problema de optimización que es encontrar el vector de minimización para que el producto interno sea mínimo, ¿cómo se puede hacer esto?
Tome otro ejemplo: https://arxiv.org/pdf/1609.05713v1.pdf
Todo se ve bien y bien hasta que golpeas a ese operador proximal en el medio del algoritmo, y ¿cuál es la definición de ese operador?
Auge:
¿Puede alguien por favor iluminarme en cuanto a:
- ¿Por qué hay tantos algoritmos de optimización definidos en términos de otros problemas de optimización?
(¿No sería este un problema de huevo y gallina: para resolver el problema 1, debe resolver el problema 2, utilizando el método para resolver el problema 3, que se basa en resolver el problema ...)
(Recompensa: ¿alguien puede hacer referencia a un documento para el cual los autores aclaran el algoritmo para el subproblema incrustado en el algoritmo de optimización de alto nivel?)
fuente
Respuestas:
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 artículos publicados que hacen hincapié en la brevedad, a menudo se omiten muchos detalles. Es posible que no se proporcionen detalles para problemas de optimización interna estándar, que se consideran "sombrero viejo".
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 a los 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 lateral. Por ejemplo, un problema de mínimos cuadrados lineales no restringidos negativamente podría resolverse para determinar los multiplicadores de Lagrange utilizados para evaluar el puntaje de optimización KKT utilizado para decidir cuándo declarar la optimización.
Si el problema de optimización es estocástico o dinámico, puede haber aún niveles jerárquicos adicionales de optimización.
Aquí hay un ejemplo. Programación secuencial cuadrática (SQP). Un problema de optimización inicial se trata resolviendo iterativamente las condiciones de optimización 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. El programa cuadrático resultante (QP) está resuelto. El QP que se resolvió tiene restricciones de región de confianza o se realiza una búsqueda de línea desde la iteración actual hasta la solución de la QP, que es en sí un problema de optimización, para encontrar la siguiente iteración. Si se utiliza un método de Cuasi-Newton, se debe resolver un problema de optimización para determinar la actualización de Cuasi-Newton al Hessian del Lagrangiano; por lo general, se trata de una optimización de forma cerrada utilizando fórmulas de 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 inviable, incluso para comenzar, 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 interna llamados dentro del solucionador QP. Al final de cada iteración, se puede resolver un problema de mínimos cuadrados lineales no negativos para determinar el puntaje de optimización. Etc.
Si este es un problema de enteros mixtos, entonces este shebang completo 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 utiliza un problema de optimización local para producir un límite superior en la solución globalmente óptima, luego se relajan algunas restricciones para producir un problema de optimización de límite inferior. Se podrían resolver miles o incluso millones de problemas de optimización "fáciles" de rama y límite para resolver un problema de optimización global o entero mixto.
Esto debería comenzar a darte una idea.
Editar : En respuesta a la pregunta de huevo y gallina que se agregó a la pregunta después de mi respuesta: si hay un problema de huevo y gallina, entonces no es un algoritmo práctico bien definido. En los ejemplos que di, no hay pollo ni huevo. Los pasos de algoritmo de nivel superior invocan solucionadores de optimización, que están definidos o ya existen. SQP invoca iterativamente 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 mayor, puede invocar un solucionador SQP para resolver subproblemas de optimización no lineal locales, y el solucionador SQP a su vez llama a un solucionador QP para resolver subproblemas QP. Sin chiicken y huevo.
Nota: Las oportunidades de optimización están "en todas partes". Los expertos en optimización, como los que desarrollan algoritmos de optimización, tienen más probabilidades de ver estas oportunidades de optimización, y verlas como tales, que el promedio de Joe o Jane. Y siendo inclinados algorítmicamente, naturalmente ven 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 (nivel superior).
Edición 2 : en respuesta a la solicitud de recompensa que acaba de agregar el OP. El documento que describe el optimizador no lineal SOPP SNOPT https://web.stanford.edu/group/SOL/reports/snopt.pdf menciona específicamente el solucionador QP SQOPT, que se documenta por separado, como utilizado para resolver subproblemas QP en SNOPT.
fuente
Me gusta la respuesta de Mark, pero creo que mencionaría "Recocido simulado", que básicamente puede ejecutarse sobre cualquier algoritmo de optimización. A un alto nivel funciona así:
Tiene un parámetro de "temperatura" que comienza caliente. Mientras está caliente, se aleja con frecuencia y (y más lejos) de donde apunta el algoritmo de optimización subordinado. A medida que se enfría, sigue el consejo del algoritmo subordinado más de cerca, y en cero lo sigue a cualquier óptimo local en el que haya terminado.
La intuición es que buscará en el espacio ampliamente al principio, buscando "mejores lugares" para buscar óptimos.
Sabemos que no existe una solución general real para el problema óptimo local / global. Cada algoritmo tendrá sus puntos ciegos, pero los híbridos como este parecen dar mejores resultados en muchos casos.
fuente
Creo que una referencia de que puedo satisfacer tu deseo está aquí . Vaya a la sección 4 - Optimización en la computación bayesiana moderna.
TL; DR: discuten los métodos proximales. Una de las ventajas de tales métodos es la división: puede encontrar una solución optimizando subproblemas más fáciles. Muchas veces (o, al menos, a veces) puede encontrar en la literatura un algoritmo especializado para evaluar una función proximal específica. En su ejemplo, hacen ruido de imagen. Uno de los pasos es un algoritmo muy exitoso y altamente citado por Chambolle.
fuente
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 técnicamente funcionan 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 de manera eficiente.
Por ejemplo, y ahora estoy hablando solo del segundo algoritmo, siempre que vea un operador proximal (que, como notó, es otro problema de optimización que puede ser muy difícil de resolver) generalmente está implícito en que tiene una solución de forma cerrada en orden 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 grupales, etc. En esos casos, reemplazaría los subproblemas para la fórmula explícita del operador proximal, y no es necesario un algoritmo para resolver ese problema.
En cuanto a por qué se escriben de esta manera, solo tenga en cuenta que si se le ocurriera otra función y quisiera aplicar ese algoritmo, verificaría, primero, si el proximal tiene una solución de forma cerrada o se puede calcular de manera eficiente. En ese caso, simplemente conecte la fórmula al algoritmo y estará listo. Como se mencionó anteriormente, esto garantiza que el algoritmo sea lo suficientemente general como para aplicarse a la función futura que pueda surgir después de que el algoritmo se publique por primera vez, junto con sus expresiones proximales de algoritmos eficientes para calcularlos.
Finalmente, como ejemplo, tome el papel original del clásico algoritmo FISTA. Derivan el algoritmo para dos funciones muy específicas, la pérdida al cuadrado y la norma l1. Sin embargo, señalan que no se puede aplicar ninguna función siempre que cumplan algunos requisitos previos, uno de ellos es que la proximidad de la regularizada se puede calcular de manera eficiente. Este no es un requisito teórico sino práctico.
Esta compartimentació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, el algoritmo propuesto tendrá esta tasa de convergencia o lo que sea.
fuente