OPTIMIZACIÓN
La optimización matemática en estadística consiste en encontrar los mejores parámetros o soluciones que maximizan o minimizan una función objetivo concreta, como ajustar un modelo a los datos o minimizar el error, para obtener el rendimiento o las predicciones estadísticas óptimas.
Introducción
Optimización continua
Descenso del gradiente
El descenso del gradiente es la columna vertebral de la optimización en machine learning: actualiza los parámetros iterativamente moviéndose en la dirección de mayor descenso de la función de pérdida.
Método de Newton y BFGS
El método de Newton converge cuadráticamente usando información de segundo orden. BFGS aproxima el hessiano para obtener un rendimiento cercano al de Newton sin el coste O(n³).
Optimización convexa
La optimización convexa es la clase de problemas donde todo mínimo local es global. Unifica la programación lineal, la programación cuadrática y las máquinas de vectores de soporte bajo un mismo marco.
Optimización con restricciones
Programación lineal
La programación lineal optimiza una función objetivo lineal sujeta a restricciones lineales de desigualdad. La región factible es un politopo convexo y el óptimo siempre está en un vértice.
Método Simplex
El método Simplex resuelve programas lineales moviéndose de vértice en vértice del politopo factible, mejorando siempre el objetivo, hasta que no es posible ninguna mejora adicional.
Multiplicadores de Lagrange
Los multiplicadores de Lagrange transforman un problema de optimización restringida en uno sin restricciones incorporando las restricciones al objetivo mediante multiplicadores.
Condiciones KKT
Las condiciones KKT generalizan los multiplicadores de Lagrange a restricciones de desigualdad, proporcionando condiciones de optimalidad necesarias y suficientes para la optimización restringida.
Optimización discreta y combinatoria
Programación entera
La programación entera optimiza objetivos lineales sobre variables enteras o binarias. La ramificación y poda es el algoritmo fundamental: divide el conjunto factible y acota los subproblemas con relajaciones lineales.
Programación dinámica
La programación dinámica resuelve problemas de optimización con subproblemas solapados y subestructura óptima almacenando soluciones para evitar cálculos redundantes.
Algoritmos voraces
Los algoritmos voraces toman la mejor elección local en cada paso sin reconsiderar decisiones anteriores. Cuando se cumple la propiedad de elección voraz, encuentran el óptimo global de forma eficiente.
Algoritmos de grafos
Introducción a los grafos
Los grafos modelan relaciones entre objetos. Aprende los conceptos clave, los tipos de grafos y las estructuras de datos utilizadas para representarlos antes de estudiar los algoritmos de grafos.
Algoritmo de Dijkstra
El algoritmo de Dijkstra encuentra el camino más corto desde un vértice origen hasta todos los demás vértices en un grafo ponderado con pesos de arista no negativos.