En optimización, ¿cuáles son algunos ejemplos geniales de reformulación?

Bueno, la pregunta es bastante genérica, así que intentaré elegir mis favoritas. Creo que los problemas que pueden formularse como programas lineales son particularmente interesantes porque 1. tenemos solucionadores comerciales eficientes que pueden resolver programas lineales con millones de variables y / o restricciones; 2. Comprendemos la geometría de los conjuntos poliédricos significativamente más que otros conjuntos porque conocemos bastante bien el álgebra lineal (tal vez los esquemas o variedades algebraicos también son muy abstractos, de modo que tomaría uno o dos cursos serios de álgebra para entender lo que estamos tratando de decir y no estamos cerca de un solucionador comercial eficiente). De todos modos, no voy a escribir las reformulaciones explícitas sino solo mencionarlas, aquí vamos. La norma l1 es un gran ejemplo. La norma l1 es convexa pero no lineal, no diferenciable. Es muy útil particularmente en geometría computacional, aprendizaje automático, etc. Más en general, el supremum puntual de funciones lineales se puede formular como un programa lineal. El producto de dos variables binarias (como restricción) puede reformularse como 3 restricciones lineales que involucran las variables binarias usando desigualdades de McCormick (o Fortet). La ruta más corta entre dos nodos en un gráfico (problemas de mincut o maxflow también) se puede resolver como un programa lineal, aunque puede haber algoritmos mucho más eficientes para estos. De hecho, podemos resolver el problema de Factorización de matriz no negativa, que es popular en el aprendizaje automático, puede resolverse usando LP [1206.1270] Factorizando matrices no negativas con programas lineales. Sin embargo, es posible que me falten muchas otras aplicaciones de LP. Una buena aplicación, entre otras, es utilizar la dualidad en SVM, página en cmu.edu. Compruebe esto para ver los problemas que se pueden formular mediante la programación semidefinida de SDP. En muchos SDP, se obtienen muy buenas relajaciones convexas que de otra manera serían muy difíciles de conseguir y esto no es solo cierto en la comunidad de programación matemática porque en el último año al menos he estado en muchas charlas sobre relajaciones SDP en diversas áreas de la informática. , estadísticas, matemática aplicada, etc. Existen técnicas de aproximación lineal por partes que siempre se pueden usar para escribir relajaciones, pero una mejor idea es estudiar las estructuras que ocurren con frecuencia y escribir relajaciones óptimas locales para aquellos, por ejemplo, en la página uiowa.edu. Por supuesto que me perdí mucho (lo siento), ¡pero espero que esto ayude!