- Un libro de texto que aborda de forma sistemática los principios y algoritmos de la optimización matemática, abarcando tanto problemas continuos como discretos
- Explica paso a paso diversos enfoques, desde métodos basados en derivadas hasta métodos estocásticos y evolutivos
- Incluye estructuras matemáticas necesarias para aplicaciones reales, como restricciones, dualidad y programación lineal y cuadrática
- Cada capítulo ofrece resumen y ejercicios, para combinar estudio y práctica
- Se distribuye bajo la licencia abierta de MIT Press (CC BY-NC-ND)
Prólogo y visión general
- Este libro es un texto sobre la teoría y la implementación de algoritmos para resolver problemas de optimización, publicado en su 2.ª edición
- Los autores son Mykel J. Kochenderfer y Tim A. Wheeler
- Publicado por MIT Press y abierto bajo una licencia Creative Commons no comercial y sin obras derivadas
- Después del prólogo y los agradecimientos, está compuesto por 13 capítulos
- Cada capítulo se organiza alrededor de conceptos clave, resumen y ejercicios, manteniendo una estructura centrada en el aprendizaje
Capítulo 1. Introducción
- Presenta la historia, el proceso, la formulación matemática y las áreas de aplicación de la optimización
- Explica los mínimos (minima) y las condiciones de optimalidad (optimality conditions)
- Incluye visión general, resumen y ejercicios de todo el libro
Capítulo 2. Derivadas y gradiente
- Explica la definición y el cálculo de derivadas de una y varias variables
- Incluye técnicas de diferenciación numérica (numerical differentiation) y diferenciación automática (automatic differentiation)
- También trata el gradiente de regresión y la aproximación estocástica (SPSA)
Capítulo 3. Bracketing
- Explica el concepto de unimodalidad (unimodality) y el procedimiento para encontrar un intervalo inicial
- Incluye algoritmos basados en intervalos como búsqueda de Fibonacci, búsqueda de sección áurea y búsqueda por interpolación cuadrática
- También incluye los métodos Shubert-Piyavskii y de bisección (bisection)
Capítulo 4. Descenso local
- Explica los conceptos de iteración en dirección de descenso (descent direction iteration) y tamaño de paso (step factor)
- Incluye técnicas de búsqueda lineal (line search) y búsqueda lineal aproximada
- Trata el enfoque de región de confianza (trust region) y las condiciones de terminación
Capítulo 5. Métodos de primer orden
- Incluye técnicas principales como descenso por gradiente, gradiente conjugado, momentum y momentum de Nesterov
- Presenta algoritmos modernos de optimización como AdaGrad, RMSProp, Adadelta, Adam y Hypergradient Descent
- Ofrece un resumen comparativo y de características de cada método
Capítulo 6. Métodos de segundo orden
- Explica el método de Newton (Newton’s Method) y el método de la secante (Secant Method)
- Incluye el algoritmo de Levenberg-Marquardt y los métodos cuasi-Newton (Quasi-Newton)
- Cierra con resumen y ejercicios
Capítulo 7. Métodos directos
- Presenta búsqueda por coordenadas, Powell, Hooke-Jeeves, pattern search y el método simplex de Nelder-Mead
- Incluye la técnica de Divided Rectangles
- Se enfoca en enfoques de optimización sin derivadas
Capítulo 8. Métodos estocásticos
- Trata enfoques estocásticos como descenso con ruido, búsqueda adaptativa en malla y optimización sin derivadas
- Incluye simulated annealing, entropía cruzada, estrategias evolutivas naturales y adaptación de matriz de covarianza (CMA)
- Destaca la eficiencia de la exploración basada en probabilidad
Capítulo 9. Métodos basados en población
- Explica técnicas de búsqueda poblacional como algoritmos genéticos, evolución diferencial y optimización por enjambre de partículas (PSO)
- Incluye Firefly, Cuckoo Search y métodos híbridos
- Resuelve problemas con una estructura de iteración poblacional (population iteration)
Capítulo 10. Restricciones
- Explica los conceptos básicos de la optimización con restricciones (constrained optimization) y los tipos de restricciones
- Incluye multiplicadores de Lagrange, variables de holgura, métodos de penalización y de punto interior (interior point)
- Trata las transformaciones para eliminar restricciones (transformations) y el método de multiplicadores (method of multipliers)
Capítulo 11. Dualidad
- Explica el problema dual (dual problem) y los métodos primal-dual
- Incluye dual ascent y ADMM (Alternating Direction Method of Multipliers)
- Trata aplicaciones en optimización distribuida (distributed methods)
Capítulo 12. Programación lineal
- Explica la formulación del problema, el algoritmo simplex (Simplex Algorithm) y los certificados duales (dual certificates)
- Presenta de forma sistemática la estructura de la optimización bajo restricciones lineales
Capítulo 13. Programación cuadrática
- Formula problemas con función objetivo cuadrática y restricciones lineales
- Trata problemas de mínimos cuadrados (least squares) y restricciones de desigualdad lineal
- Incluye programación de mínima distancia (least distance programming)
Apéndice y otra información
- Al final de cada capítulo se incluyen resumen y ejercicios
- MIT Press lo publica en la edición de 2025, con permiso de compartición no comercial (CC BY-NC-ND)
- Composición basada en LaTeX; contacto: bugs@algorithmsbook.com
4 comentarios
Ahora mismo no se puede acceder, ¿verdad? T_T
https://algorithmsbook.com/optimization/#download
Parece que ahora el enlace cambió un poco, y desde aquí se puede ver o descargar el PDF.
¡¡Gracias!!
Opinión de Hacker News
Me da gusto ver que el tema de optimización (optimization) llegó a la portada de HN.
Quiero presentar el sitio de visualización de LP que hice. Permite ver de forma visual cómo reaccionan los algoritmos de programación lineal (Linear Programming) cuando cambian las restricciones o la función objetivo.
Si entras a la página de demostración, el polígono se dibuja automáticamente y puedes observar las iteraciones del algoritmo arrastrando vértices o líneas de restricción.
Todavía no está muy pulido, pero creo que a quienes les gusta el aprendizaje visual les puede resultar divertido. Se agradece cualquier feedback.
Quiero compartir algunos recursos sobre metaheurísticas (metaheuristics).
En Timefold, donde trabajo, usamos algoritmos como Tabu Search y Simulated Annealing que aparecen en esos libros para encontrar rápidamente soluciones aproximadamente óptimas.
También vale la pena revisar el diagrama de algoritmos de búsqueda local de la documentación de Timefold.
Es un libro de optimización con licencia CC de 521 páginas y se ve realmente excelente.
Al principio cubre algoritmos modernos basados en gradientes y apoyados en diferenciación automática (por ejemplo, Adam), y en la parte final (capítulo 12) trata optimización lineal (simplex, etc.).
Tiene muchos ejercicios y era justo el tipo de libro que llevaba mucho tiempo esperando.
Creo que los algoritmos de optimización no solo sirven para resolver problemas, sino que son un intento de construir un “solucionador general de problemas”. En lugar de que el programa encuentre la respuesta directamente, se define qué forma debería tener la solución y luego se aplica optimización sobre eso.
La IA actual también se basa en este enfoque.
Este libro de Kochenderfer y su obra anterior Decision Making Under Uncertainty(PDF) están entre mis libros técnicos favoritos.
Las explicaciones son claras, las visualizaciones son excelentes y cubre diversas formas de pensar la optimización más allá del gradient descent.
El código está en Julia, pero no es difícil pasarlo a otros lenguajes. No hay que quedarse atorado con el lenguaje; lo importante es enfocarse en los conceptos.
La optimización no es solo una técnica, sino una forma de pensar para resolver problemas difíciles.
Este libro es uno de los pocos recursos que cubren en un solo volumen CMA-ES, surrogate model y Gaussian process.
Me habría ayudado muchísimo si hubiera existido un libro así cuando hacía investigación de licenciatura. Antes, ese contenido estaba disperso entre muchos papers y libros.
Durante el doctorado leí este libro con mucha atención varias veces. Investigaba redes neuronales y análisis numérico, y el equilibrio entre profundidad y amplitud está muy bien logrado.
Incluso ahora lo sigo usando con frecuencia como material de referencia.
Me sorprendió ver que el libro incluye metaheurísticas como Firefly y Cuckoo Search.
Estos algoritmos no gozan de confianza en la academia y también fueron criticados en este paper de ITOR.
Hay pequeñas comunidades que investigan solo este tipo de enfoques, se citan entre sí y forman una burbuja. En congresos también suelen ser motivo de controversia.
El capítulo sobre optimización multiobjetivo (multiobjective optimization) me pareció excelente.
Me gustaría saber si hay otros libros o recursos centrados en este tema.
Me gustaría saber si alguien puede comparar este libro con Nocedal & Wright, Numerical Optimization.