Optimización Convexa

📚 Resumen del Contenido

Un curso y libro exhaustivo de nivel posgraduado que cubre la teoría, aplicaciones y algoritmos numéricos de la optimización convexa. Se enfatiza en reconocer y formular problemas convexos en ingeniería y ciencias.

Domine la fundamentación matemática y los algoritmos prácticos de la optimización convexa para ingeniería y ciencia de datos.

Autor: Stephen Boyd, Lieven Vandenberghe

Agradecimientos: Apoyado parcialmente por la NSF, y mediante contribuciones de estudiantes y colegas en Stanford y UCLA, incluyendo menciones especiales a Arkadi Nemirovski y Kishan Baheti.

🎯 Objetivos de Aprendizaje

1. Definir los componentes de un problema matemático de optimización, incluyendo la función objetivo, las restricciones y las variables.
2. Distinguir entre problemas de mínimos cuadrados, programación lineal y optimización convexa según sus propiedades matemáticas.
3. Comparar estrategias de optimización local y global y evaluar la complejidad computacional asociada a cada una.
4. Definir y distinguir entre conjuntos afines, conjuntos convexos y conos usando notación formal de combinación.
5. Identificar y representar conjuntos convexos estándar, como bolas euclidianas, elipsoides, politopos y el cono semidefinido positivo.
6. Aplicar operaciones que preservan la convexidad, tales como intersección, transformaciones afines y funciones perspectivas, para verificar propiedades de conjuntos.
7. Identificar y aplicar operaciones que preservan la convexidad, incluyendo el supremo puntual de funciones afines y reglas de composición vectorial.
8. Derivar el conjugado de Lagrange de diversas funciones y aplicar la desigualdad de Young.
9. Caracterizar la cuasiconvexidad usando conjuntos subnivel y condiciones diferenciales de primer y segundo orden.
10. Formular y Transformar: Convertir problemas de optimización crudos en formas convexas estándar utilizando variables de holgura y eliminación de restricciones.

🔹 Lección 1: Introducción a la Optimización Matemática

Resumen: Esta lección introduce los conceptos fundamentales de la optimización matemática, pasando desde la formulación general del problema hasta clases específicas resolubles como mínimos cuadrados y programación lineal. Destaca la distinción crítica entre optimización convexa y no convexa, detallando cómo los métodos convexos actúan como un "cauce confiable" para la eficiencia y proporcionan herramientas vitales para abordar problemas no lineales más difíciles.

Resultados de Aprendizaje:

• Definir los componentes de un problema matemático de optimización, incluyendo la función objetivo, las restricciones y las variables.
• Distinguir entre problemas de mínimos cuadrados, programación lineal y optimización convexa según sus propiedades matemáticas.
• Comparar estrategias de optimización local y global y evaluar la complejidad computacional asociada a cada una.

🔹 Lección 2: Teoría de Conjuntos Convexos

Resumen: Esta lección explora la geometría fundamental de la optimización, avanzando desde estructuras lineales básicas hasta las propiedades complejas de conjuntos convexos y conos. Cubre las definiciones matemáticas de conjuntos afines y convexos, examina geometrías específicas como politopos y conos semidefinidos positivos, y detalla las operaciones y teoremas que permiten a los investigadores caracterizar y manipular conjuntos convexos en espacios de alta dimensión.

Resultados de Aprendizaje:

• Definir y distinguir entre conjuntos afines, conjuntos convexos y conos usando notación formal de combinación.
• Identificar y representar conjuntos convexos estándar, incluyendo bolas euclidianas, elipsoides, politopos y el cono semidefinido positivo.
• Aplicar operaciones que preservan la convexidad, tales como intersección, transformaciones afines y funciones perspectivas, para verificar propiedades de conjuntos.

🔹 Lección 3: Funciones Convexas y Propiedades

