OptEvolve: Hardware-Aware Discovery of Certified Optimization Algorithms

Canonical optimization algorithms each excel in distinct regimes, yet identifying the optimal combination of formulation, algorithm, and hardware strategy for a target instance remains non-obvious. While recent algorithmic discovery frameworks utilize LLM-guided evolutionary search, naive source-code mutation fails to provide structural guarantees of mathematical convergence. We introduce OptEvolve, an automated framework for optimization modeling and verified solver synthesis. OptEvolve synthesizes the optimal solver for a target problem instance by co-optimizing mathematical formulations, algorithmic schemes, and hardware-level operator implementations. Solvers are evolved as typed genomes in a monotone-operator calculus, using a symbolic gate to discard invalid candidates prior to compilation while admitting custom operator kernels under strict behavioral contracts. An empirical cost model guides the search across hyperparameters and stopping criteria, while optimizing GPU iteration fusion tiles on target devices. OptEvolve matches or beats domain-specialist solvers on structured problems and outperforms general-purpose baselines where no specialist exists. Furthermore, its targeted CUDA fusion tiles outperform XLA by up to $2.7\times$, and the framework generalizes effectively across unseen, held-out QP, LP, and SOCP benchmarks.