AI-Assisted Discovery of Convex Relaxations via Dual Agents
This work provides a novel automated method for tightening convex relaxations, benefiting researchers in optimization and inequality theory, though the improvements are incremental.
The paper introduces an AI-assisted framework using LLM agents to discover convex relaxations that improve lower bounds for sharp-constant inequalities. They achieve certified improvements on two optimization constants: from 1.28 to 1.2937 for the first autocorrelation inequality and from 0.379005 to 0.37912 for the Erdős minimum-overlap constant.
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ő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.