🤖 AI

AI-Assisted Discovery of Convex Relaxations via Dual Agents

Dieses Paper präsentiert ein KI-gestütztes Framework unter Verwendung dualer Agenten, um verbesserte konvexe Relaxationen für nichtkonvexe Optimierungsprobleme zu entdecken und rigoros zu zertifizieren, wobei die unteren Schranken für die erste Autokorrelationsungleichung sowie die Erdős-Minimum-Overlap-Konstante erfolgreich verschärft wurden.

Ursprüngliche Autoren: Sungyoon Kim, Mert Pilanci

Veröffentlicht 2026-07-01

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Sungyoon Kim, Mert Pilanci

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, das absolute „Worst-Case-Szenario“ für ein komplexes mathematisches Rätsel zu finden. In der Welt der Mathematik gibt es zwei Wege, um zu beweisen, wie schlimm eine Situation werden kann:

Der „Zeig-mir-es“-Ansatz (Obere Schranke): Sie konstruieren ein spezifisches, schreckliches Beispiel, das beweist, dass die Situation so schlimm sein kann. Es ist, als fände man einen spezifischen Stau, um zu beweisen, dass „der Verkehr 2 Stunden dauern kann, um nach Hause zu kommen“.
Der „Beweise, dass es unmöglich ist“-Ansatz (Untere Schranke): Sie müssen beweisen, dass die Situation unabhängig davon, was man versucht, niemals besser als ein bestimmter Punkt sein kann. Es ist, als würde man beweisen, dass man „egal wie man fährt, niemals in weniger als 45 Minuten zu Hause sein kann“.

In dieser Arbeit geht es um den zweiten, viel schwierigeren Ansatz. Die Autoren haben ein Team von KI-Agenten eingesetzt, die wie eine superintelligente mathematische Detektiv-Truppe agieren, um bessere „Unmöglichkeits“-Beweise zu finden.

Das Team: Zwei KI-Agenten, die zusammenarbeiten

Anstatt eines einzelnen KI-Agenten, der alles allein versucht, haben die Autoren ein „Dual-Agent“-System aufgebaut, vergleichbar mit einem kreativen Autor und einem strengen Lektor, die in einer Schleife arbeiten.

Der Coding-Agent (Der Erfinder): Dieser Agent ist der kreative Part. Seine Aufgabe ist es, sich ein mathematisches Problem anzusehen und zu sagen: „Ich denke, wenn wir diese neue Regel oder Einschränkung hinzufügen, können wir beweisen, dass das Ergebnis noch höher ausfällt.“ Er schreibt Computercode, um diese neue Regel zu testen. Denken Sie an einen Architekten, der einen neuen, präziseren Bauplan für ein Gebäude zeichnet.
Der Theory-Agent (Der Skeptiker): Dieser Agent ist der strenge Lektor. Er liest den neuen Bauplan und fragt: „Ist diese Regel tatsächlich für jeden möglichen Fall wahr? Oder haben Sie einen Fehler gemacht?“ Er versucht, die Regel zu Fall zu bringen, indem er ein Gegenbeispiel findet (einen spezifischen Fall, in dem die Regel nicht gilt).
- Wenn der Theory-Agent einen Fehler findet, schickt er den Bauplan an den Coding-Agent zurück, damit dieser ihn korrigiert.
- Wenn der Theory-Agent davon überzeugt ist, dass die Regel solide ist, gibt er das grüne Licht.

Das Ziel: Das Netz enger ziehen

Die Probleme, mit denen sie sich befasst haben, drehen sich um Autokorrelations-Ungleichungen. Vereinfacht gesagt sind dies Regeln darüber, wie stark eine Form mit einer Kopfe ihrer selbst überlappt, wenn man sie verschiebt.

Stellen Sie sich eine diffuse Wolke (eine Funktion) vor. Sie wollen wissen: „Wenn ich diese Wolke über sich selbst gleiten lasse, was ist das minimale Maß an Überlappung, das ich garantieren kann, egal wie ich die Wolke forme?“

