- Um livro-texto que aborda de forma sistemática os princípios da otimização matemática e o conjunto de algoritmos, cobrindo tanto problemas contínuos quanto discretos
- Explica passo a passo diversas abordagens, desde técnicas baseadas em derivadas até métodos estocásticos e evolutivos
- Inclui estruturas matemáticas necessárias para aplicações reais, como restrições, dualidade e programação linear/quadrática
- Cada capítulo oferece resumo e exercícios, permitindo combinar estudo e prática
- Distribuído pela licença aberta da MIT Press (CC BY-NC-ND)
Prefácio e visão geral
- Este livro é um material didático sobre teoria e implementação de algoritmos para resolver problemas de otimização, publicado em sua 2ª edição
- Os autores são Mykel J. Kochenderfer e Tim A. Wheeler
- Publicado pela MIT Press e disponibilizado sob licença Creative Commons não comercial e sem derivações
- Após o prefácio e os agradecimentos, a obra é composta por 13 capítulos
- Cada capítulo é estruturado com conceitos centrais, resumo e exercícios, mantendo um formato voltado ao aprendizado
Capítulo 1. Introdução
- Apresenta a história da otimização, o processo, a formulação matemática e as áreas de aplicação
- Explica extremos (minima) e condições de otimalidade (optimality conditions)
- Inclui visão geral, resumo e exercícios de todo o capítulo
Capítulo 2. Derivadas e gradientes
- Explica a definição e o cálculo de derivadas de uma e várias variáveis
- Inclui técnicas de diferenciação numérica (numerical differentiation) e diferenciação automática (automatic differentiation)
- Aborda gradiente de regressão e técnicas de aproximação estocástica (SPSA)
Capítulo 3. Bracketing
- Explica o conceito de unimodalidade (unimodality) e o procedimento de busca do intervalo inicial
- Reúne algoritmos baseados em intervalo, como busca de Fibonacci, busca da seção áurea e busca por aproximação quadrática
- Inclui os métodos Shubert-Piyavskii e bisseção (bisection)
Capítulo 4. Descida local (Local Descent)
- Explica os conceitos de iteração por direção de descida (descent direction iteration) e tamanho do passo (step factor)
- Inclui técnicas de busca linear (line search) e busca linear aproximada
- Aborda a estratégia de região de confiança (trust region) e critérios de parada
Capítulo 5. Métodos de primeira ordem (First-Order Methods)
- Inclui técnicas principais como descida do gradiente, gradiente conjugado, momentum e momentum de Nesterov
- Reúne algoritmos modernos de otimização como AdaGrad, RMSProp, Adadelta, Adam e Hypergradient Descent
- Fornece resumo comparativo e características de cada método
Capítulo 6. Métodos de segunda ordem (Second-Order Methods)
- Explica o método de Newton (Newton’s Method) e o método das secantes (Secant Method)
- Inclui o algoritmo de Levenberg-Marquardt e métodos quase-Newton (Quasi-Newton)
- Termina com resumo e exercícios
Capítulo 7. Métodos diretos (Direct Methods)
- Apresenta busca por coordenadas, Powell, Hooke-Jeeves, busca em padrão e o método do simplex de Nelder-Mead
- Inclui a técnica de Divided Rectangles
- Foca em abordagens de otimização sem derivadas
Capítulo 8. Métodos estocásticos (Stochastic Methods)
- Aborda métodos estocásticos como descida com ruído, busca adaptativa em malha e otimização sem derivadas
- Inclui simulated annealing, cross-entropy, natural evolution strategies e adaptação da matriz de covariância (CMA)
- Destaca a eficiência da busca baseada em probabilidade
Capítulo 9. Métodos baseados em população (Population Methods)
- Explica técnicas de busca populacional como algoritmos genéticos, evolução diferencial e otimização por enxame de partículas (PSO)
- Inclui Firefly, Cuckoo Search e métodos híbridos
- Resolve problemas com uma estrutura de iteração populacional (population iteration)
Capítulo 10. Restrições (Constraints)
- Explica os conceitos básicos de otimização com restrições (constrained optimization) e os tipos de restrição
- Inclui multiplicadores de Lagrange, variáveis de folga, penalização e métodos de ponto interior (interior point)
- Aborda transformações para remoção de restrições (transformations) e o método dos multiplicadores (method of multipliers)
Capítulo 11. Dualidade (Duality)
- Explica o problema dual (dual problem) e métodos primal-dual
- Inclui dual ascent e ADMM (Alternating Direction Method of Multipliers)
- Trata de aplicações em otimização distribuída (distributed methods)
Capítulo 12. Programação linear (Linear Programming)
- Explica formulação de problemas, algoritmo Simplex (Simplex Algorithm) e certificados duais (dual certificates)
- Apresenta de forma sistemática a estrutura da otimização sob restrições lineares
Capítulo 13. Programação quadrática (Quadratic Programming)
- Formula problemas com função objetivo quadrática e restrições lineares
- Aborda problemas de mínimos quadrados (least squares) e restrições lineares de desigualdade
- Inclui programação da menor distância (least distance programming)
Apêndice e outras informações
- Ao final de cada capítulo há resumo e exercícios
- Publicado pela MIT Press na edição de 2025, com compartilhamento não comercial permitido (CC BY-NC-ND)
- Composição tipográfica baseada em LaTeX; contato em bugs@algorithmsbook.com
4 comentários
Agora não está dando para acessar mesmo :(
https://algorithmsbook.com/optimization/#download
Parece que agora o link mudou um pouco; dá para ver ou baixar o PDF por aqui.
Obrigado!!
Opiniões no Hacker News
Fiquei feliz em ver o tema de otimização (optimization) na capa do HN
Queria apresentar o site de visualização de LP que eu criei. Dá para ver visualmente como algoritmos de Programação Linear reagem quando as restrições ou a função objetivo mudam
Se você entrar na página de demonstração, um polígono é desenhado automaticamente, e dá para observar as iterações do algoritmo enquanto arrasta vértices ou linhas de restrição
Ainda não está muito polido, mas acho que quem gosta de aprendizado visual pode se divertir usando. Feedback é bem-vindo
Queria compartilhar alguns materiais sobre metaheurísticas (metaheuristics)
Na Timefold, onde trabalho, usamos algoritmos como Tabu Search e Simulated Annealing, apresentados nesses livros, para encontrar rapidamente soluções aproximadamente ótimas
Também vale consultar o diagrama de algoritmos de busca local da documentação da Timefold
É um livro-texto de otimização sob licença CC com 521 páginas, e parece realmente excelente
No começo ele trata de algoritmos modernos baseados em gradiente com autodiferenciação (por exemplo, Adam), e na parte final (capítulo 12) cobre otimização linear (simplex etc.)
Também tem muitos exercícios, e era exatamente o tipo de livro que eu esperava há muito tempo
Acho que algoritmos de otimização não servem apenas para resolver problemas, mas são uma tentativa de chegar a um “solucionador geral de problemas”. Em vez de o programa encontrar diretamente a resposta, você define que forma a resposta deve ter e então aplica otimização sobre isso
A IA atual também se baseia nessa abordagem
Este livro do Kochenderfer e sua obra anterior Decision Making Under Uncertainty(PDF) estão entre meus livros técnicos favoritos
As explicações são claras, as visualizações são excelentes, e ele aborda várias formas de pensar sobre otimização além de gradient descent
O código está em Julia, mas não é difícil portar para outras linguagens. Não fique preso à linguagem; foque nos conceitos
Otimização não é só uma técnica, mas a própria forma de pensar para resolver problemas difíceis
Este livro é um material raro que cobre CMA-ES, surrogate model e Gaussian process em um único volume
Se eu tivesse tido um livro assim na época da iniciação científica, teria ajudado muito. Antes, esse conteúdo ficava espalhado por vários artigos e livros
Durante o doutorado, li este livro várias vezes com bastante atenção. Eu pesquisava redes neurais e análise numérica, e ele equilibra muito bem profundidade e amplitude
Ainda hoje eu o uso bastante como referência
Fiquei surpreso ao ver metaheurísticas como Firefly e Cuckoo Search incluídas no livro
Esses algoritmos não são bem vistos na academia e já foram criticados no artigo da ITOR
Existe uma pequena comunidade que pesquisa apenas esse tipo de abordagem e forma uma bolha citando uns aos outros. Isso também costuma gerar controvérsia em conferências
O capítulo sobre otimização multiobjetivo (multiobjective optimization) foi excelente
Fiquei curioso para saber se existem outros livros ou materiais focados nesse tema
Queria saber se alguém poderia comparar este livro com Numerical Optimization, de Nocedal & Wright