🤖 AI

AI-Assisted Discovery of Convex Relaxations via Dual Agents

Dit artikel presenteert een door AI ondersteund framework dat gebruikmaakt van duale agenten om verbeterde convexe relaxaties voor niet-convexe optimalisatieproblemen te ontdekken en rigoureus te certificeren, waarbij de onderste grenzen voor de eerste autocorrelatie-ongelijkheid en de Erdős minimum-overlap constante succesvol zijn aangescherpt.

Oorspronkelijke auteurs: Sungyoon Kim, Mert Pilanci

Gepubliceerd 2026-07-01

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Sungyoon Kim, Mert Pilanci

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert het absolute "worst-case scenario" te vinden voor een complexe wiskundige puzzel. In de wereld van de wiskunde zijn er twee manieren om te bewijzen hoe slecht een situatie kan uitpakken:

De "Laat het me zien"-benadering (Bovengrens): Je bouwt één specifiek, vreselijk voorbeeld dat bewijst dat de situatie zó erg kan zijn. Het is alsof je één specifieke verkeersopstopping vindt om te bewijzen dat "het verkeer 2 uur kan duren om naar huis te rijden."
De "Bewijs dat het onmogelijk is"-benadering (Ondergrens): Je moet bewijzen dat de situatie, ongeacht wat je probeert, nooit beter kan zijn dan een bepaald punt. Het is alsof je bewijst dat "ongeacht hoe je rijdt, je nooit in minder dan 45 minuten thuis kunt zijn."

Dit artikel gaat over de tweede, veel moeilijkere benadering. De auteurs hebben een team van AI-agenten gebruikt die fungeerden als een super-slimme wiskundige detective-eenheid om betere "onmogelijke" bewijzen te vinden.

Het Team: Twee AI-agenten die Samenwerken

In plaats van één AI die alles probeert te doen, hebben de auteurs een "dual-agent" systeem opgezet, zoals een creatieve schrijver en een strenge redacteur in een lus.

De Coding Agent (De Uitvinder): Deze agent is de creatieve een. Zijn taak is om naar een wiskundig probleem te kijken en te zeggen: "Ik denk dat als we deze nieuwe regel of beperking toevoegen, we kunnen bewijzen dat het antwoord zelfs nog hoger is." Hij schrijft computercode om deze nieuwe regel te testen. Denk aan een architect die een nieuwe, strakkere blauwdruk tekent voor een gebouw.
De Theory Agent (De Scepticus): Deze agent is de strenge redacteur. Hij leest de nieuwe blauwdruk en vraagt: "Is deze regel eigenlijk waar voor elke mogelijke casus? Of heb je een fout gemaakt?" Hij probeert de regel te breken door een tegenvoorbeeld te vinden (een specifieke casus waarin de regel faalt).
- Als de Theory Agent een fout vindt, stuurt hij de blauwdruk terug naar de Coding Agent om de fout te herstellen.
- Als de Theory Agent ervan overtuigd is dat de regel solide is, geeft hij groen licht.

Het Doel: Het Net Aanhalen

De problemen waar zij zich mee bezighielden, gaan over Autocorrelatie-ongelijkheden. In eenvoudige termen zijn dit regels over hoeveel een vorm overlapt met een kopie van zichzelf wanneer deze verschoven wordt.

Stel je voor dat je een vage wolk hebt (een functie). Je wilt weten: "Als ik deze wolk over zichzelf heen schuif, wat is de minimale overlap die ik kan garanderen, ongeacht hoe ik de wolk vorm?"

De Oude Manier: Eerdere onderzoekers hadden een "net" (een wiskundige relaxatie) dat alle mogelijke wolken ving, maar het net had grote gaten. Het antwoord dat zij kregen was een beetje losjes (bijv. "De overlap is ten minste 1,28").
De Nieuwe Manier: De AI-agenten werkten samen om de gaten in het net te dichten. Ze voegden nieuwe, wiskundig bewezen regels toe die het net strakker maakten.
- Voor het eerste probleem verstrakten ze het net genoeg om te bewijzen dat de overlap daadwerkelijk ten minste 1,2937 is (omhoog van 1,28).
- Voor het tweede probleem bewezen ze dat de overlap ten minste 0,37912 is (omhoog van 0,379005).

Deze getallen lijken klein, maar in de wereld van de hogere wiskunde is het verbeteren van een constante met zelfs maar een fractie een enorme overwinning. Het betekent dat ze een nauwkeuriger "vloer" hebben gevonden waar het antwoord nooit onder kan zakken.

De "Gouden Standaard" Check

Het meest indrukwekkende deel van dit artikel is hoe ze ervoor hebben gezorgnd dat ze niet hebben valsgespeeld.

Wanneer een AI een wiskundig probleem oplost, gebruikt het meestal een rekenmachine die getallen afrondt, wat kan leiden tot kleine fouten. Als je naar boven afrondt, kun je per ongeluk beweren dat een getal hoger is dan het in werkelijkheid is.

Om dit op te lossen, gebruikten de auteurs een Dual Certificate.