Der alte Weg: Frühere Forscher hatten ein „Netz“ (eine mathematische Relaxation), das alle möglichen Wolken auffing, aber das Netz hatte große Löcher. Das Ergebnis, das sie erhielten, war etwas vage (z. B. „Die Überlappung beträgt mindestens 1,28“).
Der neue Weg: Die KI-Agenten haben zusammengearbeitet, um die Löcher im Netz zu stopfen. Sie haben neue, mathematisch bewiesene Regeln hinzugefügt, die das Netz enger machten.
- Für das erste Problem haben sie das Netz so weit verdichtet, dass sie bewiesen haben, dass die Überlappung tatsächlich mindestens 1,2937 beträgt (statt bisher 1,28).
- Für das zweite Problem haben sie bewiesen, dass die Überlappung mindestens 0,37912 beträgt (statt bisher 0,379005).

Diese Zahlen mögen klein erscheinen, aber in der Welt der Hochmathematik ist die Verbesserung einer Konstante um selbst einen winzigen Bruchteil ein gewaltiger Sieg. Es bedeutet, dass sie einen präziseren „Boden“ gefunden haben, unter den die Antwort niemals fallen kann.

Der „Goldstandard“-Check

Der beeindruckendste Teil dieser Arbeit ist, wie sie sichergestellt haben, dass sie nicht geschummelt haben.

Wenn eine KI ein mathematisches Problem löst, verwendet sie normalerweise einen Taschenrechner, der Zahlen rundet, was zu winzigen Fehlern führen kann. Wenn man aufrundet, behauptet man versehentlich, eine Zahl sei höher, als sie tatsächlich ist.

Um dies zu beheben, haben die Autoren ein Dual-Zertifikat verwendet.

Betrachten Sie den Coding-Agenten als jemanden, der eine Brücke baut.
Der Theory-Agent prüft die Mathematik.
Aber um zu 100 % sicher zu sein, dass die Brücke nicht einstürzt, haben sie eine spezielle „Intervallarithmetik“-Prüfung verwendet. Dies ist wie das Messen der Brücke mit einem Lineal, das eine winzige Fehlermarge eingebaut hat, um sicherzustellen, dass die Brücke selbst bei der ungünstigsten Rundung noch stabil ist.

Sie sagten nicht einfach: „Der Computer sagt 1,2937.“ Sie lieferten einen spezifischen, verifizierbaren mathematischen „Beleg“ (einen dual-zulässigen Punkt), der ohne jeden Zweifel beweist, dass die Antwort tatsächlich mindestens so hoch ist.

Zusammenfassung

Kurz gesagt beschreibt diese Arbeit einen neuen Weg, KI für die reine Mathematik einzusetzen. Anstatt nur Antworten zu erraten, haben sie eine Schleife geschaffen, in der eine KI neue mathematische Regeln erfindet und eine andere KI diese rigoros testet, um sicherzustellen, dass sie wahr sind. Durch dies ist es ihnen gelungen, die mathematischen „Sicherheitsnetze“ für zwei berühmte, langjährige Probleme zu straffen und zu beweisen, dass die Antworten etwas höher (und präziser) sind, als bisher zertifiziert worden waren.

Technisches Resümee: KI-gestützte Entdeckung konvexer Relaxationen mittels dualer Agenten

1. Problemstellung

Die Arbeit befasst sich mit der Herausforderung, die zertifizierten unteren Schranken für scharfe Konstanten in der Funktionalanalysis zu verbessern, wobei der Schwerpunkt auf nichtkonvexen Optimierungsproblemen liegt, bei denen das Ziel darin besteht, das Infimum eines Scores über einem unendlichdimensionalen Raum zulässiger Funktionen zu finden.

Die Autoren adressieren zwei spezifische Konstanten, die von Georgiev et al. (2025) untersucht wurden:

Die erste Autokorrelations-Ungleichung (C6.2): Eine Konstante aus der additiven Kombinatorik im Zusammenhang mit Sidon-Mengen, definiert durch die Ungleichung:
$\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$
für alle nicht-negativen Funktionen $f: \mathbb{R} \to \mathbb{R}$ .
Die Erdős Minimum Overlap Konstante (C6.5): Eine Konstante, welche die Asymptotik des Minimum-Overlap-Problems steuert, definiert als:
$\sup_{x \in [-2, 2]} \int_{-1}^{1} f(t)g(x+t) \, dt \ge C_{6.5}$
für nicht-negative $f, g: [-1, 1] \to [0, 1]$ mit $f+g=1$ und $\int f = 1$ .

