The convex optimization approach to regret minimization

El enfoque de la optimización convexa aplicado a la minimización de arrepentimiento

En el escenario en línea de toma de decisiones, un jugador tiene que escoger entre un conjunto de decisiones disponibles y, tras ello, incurre en una pérdida correspondiente a la calidad de la opción elegida. El paradigma de la minimización de arrepentimiento (regret minimization) sugiere la meta de causar una pérdida promedio que se acerque a la mejor decisión fijada a posteriori. Recientemente las herramientas de la optimización convexa han dado lugar a algoritmos que son más generales, unifican resultados previos y con frecuencia brindan límites de arrepentimiento nuevos y mejorados.

En este documento se estudian algunos de los desarrollos recientes en esta fusión entre la optimización y el aprendizaje. Se comienza describiendo dos plantillas generales para producir algoritmos y validar límites de arrepentimiento. Las plantillas son muy simples y unifican el análisis de varios algoritmos bien conocidos y utilizados.

Linear Programming: Foundations and Extensions

Programación lineal: fundamentos y extensiones

Este libro se centra en optimización restringida (constrained optimization). Comienza con un tratamiento profundo de la programación lineal y continúa con análisis convexo, flujos de redes, programación entera, programación cuadrática y optimización convexa. A lo largo de este recorrido también se incluye la programación dinámica y el problema de complementariedad lineal.

El documento tiene como objetivo constituirse como una primera introducción al tema. Ejemplos específicos y algoritmos concretos preceden tópicos más abstractos. Sin embargo, los temas cubiertos se desarrollan con cierta profundidad, se trabaja en detalle un considerable número de ejemplos numéricos y se incluyen muchos aspectos recientes, de los cuales los métodos de punto interior son los más notables. Los ejercicios de final de cada capítulo ilustran los planteamientos teóricos y, en algunos casos, los amplían.

Se divide en cuatro partes. Para las dos primeras se asume que existe una formación previa en álgebra lineal. Para las últimas dos se requiere cierto conocimiento en cálculo multivariado. En particular debe saberse cómo emplear los multiplicadores de Lagrange para resolver problemas de cálculo simple en dos y tres dimensiones.