Resumen: Esta lección explora operaciones avanzadas que preservan la convexidad, como supremos puntuales y reglas específicas de composición, e introduce la función conjugada de Lagrange. Extiende el concepto de convexidad a funciones cuasiconvexas y log-concavas, mientras también examina la convexidad respecto a desigualdades generalizadas y propiedades matriciales específicas como el complemento de Schur. Estos conceptos constituyen la base matemática para identificar y formular problemas de optimización complejos.

Resultados de Aprendizaje:

• Identificar y aplicar operaciones que preservan la convexidad, incluyendo el supremo puntual de funciones afines y reglas de composición vectorial.
• Derivar el conjugado de Lagrange de diversas funciones y aplicar la desigualdad de Young.
• Caracterizar la cuasiconvexidad usando conjuntos subnivel y condiciones diferenciales de primer y segundo orden.

🔹 Lección 4: Formulación de Problemas de Optimización Convexa

Resumen: Esta lección cubre la estructura formal y la transformación de problemas de optimización convexa, desde formas estándar y condiciones de optimalidad hasta clases específicas de problemas como Programación Lineal (LP), Programación Cuadrática (QP) y Programación Semidefinida (SDP). Los estudiantes aprenderán a identificar la optimalidad global, usar el método de bisección para problemas cuasiconvexos y aplicar la scalarización a la optimización multicriterio vectorial.

Resultados de Aprendizaje:

• Formular y Transformar: Convertir problemas de optimización crudos en formas convexas estándar usando variables de holgura y eliminación de restricciones.
• Analizar la Optimalidad: Aplicar el criterio de optimalidad basado en gradientes para determinar si un punto es óptimo global.
• Clasificar y Resolver: Distinguir entre LP, QP, SOCP, GP y SDP, y aplicar métodos especializados como el Método de Bisección para funciones cuasiconvexas.

🔹 Lección 5: Dualidad de Lagrange y Condiciones KKT

Resumen: Esta lección explora la teoría fundamental de la dualidad de Lagrange, pasando desde la definición de la función dual de Lagrange hasta la formulación del problema dual. Cubre la brecha crítica entre valores óptimos primal y dual, las interpretaciones geométricas y juegos teóricas de estas relaciones, y las condiciones Karush-Kuhn-Tucker (KKT) que caracterizan soluciones óptimas. Finalmente, la lección extiende estos conceptos al análisis de sensibilidad y precios sombra.

Resultados de Aprendizaje:

• Derivar la función dual de Lagrange y formular el problema dual para diversos problemas de optimización.
• Evaluar la relación entre problemas primal y dual usando dualidad débil/fuerte y la condición de calificación de Slater.
• Aplicar las condiciones de optimalidad KKT para resolver y verificar soluciones óptimas en problemas convexos y no convexos.

🔹 Lección 6: Aproximación, Ajuste y Regularización

Resumen: Esta lección explora los fundamentos matemáticos y aplicaciones prácticas de aproximar soluciones a sistemas de ecuaciones lineales y ajustar funciones a datos. Cubre aproximaciones basadas en normas, incluyendo funciones de penalización y regularización para gestionar valores atípicos y esparsidad, y técnicas de optimización robusta para manejar incertidumbres en los datos. Además, detalla el ajuste de funciones bajo restricciones específicas como convexidad y monotonía.

Resultados de Aprendizaje:

• Formular y resolver problemas de aproximación por norma e interpretar las diferencias geométricas y estadísticas entre enfoques de mínimos cuadrados, Chebyshev y L1.
• Diseñar e implementar modelos de aproximación regularizados para alcanzar compromisos entre error residual, magnitud de la solución y esparsidad.
• Construir marcos de aproximación robustos para tener en cuenta incertidumbres en la matriz de datos.

🔹 Lección 7: Estimación y Inferencia Estadística

Resumen: Esta lección explora la intersección entre inferencia estadística y optimización convexa. Se centra en formular problemas de estimación —incluyendo máxima verosimilitud, estimación no paramétrica de distribuciones y diseño óptimo de detectores— como programas convexos. Los estudiantes aprenderán a utilizar la optimización para encontrar parámetros y diseñar experimentos informativos.

