¿Utilizan programación semidefinida en la industria?

10

No puedo ver ninguna mención de ello en los listados de trabajo. He visto programación entera mencionada, MIP, programación no lineal entera mixta, LP, programación dinámica, etc., pero no SDP. ¿Es mucho más moderno en la academia que en la industria?

Por mi exposición limitada a académicos y participantes de la industria en sistemas de energía eléctrica, creo que hay una buena posibilidad de que el SDP sea aplicado en problemas óptimos de flujo de energía por parte de operadores de sistemas independientes, pero que depende de la medida en que las cabezas de huevo puedan escalar los enfoques actuales para lidiar con casos de problemas más grandes.

GrayOnGray
fuente

Respuestas:

8

Desde mi propia experiencia limitada en la industria energética, nadie está resolviendo SDP a ese tipo de escala. Tengo un conocimiento limitado de lo que está haciendo el ISO de Nueva Inglaterra, y creo que están más interesados ​​en incorporar la estocasticidad en sus modelos MILP existentes. De amigos que han trabajado en sistemas de energía en laboratorios de investigación gubernamentales en los Estados Unidos, también están pensando en la estocasticidad (programación estocástica, restricciones de posibilidades, optimización robusta ...).

Desde mi experiencia en el sector de las grandes empresas tecnológicas, las personas están resolviendo MILP en los modelos más complicados y generalmente deterministas.

Por el lado de la ingeniería química, deduzco que parecen interesados ​​en MINLP, en particular la optimización no convexa con restricciones cuadráticas, que surge naturalmente en los problemas de mezcla. También hay problemas restringidos por PDE y todas esas otras cosas divertidas, pero eso es principalmente por mi experiencia.

Si tuviera que especular, SDP podría usarse en el diseño de semiconductores como una subrutina (por ejemplo, para MAXCUT), pero dada la falta de solucionadores de calidad, supongo que no hay una gran demanda (al menos).

Yo diría que en la academia, SDP es más interesante como herramienta de prueba, es decir, "¡mira, este problema es tiempo polinómico!" si puedes descubrir cómo lidiar como un SDP. Los solucionadores de SDP son tan delicados (en comparación con otras clases de problemas convexos) que creo que la gente no está realmente entusiasmada con la idea de tener que resolverlos.

IainDunning
fuente
No se sabe que SDP sea siempre en tiempo polinómico, creo. IIRC necesita restricciones adicionales para saberlo con certeza.
usuario541686
Claro, pero si no se cumplieran esas limitaciones, no lo vería en una prueba porque no tendría mucho sentido.
IainDunning
7

La programación semidefinida y la programación de cono de segundo orden no se han adoptado tan rápidamente en la práctica como muchos de nosotros esperábamos. He estado involucrado en esto durante los últimos 20 años, y ha sido muy decepcionante ver un progreso lento. Permítanme señalar algunos de los desafíos:

  1. O(metro2)metroO(metro2) Los requisitos de almacenamiento son un tema activo de investigación, pero en el área de SDP simplemente no han demostrado ser lo suficientemente robustos para su uso en un solucionador de propósito general.

  2. Los proveedores de software LP aún no han considerado adecuado incluir soporte para SDP en sus productos. Comienza a aparecer algún soporte limitado para SOCP.

  3. El conocimiento sobre programación semidefinida se ha extendido lentamente. El libro de texto de Boyd y Vandenberghe ha sido de gran ayuda a este respecto, pero hay un largo camino por recorrer antes de que esta tecnología sea tan conocida como las técnicas de optimización más antiguas.

  4. Los lenguajes y sistemas de modelado (como GAMS, AMPL, etc.) aún no brindan un buen soporte para SOCP y SDP. El paquete CVX es el trabajo más interesante en esta dirección, pero incluso requiere cierta sofisticación por parte del usuario.

SDP ha encontrado aplicaciones a nivel de investigación en muchas áreas de ingeniería y ciencia. Parece probable que estos eventualmente se vuelvan importantes también en la industria.

Brian Borchers
fuente
55
Solo para agregar: el único solucionador comercial de SDP afaik es MOSEK y de todos modos es bastante reciente. Creo que la robustez es más importante de lo que uno puede pensar: en muchas aplicaciones puede asignar más tiempo, pero si un solucionador falla, ¿qué debe hacer?
AndreaCassioli
5

La mayor parte del trabajo del que estoy al tanto en los laboratorios para problemas de flujo de energía se centra también en la optimización estocástica, centrándose principalmente en MILP.

En ingeniería química, están interesados ​​en los MINLP, y el ejemplo clásico es un problema de mezcla (específicamente, el problema prototípico de agrupación de Haverly), por lo que los términos bilineales surgen mucho. En ocasiones aparecen términos trilineales, según los modelos de mezcla termodinámica o los modelos de reacción utilizados. También hay una cantidad limitada de interés en la optimización restringida por ODE o PDE; ninguno de esos trabajos usa SDP.

La mayor parte del trabajo de optimización restringido por PDE que he visto (estoy pensando específicamente en la optimización de topología) no usa SDP. Las restricciones de PDE podrían ser lineales y, en teoría, podrían admitir una formulación de SDP dependiendo de cuáles sean las restricciones objetivas y restantes. En la práctica, los problemas de ingeniería tienden a ser no lineales y producen problemas no convexos que luego se resuelven en los óptimos locales (posiblemente también usando multistart). A veces, las formulaciones de penalización se utilizan para excluir óptimos locales subóptimos conocidos.

Pude ver que tal vez se usa en la teoría del control. La pequeña cantidad de trabajo que he visto sobre "desigualdades de matriz lineal" sugiere que posiblemente podría ser útil allí, pero la teoría de control en la industria tiende a depender de métodos probados y verdaderos en lugar de formulaciones matemáticas innovadoras, por lo que dudo de los SDP se usarán por un tiempo hasta que puedan demostrar su utilidad.

Hay algunos solucionadores de SDP que están bien, y han resuelto problemas que son bastante grandes para la academia (la última vez que lo revisé fue hace 3-4 años, y estaban resolviendo decenas a cientos de miles de variables), pero los escenarios de flujo de energía implican problemas mucho mayores (decenas de millones a miles de millones de variables), y no creo que los solucionadores todavía estén allí. Creo que podrían llegar allí; ha habido una buena cantidad de trabajo reciente sobre métodos de punto interior sin matriz que sugiere que sería factible ampliar los solucionadores de SDP utilizando esas técnicas, pero nadie lo ha hecho todavía, probablemente porque los LP, MILP y NLP convexos surgen con mucha más frecuencia y son tecnologías establecidas.

Geoff Oxberry
fuente
2
Ahora sé muy poco sobre esto, pero lo curioso es que las aplicaciones para controlar la teoría han existido por un tiempo. Desigualdades de matriz lineal en sistemas y control se publicó en 1994. Stephen Boyd realiza la mayor parte de su investigación en la intersección de la optimización y el control, y también lo ha estado haciendo al menos desde 1996.
GrayOnGray
Es verdad. La mayor parte de lo que sé sobre el control industrial proviene de una breve pasantía en la industria de procesamiento químico, y allí, el control predictivo del modelo fue una gran novedad, y creo que se desarrolló en algún momento entre mediados de los 80 y principios de los 90.
Geoff Oxberry