AI-Assisted Discovery of Convex Relaxations via Dual Agents
06:00 · July 1, 2026 · arXiv cs.AI RSS
Recent work shows that LLM agents can improve sharp-constant inequalities by searching for extremal constructions, which yield upper bounds. We address the complementary side: a lower bound holds for every admissible function and follows from a convex relaxation of the nonconvex problem, with tighter relaxations giving stronger bounds. We instantiate the autoresearch paradigm to discover such relaxations: a coding agent proposes valid tightening constraints, a theory agent verifies each one and searches for counterexamples, and every reported bound is certified by an explicit dual-feasible point checked in rigorous interval arithmetic. On two optimization constants studied by \citet{tao2025alphaevolve} - the first autocorrelation inequality ($C_{6.2}$) and the Erd\H{o}s minimum-overlap constant ($C_{6.5}$) - we improve the certified lower bounds from $1.28$ to $1.2937$ and from $0.379005$ to $0.37912$, respectively.
Summary
Recent work has shown that LLM agents can tighten upper bounds on sharp constants by searching for explicit extremal functions. This paper addresses the complementary task of strengthening lower bounds, which must hold for every admissible function and are obtained by constructing successively tighter convex relaxations of the underlying nonconvex optimization problem. The authors implement an autoresearch loop in which a coding agent proposes additional valid constraints while a paired theory agent checks each proposal for correctness and attempts to find counterexamples. Only constraints that survive this verification step are retained, and every accepted relaxation is certified by an explicit dual-feasible point whose objective value is confirmed with rigorous interval arithmetic.
The method is applied to two constants previously studied through extremal-search techniques. For the first autocorrelation inequality (C6.2), the certified lower bound is raised from 1.28 to 1.2937. For the Erdős minimum-overlap constant (C6.5), the bound improves from 0.379005 to 0.37912. In both cases the new relaxations remain valid over the infinite-dimensional function spaces involved, and the reported values are accompanied by machine-checkable dual certificates rather than numerical solver output alone.
By shifting the search from candidate functions to candidate programs that encode convex relaxations, the dual-agent framework exploits the complementary strengths of code generation and formal verification. The resulting bounds are the first improvements on these particular constants achieved through an automated, self-refining research loop, illustrating how LLM agents can contribute to certified results in functional analysis and continuous optimization.
Why it matters
This fundamental research is highly relevant for AI researchers and optimization specialists in the Netherlands, showcasing a novel application of LLM agents in automated mathematical discovery. It provides advanced methodologies that Dutch R&D institutions can leverage for complex problem-solving and algorithm development.
