Métodos de optimización no convexos para encontrar predicciones que minimicen el error de decisión

Abstract

Lidiar con parámetros desconocidos en problemas de optimización es un desafío importante y ha sido bien estudiado en la literatura. Una forma de enfrentar este problema es a través de un marco denominado Predict then Optimize, es decir, primero se predicen estos costos a través de observaciones históricas y luego se utilizan las predicciones para tomar una decisión en un problema de optimización. Sin embargo, las decisiones producidas por este marco pueden ser altamente sensibles a los parámetros inciertos, ya que minimizan el error de predicción y no el error de decisión. Es por esto que recientemente se han hecho esfuerzos para construir modelos predictivos enfocados en minimizar el error de decisión. Este marco es conocido como Smart Predict then Optimize (SPO). El objetivo es minimizar una medida de arrepentimiento (o regret) en las decisiones tomadas con predicciones. En esta tesis se formula el problema que minimiza el regret esperado de forma exacta como un modelo de optimización binivel pesimista. Este problema es reformulado utilizando argumentos de dualidad, obteniendo como resultado un problema de optimización cuadrático no convexo. Es conocido que tanto los problemas de optimización binivel como los problemas de optimización no convexos son generalmente difíciles de resolver. Se muestran diferentes modelos y extensiones del problema binivel pesimista. Entre ellos, algunos modelos de referencia presentes en el estado del arte como el modelo de mínimos cuadrados ordinarios y el enfoque propuesto por Elmachtoub y Grigas (2022) (SPO+). Por otro lado, también se muestran extensiones del modelo pesimista como γ-fija y el modelo penalizado, los cuales son restricciones del problema exacto. Además, se presenta un método que tiene como objetivo la linealización del problema de optimización cuadrático no convexo. Finalmente, se muestran varias técnicas computacionales para lograr la escalabilidad de los métodos propuestos. Se reportan extensos resultados computacionales aplicados al problema del camino más corto en instancias de datos generados sintéticamente. Estos resultados indican que el enfoque propuesto en esta tesis puede mejorar el rendimiento en el conjunto de entrenamiento en comparación con SPO+, un método de vanguardia para el aprendizaje centrado en decisiones.