Denk aan de Coding Agent die een brug bouwt.
De Theory Agent controleert de wiskunde.
Maar om 100% zeker te weten dat de brug niet instort, gebruikten ze een speciale "intervalrekening"-check. Dit is als het meten van de brug met een liniaal die een kleine foutmarge ingebouwd heeft, om te garanderen dat zelfs met de slechtst denkbare afronding, de brug nog steeds veilig is.

Ze zeiden niet alleen: "De computer zegt 1,2937." Ze produceerden een specifiek, verifieerbaar wiskundig "bewijs van ontvangst" (een dual-feasible point) dat bewijst, zonder enige twijfel, dat het antwoord inderdaad ten minste zo hoog is.

Samenvatting

Kortom, dit artikel beschrijft een nieuwe manier om AI voor zuivere wiskunde te gebruiken. In plaats van alleen maar antwoorden te raden, creëerden ze een lus waarin één AI nieuwe wiskundige regels verzint, en een andere AI deze rigoureus test om te garanderen dat ze waar zijn. Door dit te doen, hebben ze succesvol de wiskundige "veiligheidsnetten" voor twee beroemde, langlopende problemen verstrakkt, waarmee ze hebben bewezen dat de antwoorden iets hoger (en preciezer) zijn dan eerder gecertificeerd.

Technische Samenvatting: AI-gestuurde ontdekking van convexe relaxaties via duale agenten

1. Probleemstelling

Het artikel behandelt de uitdaging om gecertificeerde ondergrenzen te verbeteren voor scherpe constante ongelijkheden in de functionele analyse, met een specifieke focus op niet-convexe optimalisatieproblemen waarbij het doel is om het infimum van een score te vinden over een oneindig-dimensionale ruimte van toegestane functies.

De auteurs richten zich op twee specifieke constanten die zijn bestudeerd door Georgiev et al. (2025):

De eerste autocorrelatie-ongelijkheid (C6.2): Een constante voortvloeiend uit de additieve combinatoriek gerelateerd aan Sidon-verzamelingen, gedefinieerd door de ongelijkheid:
$\max_{-1/2 \le t \le 1/2} \int_{\mathbb{R}} f(t-x)f(x) \, dx \ge C_{6.2} \left( \int_{-1/4}^{1/4} f(x) \, dx \right)^2$
voor alle niet-negatieve $f: \mathbb{R} \to \mathbb{R}$ .
De Erdős Minimum Overlap Constante (C6.5): Een constante die de asymptotica van het minimum overlap-probleem beheerst, gedefinieerd als:
$\sup_{x \in [-2, 2]} \int_{-1}^{1} f(t)g(x+t) \, dt \ge C_{6.5}$
voor niet-negatieve $f, g: [-1, 1] \to [0, 1]$ met $f+g=1$ en $\int f = 1$ .

Hoewel recente AI-gestuurde arbeid er succesvol in is geslaagd bovengrenzen te verbeteren door te zoeken naar extreme constructies (specifieke functies die een grens schenden), is het verbeteren van ondergrenzen een ander verhaal. Een ondergrens moet gelden voor elke toegestane functie, wat een bewijs vereist dat geen enkele functie de score onder een bepaalde waarde kan drijven. Dit wordt doorgaans bereikt door een convexe relaxatie van het oorspronkelijke niet-convexe probleem op te lossen. Hoe strakker de relaxatie (dat wil zeggen, hoe meer geldige restricties worden toegevoegd), hoe sterker de ondergrens.

2. Methodologie: De Dual-Agent Loop

De auteurs implementeren een autoresearch-paradigma met behulp van een human-in-the-loop framework dat wordt aangestuurd door twee gespecialiseerde Large Language Model (LLM) agenten. Het systeem is ontworpen om iteratief geldige restricties te ontdekken en te verifiëren die een convexe relaxatie aanscherpen.

De Agenten

Coding Agent:
- Rol: Stelt nieuwe restricties voor of versterkt bestaande restricties voor het convexe programma.
- Output: Genereert een gewijzigd convex optimalisatieprogramma en een "rigoureus bewijs" (een wiskundig argument) dat rechtvaardigt waarom de nieuwe restrictie geldt voor alle toegestane functies.
- Actie: Implementeert de restrictie in code (met behulp van CVXPY) en lost het programma op om een kandidaat-ondergrens te produceren.
Theory Agent:
- Rol: Fungeert als verifieerder en zoekt naar tegenvoorbeelden.
- Actie: Leest de voorgestelde restrictie en het bijbehorende bewijs. Het analyseert de logica kritisch om te waarborgen dat de restrictie een noodzakelijk gevolg is van de toelatingsvoorwaarden (bijv. $f \ge 0$ ). Cruciaal is dat het actief op zoek gaat naar tegenvoorbeelden—specifieke toegestane functies waarvan de coëfficiënten de voorgestelde restrictie schenden.
- Besluit: Als het bewijs sluitend is en er geen tegenvoorbeeld wordt gevonden, wordt de restrictie geaccepteerd. Als er een fout of tegenvoorbeeld wordt gevonden, wordt het voorstel afgewezen en krijgt de Coding Agent de instructie om een andere aanpak te proberen.

De Verificatie Pipeline

