Discrete & global optimization
Parent: optimization
When there's no gradient (discrete choices) or many local minima (rugged landscape) — you search, not descend.
Combinatorial / integer
- Integer / mixed-integer programming (MILP): LP relaxation + branch-and-bound + cutting planes (the workhorse); exact but exponential worst-case.
- SAT / CSP solving: DPLL + CDCL (conflict-driven clause learning) — see csp-formalization; the same collapse/backjump/no-good machinery.
- Matroids / submodularity / greedy: some combinatorial problems have structure making greedy optimal or
1−1/e-approximate (submodular maximization). - Approximation algorithms / LP rounding for NP-hard problems.
Global optimization (continuous, non-convex, many minima)
- Simulated annealing (temperature schedule = smooth→sharp landscapes; the continuation idea);
- Evolutionary / genetic, CMA-ES (population + selection + variation);
- Particle swarm, basin hopping.
Black-box / derivative-free
- Nelder–Mead (simplex);
- Bayesian optimization: fit a Gaussian-process surrogate, optimize an acquisition function (explore/exploit) — sample-efficient for expensive black boxes (hyperparameter tuning);
- Bandits (the 1-step explore/exploit core).
The theme
No smoothness → exploration + selection replaces descent. This is where optimization becomes search over a combinatorial/rugged space — exactly the regime our agent harness lives in (infinite branching, unsound evaluation → MCTS + soft constraints, non-determinism-and-infinite-branching).