OTIMIZAÇÃO

A otimização matemática encontra a melhor solução dentro de um conjunto de opções viáveis. Aprenda os conceitos-chave, os tipos de problemas, e as condições de otimalidade.

A descida do gradiente é a espinha dorsal da otimização em machine learning: ela atualiza iterativamente os parâmetros movendo-se na direção de maior descida da função de perda.

O método de Newton converge quadraticamente usando informação de segunda ordem. O BFGS aproxima a Hessiana para obter desempenho próximo ao de Newton sem o custo O(n³).

A otimização convexa é a classe de problemas em que todo mínimo local é global. Ela unifica programação linear, programação quadrática, e máquinas de vetores de suporte sob um único framework.

A programação linear otimiza uma função objetivo linear sujeita a restrições lineares de desigualdade. A região viável é um politopo convexo e o ótimo sempre fica em um vértice.

O método Simplex resolve programas lineares movendo-se de vértice em vértice do politopo viável, sempre melhorando o objetivo, até que nenhuma melhoria adicional seja possível.

Os multiplicadores de Lagrange transformam um problema de otimização restrita em um sem restrições, incorporando as restrições ao objetivo por meio de multiplicadores.

As condições KKT generalizam os multiplicadores de Lagrange para restrições de desigualdade, fornecendo condições de otimalidade necessárias e suficientes para a otimização restrita.

A programação inteira otimiza objetivos lineares sobre variáveis inteiras ou binárias. O branch and bound é o algoritmo fundamental: ele particiona o conjunto viável e delimita subproblemas usando relaxações lineares.

A programação dinâmica resolve problemas de otimização com subproblemas sobrepostos e subestrutura ótima armazenando soluções para evitar cálculo redundante.

Algoritmos gulosos fazem a melhor escolha local a cada passo sem reconsiderar decisões passadas. Quando a propriedade da escolha gulosa vale, eles encontram o ótimo global eficientemente.

Grafos modelam relações entre objetos. Aprenda os conceitos-chave, os tipos de grafos, e as estruturas de dados usadas para representá-los antes de estudar algoritmos de grafos.

O algoritmo de Dijkstra encontra o caminho mais curto de um vértice origem até todos os outros vértices em um grafo ponderado com pesos de aresta não negativos.