Om te garanderen dat het uiteindelijke resultaat een gecertificeerde grens is (wiskundig bewezen, niet slechts numeriek geschat), maakt het systeem gebruik van een rigoureus duaal certificeringsproces:

Duale Haalbaarheid: Het systeem construeert de duale vorm van het convexe programma.
Intervalrekening: Het vindt een duaal haalbaar punt $\lambda$ en verifieert de haalbaarheid en de duale objectieve waarde met behulp van rigoureuze intervalrekening. Dit houdt rekening met afrondingsfouten van floating-point getallen en irrationele probleemdata (bijv. trigonometrische momenten).
Certificering: Door zwakke dualiteit bewijst een geldige duaal punt $\lambda$ met objectieve waarde $\beta$ dat het primaire optimum (en dus de ware constante) ten minste $\beta$ is. De gerapporteerde ondergrens is het onderste eindpunt van een geverifieerde insluiting.

Rol van de Mens

Een menselijke onderzoeker voert een laatste beoordeling en compactificatie uit. De agent-loop accumuleert vaak redundante restricties. De mens beoordeelt het uiteindelijke programma, verwijdert overbodige restricties om een minimale, leesbare formulering te creëren, en verifieert de wiskundige argumenten voordat de definitieve certificering plaatsvindt.

3. Belangrijkste Bijdragen

Paradigmaverschuiving: Het artikel demonstreert een nieuwe toepassing van AI-agenten op de ontdekking van convexe relaxaties in plaats van enkel het zoeken naar extreme voorbeelden. Het richt zich op de "ondergrens"-zijde van ongelijkheden, wat het bewijzen van universele kwantificatie vereist (geldigheid voor alle functies) in plaats van existentiële kwantificatie (het vinden van één functie).
Dual-Agent Framework: Het introduceert een specifieke loop waarbij een coding agent restricties voorstelt en een theory agent de geldigheid verifieert en op zoek gaat naar tegenvoorbeelden, wat het iteratieve verfijnen van wiskundige relaxaties effectief automatiseert.
Rigoureuze Certificering: De integratie van intervalrekening en duale haalbaarheidscontroles zorgt ervoor dat de verbeterde grenzen wiskundig gecertificeerd zijn, onafhankelijk van de floating-point precisie van de numerieke solver.

4. Resultaten

Het framework werd toegepast op de twee genoemde constanten, waarbij de gecertificeerde ondergrenzen werden verbeterd:

C6.2 (Eerste Autocorrelatie-ongelijkheid):
- Vorige beste ondergrens: 1.28 (Cloninger & Steinerberger, 2017).
- Nieuwe gecertificeerde ondergrens: 1.2937.
- Opmerking: Er bestond voorheen geen convex programma voor dit probleem; de agenten hebben er een vanaf nul opgebouwd.
C6.5 (Erdős Minimum Overlap Constante):
- Vorige beste ondergrens: 0.379005 (White, 2022).
- Nieuwe gecertificeerde ondergrens: 0.37912.
- Opmerking: De agenten vertrokken vanuit het bestaande convexe programma van White en ontdekten twee nieuwe geldige restricties gebaseerd op de Bochner-stelling (die afdwingt dat de momentenreeksen van zowel $f$ als zijn complement $g=1-f$ realiseerbaar zijn door niet-negatieve maten).

Het artikel merkt op dat de bovengrenzen voor deze problemen zijn verbeterd door zoekgebaseerde methoden (bijv. Together AI, 2026), maar dat de ondergrenzen sinds 2022 onveranderd waren gebleven. Dit werk slaagt erin de ondergrenzen vooruit te helpen.

5. Betekenis en Claims

De auteurs claimen dat dit de eerste toepassing is van een autoresearch-stijl agentic loop om gecertificeerde ondergrenzen te verbeteren op deze specifieke ongelijkheden. De betekenis ligt in:

Complementariteit: Het vult bestaand AI-onderzoek dat zich richt op het vinden van extreme voorbeelden (bovengrenzen) aan door de moeilijkere taak van het bewijzen van ondergrenzen via relaxatie aan te pakken.
Autonomie in Ontdekking: De agenten identificeerden succesvol wiskundige eigenschappen (zoals de Bochner-condities voor $f$ en $1-f$ ) die eerdere door mensen ontworpen formuleringen hadden overgeslagen of niet expliciet hadden opgelegd.
Generaliseerbaarheid: Hoewel gedemonstreerd op autocorrelatie-ongelijkheden, stellen de auteurs dat het framework niet specifiek voor deze problemen is. Het is toepasbaar op elk niet-convex optimalisatieprobleem waarbij een ondergrens kan worden uitgedrukt als een convexe relaxatie die wordt aangescherpt door geldige restricties en gecertificeerd via dualiteit (bijv. in optimalisatie, combinatoriek en regeltechniek).

Het artikel sluit bescheiden af door te erkennen dat de geldigheid van de restricties momenteel afhangt van menselijke beoordeling van de wiskundige argumenten in plaats van formele bewijsassistenten (zoals Lean), hoewel zij suggereren dat toekomstige integratie met formele verificatietools de loop volledig autonoom zou kunnen maken.