Während jüngste KI-gestützte Arbeiten erfolgreich obere Schranken durch die Suche nach extremalen Konstruktionen (spezifische Funktionen, die eine Schranke verletzen) verbessert haben, ist die Verbesserung von unteren Schranken ein grundlegend anderes Unterfangen. Eine untere Schranke muss für jede zulässige Funktion gelten, was einen Beweis erfordert, dass keine Funktion den Score unter einen bestimmten Wert drücken kann. Dies wird typischerweise durch das Lösen eines konvexen Relaxationsproblems des ursprünglichen nichtkonvexen Problems erreicht. Je enger die Relaxation ist (d. h. je mehr gültige Nebenbedingungen hinzugefügt werden), desto stärker ist die untere Schranke.

2. Methodik: Der Dual-Agent-Loop

Die Autoren implementieren ein Autoresearch-Paradigma unter Verwendung eines Human-in-the-Loop-Frameworks, das von zwei spezialisierten Large Language Model (LLM) Agenten gesteuert wird. Das System ist darauf ausgelegt, iterativ gültige Nebenbedingungen zu entdecken und zu verifizieren, um eine konvexe Relaxation zu verschärfen.

Die Agenten

Coding Agent:
- Rolle: Schlägt neue Nebenbedingungen vor oder verstärkt bestehende Nebenbedingungen für das konvexe Programm.
- Ausgabe: Erzeugt ein modifiziertes konvexes Optimierungsprogramm und einen „rigorosen Beweis“ (ein mathematisches Argument), der rechtfertigt, warum die neue Nebenbedingung für alle zulässigen Funktionen gilt.
- Aktion: Implementiert die Nebenbedingung im Code (unter Verwendung von CVXPY) und löst das Programm, um eine Kandidat-untere Schranke zu erzeugen.
Theory Agent:
- Rolle: Agiert als Verifizierer und Sucher nach Gegenbeispielen.
- Aktion: Analysiert den vorgeschlagenen Beweis und die Nebenbedingung kritisch, um sicherzustellen, dass die Nebenbedingung eine notwendige Konsequenz der Zulässigkeitsbedingungen (z. B. $f \ge 0$ ) ist. Entscheidend ist, dass er aktiv nach Gegenbeispielen sucht – also spezifischen zulässigen Funktionen, deren Koeffizienten die vorgeschlagene Nebenbedingung verletzen.
- Entscheidung: Wenn der Beweis fundiert ist und kein Gegenbeispiel gefunden wurde, wird die Nebenbedingung akzeptiert. Falls ein Fehler oder ein Gegenbeispiel gefunden wird, wird der Vorschlag abgelehnt und der Coding Agent angewiesen, einen anderen Ansatz zu versuchen.

Die Verifizierungspipeline

Um sicherzustellen, dass das Endergebnis eine zertifizierte Schranke ist (mathematisch bewiesen und nicht nur numerisch geschätzt), nutzt das System einen rigorosen dualen Zertifizierungsprozess:

Duale Zulässigkeit: Das System konstruiert das Dual des konvexen Programms.
Intervallarithmetik: Es findet einen dual-zulässigen Punkt $\lambda$ und verifiziert dessen Zulässigkeit sowie den dualen Zielfunktionswert mittels rigoroser Intervallarithmetik. Dies berücksichtigt Rundungsfehler bei Gleitkommazahlen und irrationale Problemdaten (z. B. trigonometrische Momente).
Zertifizierung: Durch die schwache Dualität beweist ein gültiger dualer Punkt $\lambda$ mit dem Zielfunktionswert $\beta$ , dass das primale Optimum (und damit die wahre Konstante) mindestens $\beta$ beträgt. Die endgültig berichtete Schranke ist der untere Endpunkt eines verifizierten Enclosures.

Rolle des Menschen

Ein menschlicher Forscher führt eine abschließende Überprüfung und Kompaktierung durch. Der Agenten-Loop häuft oft redundante Nebenbedingungen an. Der Mensch überprüft das finale Programm, entfernt unnötige Nebenbedingungen, um eine minimale, lesbare Formulierung zu erstellen, und verifiziert die mathematischen Argumente vor der endgültigen Zertifizierung.