Resultados de Aprendizaje:

• Formular y resolver problemas de Estimación de Máxima Verosimilitud (MLE) y Regresión Logística como tareas de optimización convexa.
• Diseñar detectores óptimos usando Programación Lineal (LP) e interpretar Curvas de Respuesta Operativa del Receptor (ROC).
• Aplicar técnicas de estimación no paramétrica, incluyendo Máxima Entropía y minimización de divergencia de Kullback-Leibler.

🔹 Lección 8: Problemas Geométricos y Clasificación

Resumen: Esta lección explora la aplicación de la optimización convexa a problemas geométricos, incluyendo la proyección de puntos sobre conjuntos, el cálculo de distancias entre conjuntos y la caracterización de centros de conjuntos. Extiende estos principios geométricos a tareas del mundo real como clasificación lineal y no lineal, colocación óptima de instalaciones y planificación de pisos mediante programación geométrica.

Resultados de Aprendizaje:

• Formular y resolver problemas de proyección y distancia entre conjuntos convexos usando condiciones KKT y representaciones duales.
• Aproximar conjuntos convexos complejos usando elipsoides de volumen extremal e identificar sus factores de eficiencia.
• Calcular diversos centros de conjunto y aplicarlos a discriminación y clasificación robustas.

🔹 Lección 9: Algoritmos de Minimización sin Restricciones

Resumen: Esta lección cubre los fundamentos teóricos y las implementaciones algorítmicas de la minimización sin restricciones para funciones convexas. Detalla métodos de descenso que van desde el Descenso por Gradiente de primer orden hasta el Método de Newton de segundo orden. Una parte significativa se dedica al análisis de convergencia, centrado en la convexidad fuerte y la teoría invariante afín de autoconcordancia.

Resultados de Aprendizaje:

• Definir la convexidad fuerte y utilizar sus implicaciones para proporcionar cotas superiores sobre la suboptimalidad y la distancia al óptimo.
• Comparar y contrastar el Descenso por Gradiente con el Descenso más empinado bajo normas euclidianas, cuadráticas y L1.
• Calcular el paso de Newton y el decremento de Newton, explicando por qué el método de Newton es invariante afín.

🔹 Lección 10: Minimización con Restricciones de Igualdad

Resumen: Esta lección explora métodos para resolver problemas de optimización convexa con restricciones lineales de igualdad. Se centra en la derivación e implementación del paso de Newton, comparando métodos de inicio factible e infactible, e interpretando estos pasos dentro de un marco primal-dual. Énfasis especial en la implementación numérica eficiente mediante eliminación de bloques del sistema KKT.

Resultados de Aprendizaje:

• Calcular e interpretar el paso de Newton y el decremento para problemas con restricciones de igualdad.
• Demostrar la equivalencia entre el método de Newton con restricciones de igualdad y la eliminación de esas restricciones.
• Implementar el método de Newton con inicio infactible y explicar su propiedad de reducción del residuo primal-dual.

🔹 Lección 11: Métodos de Punto Interior

Resumen: Esta lección cubre los métodos de punto interior, que resuelven problemas de optimización convexa con restricciones de desigualdad aplicando el método de Newton a una secuencia de problemas con restricciones de igualdad. El núcleo gira en torno a funciones barrera logarítmicas, trazando una ruta central hacia la solución óptima, y utilizando marcos primal-dual para aumentar eficiencia y robustez.

Resultados de Aprendizaje:

• Definir y construir funciones barrera logarítmicas y caracterizar la ruta central y sus puntos duales asociados.
• Implementar el método de barrera, incluyendo el equilibrio entre pasos de centrado y iteraciones externas.
• Formular y resolver problemas de fase I de factibilidad para encontrar puntos de partida estrictamente factibles.