3. Kernbeiträge

Paradigmenwechsel: Die Arbeit demonstriert eine neuartige Anwendung von KI-Agenten zur Entdeckung konvexer Relaxationen anstatt lediglich nach extremalen Beispielen zu suchen. Sie adresset die „Untere Schranken“-Seite von Ungleichheiten, die den Beweis einer universellen Quantifizierung (Gültigkeit für alle Funktionen) erfordert, statt einer existenziellen Quantifizierung (Finden einer Funktion).
Dual-Agent-Framework: Es führt einen spezifischen Loop ein, in dem ein Coding Agent Nebenbedingungen vorschlägt und ein Theory Agent die Gültigkeit prüft und nach Gegenbeispielen sucht, was die iterative Verfeinerung mathematischer Relaxationen automatisiert.
Rigorose Zertifizierung: Die Integration von Intervallarithmetik und Dual-Feasibility-Checks stellt sicher, dass die verbesserten Schranken mathematisch zertifiziert sind, unabhängig von der numerischen Präzision des Solvers.

4. Ergebnisse

Das Framework wurde auf die beiden oben genannten Konstanten angewendet und verbesserte die zertifizierten unteren Schranken:

C6.2 (Erste Autokorrelations-Ungleichung):
- Bisher beste untere Schranke: 1.28 (Cloninger & Steinerberger, 2017).
- Neue zertifizierte untere Schranke: 1.2937.
- Anmerkung: Zuvor existierte kein konvexes Programm für dieses Problem; die Agenten konstruierten eines von Grund auf neu.
C6.5 (Erdős Minimum Overlap Konstante):
- Bisher beste untere Schranke: 0.379005 (White, 2022).
- Neue zertifizierte untere Schranke: 0.37912.
- Anmerkung: Die Agenten starteten mit dem bestehenden konvexen Programm von White und entdeckten zwei neue gültige Nebenbedingungen basierend auf dem Bochner-Theorem (welches erzwingt, dass die Momentenfolgen sowohl von $f$ als auch von dessen Komplement $g=1-f$ durch nicht-negative Maße realisierbar sind).

Die Arbeit stellt fest, dass die oberen Schranken für diese Probleme durch suchbasierte Methoden (z. B. Together AI, 2026) verbessert wurden, die unteren Schranken jedoch seit 2022 stagnierten. Diese Arbeit konnte die unteren Schranken erfolgreich voranbringen.

5. Bedeutung und Ansprüche

Die Autoren behaupten, dies sei die erste Verwendung eines Autoresearch-ähnlichen agentischen Loops zur Verbesserung zertifizierter unterer Schranken für diese spezifischen Ungleichheiten. Die Bedeutung liegt in:

Komplementarität: Es ergänzt die bestehende KI-Forschung, die sich auf das Finden von extremalen Beispielen (obere Schranken) konzentriert, indem es das schwierigere Problem der Beweisführung für untere Schranken via Relaxation angeht.
Autonomie in der Entdeckung: Die Agenten identifizierten erfolgreich mathematische Eigenschaften (wie die Bochner-Bedingungen für $f$ und $1-f$ ), die zuvor von Menschen entworfene Formulierungen entweder übersehen oder nicht explizit auferlegt hatten.
Generalisierbarkeit: Obwohl es am Beispiel der Autokorrelations-Ungleichungen demonstriert wurde, geben die Autoren an, dass das Framework nicht auf diese Probleme beschränkt ist. Es lässt sich auf jedes nichtkonvexe Optimierungsproblem anwenden, bei dem eine untere Schranke durch eine konvexe Relaxation, die durch zusätzliche Nebenbedingungen verschärft wird, ausgedrückt und durch Dualität zertifiziert werden kann (z. B. in der Optimierung, Kombinatorik und Regelungstechnik).

Die Arbeit schließt bescheiden mit dem Hinweis, dass die Validität der Nebenbedingungen derzeit noch auf der menschlichen Überprüfung der mathematischen Argumente beruht und nicht auf formalen Proof Assistants (wie Lean), deutet jedoch darauf an, dass eine zukünftige Integration mit formalen Verifizierungswerkzeugen den Loop vollständig autonom machen könnte.