Der Beweis zum Mitnehmen verständlich erklärt

Ein Lieferdienst sucht für sein Lager den Ort mit dem kürzesten Weg zum fernsten Kunden. Er kann nicht jeden Ort ausprobieren. Hier lesen Sie, wie man den Fehler einer gefundenen Lösung eingrenzt, ohne die beste zu kennen, und warum das nicht immer geht.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein Lager für den fernsten Kunden

Ein Lieferdienst sucht einen Standort für sein Lager. Die Kunden sind über eine Karte verteilt. Der Weg zum am weitesten entfernten Kunden soll möglichst kurz sein. Zeichnet man um das Lager einen Kreis bis zu diesem Kunden, liegen alle Kunden im Kreis. Gesucht ist also der kleinste Kreis um alle Kunden.

Alle Standorte durchzuprobieren geht nicht, denn es gibt unendlich viele. Also wählt man einen Ort und zeichnet den Kreis. Der beste Kreis ist höchstens so groß wie dieser (eine Obergrenze). Wie weit ist der Kreis noch vom besten entfernt? Ohne den besten zu kennen, scheint das unmöglich.

Die Zahlen auf dieser Seite stammen aus einem Programm zum Ausprobieren im Browser, kurz Demo. Es arbeitet mit einem vereinfachten Rechenbild: zufällig erzeugte Kundenwolken, Luftlinie, keine echten Daten. Der Knopf „Demo ausprobieren“ am Ende dieses Teils öffnet es. Zum Verstehen brauchen Sie es nicht.

Die zweite Zahl, von unten

Es gibt einen Kniff, der eine zweite Zahl von unten liefert, eine Untergrenze. Stellen Sie sich jeden Kunden als Stein auf der Karte vor. Auf die Steine streuen Sie einen Beutel Sand, beliebig viel auf jeden. Dort, wo die Karte im Gleichgewicht läge, ist der Schwerpunkt. Gerechnet wird so: Man quadriert den Abstand jedes Steins zum Schwerpunkt, gewichtet ihn mit dem Sand auf dem Stein, bildet den Durchschnitt und zieht die Wurzel. Das Quadrieren lässt weit entfernten Sand stärker zählen: Ein Abstand von 2 zählt 4, ein Abstand von 3 zählt 9.

Warum kann der beste Kreis nicht kleiner sein? Jeder Stein liegt höchstens einen Radius von der Mitte des besten Kreises entfernt. Mit dieser Mitte als Bezugspunkt ergibt die Rechnung von oben also höchstens den Radius. Mit dem Schwerpunkt als Bezugspunkt ergibt sie nie mehr: Schiebt man den Bezugspunkt vom Schwerpunkt weg, kommt zum Durchschnitt der Quadrate genau das Quadrat der Verschiebung hinzu. Also liegt die Untergrenze unter dem Radius, wie man den Sand auch verteilt.

Angenommen, zwei Kunden liegen 10 km auseinander und tragen gleich viel Sand. Der Schwerpunkt liegt in der Mitte, beide Steine sind 5 km entfernt. Quadriert ergibt das je 25, im Durchschnitt 25, die Wurzel daraus ist 5. Die Untergrenze ist also 5 km, genau der Radius des kleinsten Kreises um die beiden. Für alle Kunden zusammen gibt es eine Sandverteilung, bei der die Untergrenze den besten Kreis genau trifft. Man kennt sie vorher nicht. Das Verfahren im nächsten Abschnitt sucht sie.

Die Lücke ist der Beweis

Ein Vergleich: Ein Handwerker bietet an, Ihr Dach für einen bestimmten Betrag zu decken. Ein Sachverständiger rechnet vor, dass es unter einem etwas niedrigeren Betrag nicht geht. Liegen beide Beträge dicht beieinander, kann weiteres Suchen höchstens diesen Unterschied sparen.

Beim Lager steht oben der gefundene Kreis, das Angebot. Unten steht die Untergrenze, die Rechnung des Sachverständigen. Der beste Kreis liegt dazwischen, und der Unterschied heißt Lücke. Ist sie klein, ist der gefundene Kreis nah am besten, ohne dass man den besten gesehen hat. Jeder kann beide Zahlen nachrechnen. Das ist der Beweis zum Mitnehmen: Man kann ihn jemandem zeigen, der der eigenen Rechnung nicht traut.

Die Lücke schrumpft so: Man legt mehr Sand auf den Kunden, der vom Lager am weitesten entfernt liegt. Das hebt die Untergrenze am stärksten, denn weit entfernter Sand zählt am stärksten. Das Lager setzt man in den Schwerpunkt des Sandes, es rückt dabei auf diesen Kunden zu. Dann wiederholt man das. In der Beispielwolke der Demo (zwanzig Kunden, zweihundert Wiederholungen) betrug die Lücke gut ein halbes Prozent der Obergrenze.

Der Haken: der Beweis ist grob

Die Lücke setzt sich aus zwei Abständen zusammen: vom gefundenen Kreis zum besten und vom besten zur Untergrenze. In der Messung der Demo (15 zufällig erzeugte Kundenwolken) war der erste Abstand im Lauf der Rechenschritte typischerweise etwa halb so groß wie die Lücke. Die Lücke zeigt also etwa doppelt so viel Fehler an, wie wirklich da ist.

Wenn die Schüssel fehlt

Denken Sie sich die Kreisgröße für jeden Standort als Höhe über der Karte. Hier ergibt sich eine Schüssel ohne Nebenmulden: Eine Murmel rollt von jedem Punkt zum tiefsten Punkt und bleibt nirgends hängen. In der Demo endeten alle hundert Suchläufe je Wolke nahe am besten Kreis, mit einem Radius höchstens ein Tausendstel darüber. Die Schüssel sorgt dafür, dass die Suche nicht hängen bleibt. Eine Untergrenze liefert erst der Sand.

Ändern wir die Frage: Der Kreis muss nur die meisten Kunden umschließen, einzelne entlegene dürfen draußen bleiben. Nun entscheidet man für jeden Kunden Ja oder Nein, statt stufenlos zu verschieben. Jede Auswahl der Kunden draußen hat ihren eigenen besten Kreis. Im Höhenbild ist das je eine Mulde, dazwischen liegen Berge. Das Verfahren mit dem Sand liefert hier im Allgemeinen keine Untergrenze, die billig auszurechnen ist und nah am Besten liegt.

Ein einfaches Verfahren wählt die nächsten Kunden (so viele, wie der Kreis umschließen muss), zeichnet deren kleinsten Kreis und beginnt von dessen Mitte neu, bis sich nichts mehr ändert. Die Demo startet es an hundert zufälligen Orten. Bei zwanzig Kunden (vier dürfen draußen bleiben) endete in jeder gemessenen Wolke mehr als die Hälfte der Starts nicht beim besten Kreis.

Als Beweis bliebe, alle Möglichkeiten zu prüfen. In der Ebene hilft ein Trick: Ein Kreis ist durch drei Punkte auf seinem Rand festgelegt, oft schon durch zwei. Also genügt es, alle Kreise durch zwei oder drei Kunden zu prüfen, bei vierzig Kunden gut zehntausend. Hat jeder Kunde zehn Angaben statt zwei Ortsangaben, legen bis zu elf Punkte eine Kugel fest. Dann gibt es bei vierzig Kunden mehr als zwei Milliarden Möglichkeiten.

Häufige Missverständnisse

• „Eine kleine Lücke heißt, der gefundene Kreis ist der beste.“ Nein. Der beste Kreis liegt irgendwo in der Lücke. Man weiß nur, wie weit er höchstens entfernt ist.
• „Eine Schüssel bedeutet automatisch einen Beweis.“ Nein. Beim Kreis um alle Kunden gibt es eine Sandverteilung, die den besten Kreis genau trifft. Bei anderen Schüsselaufgaben muss es sie nicht geben.

Woran Sie das im Alltag erkennen

• Jemand nennt ein Ergebnis „fast optimal“, aber niemand sagt, wo die Untergrenze liegt. Dann wissen Sie nicht, ob Sie wenig oder viel verschenken.
• Eine Aufgabe besteht aus vielen Ja/Nein-Entscheidungen, etwa wer welche Tour fährt. Ein billiger Beweis fehlt dort im Allgemeinen.

Was Sie mitnehmen

• Fragen Sie bei jedem Ergebnis nach einer zweiten Zahl von der anderen Seite und danach, wer sie nachrechnen kann.
• Ein billiger Beweis hängt an der Aufgabe: Stufenloses Verschieben mit passender Sandverteilung gibt ihn, eine Ja/Nein-Auswahl im Allgemeinen nicht.
• Fehlt ein billiger Beweis, bleibt das teure Prüfen aller Möglichkeiten oder die Suche von mehreren Startpunkten. Treffen alle denselben Wert, ist das nur ein Hinweis.

Wie ernst ist das Rechenbild zu nehmen?

Die Messzahlen gelten nur für diese zufällig erzeugten Kundenwolken und die benutzten einfachen Verfahren, nicht für ein bestimmtes Standortprogramm.

Der Knopf „Weiter zum Fachteil“ führt zum zweiten Teil mit Formeln und Messwerten.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Aufgabe: Gegeben sind Punkte \(x_1, \dots, x_n \in \mathbb{R}^d\); gesucht ist die kleinste Kugel, die alle enthält (in der Ebene der kleinste Kreis). Das Problem ist konvex: Jede Nebenbedingung \(\lVert x_i - c \rVert \le R\) begrenzt eine Norm, also eine konvexe Funktion von \((c, R)\).
• Punktwolken: Normalwolke, Haufen + Ausreißer und zwei Haufen (Wolken in \(d\) Dimensionen als Normalwolken). Die Standardwolke (Seed 35) ist ausdrücklich eine einzelne; die Experimente laufen über fünf feste Wolken je Wolkenart (SWEEP_SEEDS).
• Zertifikat: Jeder Mittelpunkt \(c\) gibt eine obere Schranke, den Abstand zum fernsten Punkt. Jede Gewichtsverteilung \(\lambda\) im Simplex gibt eine untere Schranke, die Wurzel der gewichteten Streuung der Punkte um ihren Gewichtsschwerpunkt (schwache Dualität). Ein Prüfer (check_certificate) rechnet die Schranken bei jedem Lauf aus Gewichten und Mittelpunkt neu und meldet eine verletzte Regel als Fehler.
• Verfahren: Frank-Wolfe auf dem Dual: Der fernste Punkt bekommt mehr Gewicht, der Mittelpunkt rückt auf ihn zu, die Schrittweite folgt aus exakter Linienminimierung. Die Lücke des konvexen Falls kostet in jeder Dimension \(O(n \cdot d)\) je Schritt.
• Orakel: Der exakte Radius nach Welzl dient in der App als Vergleich; das Zertifikat braucht ihn nicht.
• Nichtkonvexes Gegenstück: die getrimmte Kugel, kleinste Kugel um mindestens \(m\) der \(n\) Punkte. Das Wechselverfahren wählt die \(m\) nächsten Punkte, bildet deren Kugel und wiederholt. Exakt geht es durch Aufzählen aller Auswahlen oder über Stützpunkt-Kugeln.

Die Formeln

Das konvexe Problem unter der Nebenbedingung \(\lVert x_i - c \rVert \le R\) für alle \(i\) und seine obere Schranke (jeder Mittelpunkt \(c\) liefert eine zulässige Kugel):

\[R^* = \min_{c,R} R\]

\[U(c) = \max_i \lVert x_i - c \rVert \ge R^*\]

Für Gewichte \(\lambda \ge 0\) mit \(\sum_i \lambda_i = 1\) sei \(\bar x = \sum_i \lambda_i x_i\). Die untere Schranke ist die Wurzel der gewichteten Streuung \(D(\lambda)\) um den Gewichtsschwerpunkt:

\[D(\lambda) = \sum_i \lambda_i \lVert x_i \rVert^2 - \lVert \bar x \rVert^2 = \sum_i \lambda_i \lVert x_i - \bar x \rVert^2\]

Schwache Dualität: Für die optimale Kugel \((c^*, R^*)\) gilt die Kette unten, denn der Gewichtsschwerpunkt minimiert die gewichtete Streuung. Also liegt \(R^*\) zwischen beiden Schranken, auf welchem Weg man zu Mittelpunkt und Gewichten kam.

\[R^{*2} \ge \sum_i \lambda_i \lVert x_i - c^* \rVert^2 \ge \sum_i \lambda_i \lVert x_i - \bar x \rVert^2 = D(\lambda)\]

\[\sqrt{D(\lambda)} \le R^* \le U(c)\]

Starke Dualität gilt hier (es gibt einen strikt zulässigen Punkt, die Slater-Bedingung ist erfüllt; die Rechnung steht im Expander der Demo und ist von Hand geführt, nicht Teil der Tests):

\[\max_\lambda D(\lambda) = R^{*2}\]

Das Verfahren startet bei \(\lambda = e_1\). Im Schritt sei \(c = \sum_i \lambda_i x_i\) und \(i^*\) der fernste Punkt:

\[\lambda \leftarrow (1-\gamma)\lambda + \gamma e_{i^*}\]

mit exakter Linienminimierung für \(\gamma \in [0,1]\). Die obere Schranke ist \(U(c)\), die untere \(\sqrt{D(\lambda)}\). Die getrimmte Kugel ist dagegen

\[\min_{S,\, |S| = m} R^*(S)\]

Die Zielfunktion ist nicht konvex in den Auswahlvariablen; es gibt keine billige duale Schranke, die im Allgemeinen scharf ist. Exakt prüft man für jede Wahl von \(r = n - m\) entfernten Punkten die kleinste Kugel der übrigen oder alle Kugeln durch höchstens \(d + 1\) Punkte; die Zahl der Kugeln ist

\[\binom{n}{r}\]

\[\sum_{k=2}^{d+1} \binom{n}{k}\]

Herleitung der unteren Schranke in vier Schritten

Die Herleitung ist Standardrechnung, hier nachgerechnet, und keine Aussage der README. Symbole wie oben.

• Verschiebungssatz: Für jeden Punkt \(c\) gilt \(\sum_i \lambda_i \lVert x_i - c \rVert^2 = D(\lambda) + \lVert \bar x - c \rVert^2\). Der Kreuzterm \(2\sum_i \lambda_i (x_i - \bar x)^\top (\bar x - c)\) verschwindet, weil \(\sum_i \lambda_i (x_i - \bar x) = 0\). Der Gewichtsschwerpunkt minimiert also die gewichtete Streuung; das ist der zweite Schritt der Kette oben.
• Obergrenze der gewichteten Streuung um \(c^*\): Für die optimale Kugel gilt \(\lVert x_i - c^* \rVert \le R^*\) für alle \(i\). Gewichtet mit \(\lambda\) (Summe 1) folgt \(\sum_i \lambda_i \lVert x_i - c^* \rVert^2 \le R^{*2}\), der erste Schritt der Kette.
• Zusammen: \(R^{*2} \ge D(\lambda) + \lVert \bar x - c^* \rVert^2 \ge D(\lambda)\), also \(\sqrt{D(\lambda)} \le R^*\) für jede Gewichtsverteilung. Im Extremfall \(\lambda = e_i\) ist \(D = 0\): wahr, aber wertlos.
• Wann sie scharf ist: Gleichheit verlangt \(\bar x = c^*\) und Gewicht nur auf Punkten im Abstand \(R^*\) von \(c^*\). Dass solche Gewichte existieren, ist die starke Dualität (von Hand gezeigt, nicht getestet); das Verfahren sucht sie.

Die obere Schranke braucht keine Herleitung: Jeder Mittelpunkt \(c\) liefert mit \(U(c)\) eine zulässige Kugel, also \(R^* \le U(c)\). Die Lücke zerfällt in zwei Fehler: \(U(c) - \sqrt{D(\lambda)} = (U(c) - R^*) + (R^* - \sqrt{D(\lambda)})\). Der Befund „Fehler der oberen Schranke etwa die Hälfte der Lücke“ (unten) heißt daher, dass beide Schranken im Median über den Verlauf ungefähr gleich weit vom wahren Radius liegen. Das ist eine Umformung dieser Seite, keine zusätzliche Messung. Zur Form der oberen Schranke: \(U(c)\) ist konvex, aber nicht glatt, denn sie hat Knicke, wo der fernste Punkt wechselt. Das Mittelpunkt-Verfahren der Demo ist deshalb ein Schritt auf den jeweils fernsten Punkt zu und kein Gradientenabstieg (so der Quelltext, kvz_algorithm.py). Warum der fernste Punkt das Gewicht bekommt (Rechnung dieser Seite): Mit \(c = \sum_i \lambda_i x_i\) ist \(\partial D / \partial \lambda_i = \lVert x_i - c \rVert^2 - \lVert c \rVert^2\), und das ist für den fernsten Punkt am größten; er hebt die untere Schranke also am stärksten.

Durchgerechnet: zwei Handinstanzen

Kreis um alle Punkte. Die Handinstanz der README hat die Punkte (0,0), (4,0), (0,3), (1,1); der kleinste Kreis hat den Mittelpunkt (2; 1,5) und den Radius 2,5, dual mit den Gewichten (0; ½; ½; 0) ergibt sich 6,25 = 2,5². Die folgende Rechnung ist eine Rechnung dieser Seite, keine Messung der Demo:

• Das Gewicht liegt je zur Hälfte auf (4,0) und (0,3); der Gewichtsschwerpunkt ist deren Mitte, also (2; 1,5). Er fällt mit dem Mittelpunkt des Kreises zusammen.
• Beide gewichteten Punkte haben von (2; 1,5) den Abstand 2,5; sie liegen einander gegenüber. Also ist \(D(\lambda) = 2{,}5^2 = 6{,}25\) und die untere Schranke 2,5.
• Die obere Schranke für \(c = (2; 1{,}5)\): Der Punkt (0,0) hat ebenfalls den Abstand 2,5, denn \(2^2 + 1{,}5^2 = 6{,}25\); der Punkt (1,1) liegt näher. Also ist \(U(c) = 2{,}5\), die Lücke ist null, und der Radius 2,5 ist als kleinster bewiesen.
• Zum Vergleich gibt das Gewicht \(e_1\) (alles auf (0,0)) die untere Schranke null: gültig, aber ohne Aussagekraft.

Getrimmte Kugel. Die Instanz der README hat die Punkte (0,0), (1,0), (0,1), (10,0) und \(m = 3\); das Optimum ist 0,7071 (die drei nahen Punkte). Das Wechselverfahren aus (10,0), Rechnung dieser Seite: Die drei nächsten Punkte sind (10,0), (1,0) und (0,0); (0,1) liegt weiter weg. Ihre kleinste Kugel hat den Mittelpunkt (5; 0) und den Radius 5. Von dort aus sind wieder dieselben drei Punkte am nächsten (Abstände 4, 5 und 5; (0,1) ist etwas weiter als 5 entfernt). Das Verfahren ändert sich nicht mehr und bleibt bei 5 hängen, rund dem Siebenfachen des Optimums. Das ist eine bewusst gebaute Instanz, kein Häufigkeitsbefund; die Häufigkeiten stehen in der Tabelle unten.

Befunde

Alle Zahlen stammen aus der README der Demo. Sie sagt, jede stehe in tests/test_claims.py. Nach dem Lesen der Tests gilt das so: Die Handinstanzen und die Zählungen des Beweisaufwands prüft der Test auf den genannten Wert (die Zahl über 2 Milliarden als Schranke), die Standardwolke mit kleiner Toleranz, die übrigen Zahlen nur als Bänder um den genannten Wert; einzelne Zahlen (Nachmessungen, Laufzeit) prüft er nicht (siehe „Grenzen“). Die Experimente laufen über fünf feste Wolken je Wolkenart, nicht über einen einzelnen Seed; die Standardwolke und die Handinstanzen sind Einzelinstanzen und als solche ausgewiesen.

Frage	Befund
Handinstanz (0,0), (4,0), (0,3), (1,1)	Kugel um (2; 1,5), Radius 2,5; dual mit Gewichten (0; ½; ½; 0): 6,25 = 2,5². Getrimmt mit (0,0), (1,0), (0,1), (10,0) und m = 3: Optimum 0,7071; das Wechselverfahren aus (10, 0) bleibt bei 5 hängen.
Wie eng wird das Zertifikat? (Standardwolke: 20 Punkte, 200 Schritte, Einzelwolke)	Untere Schranke 2,334, obere 2,346, wahr 2,340: bewiesene Lücke 0,51 % (Anteil der oberen Schranke), wahrer Fehler 0,27 % (Anteil des wahren Radius).
Gilt die Reihenfolge untere Schranke ≤ wahrer Radius ≤ obere Schranke?	In 1500 Zufallspaaren (Mittelpunkt, Gewichte) in 2, 10 und 50 Dimensionen keine Verletzung; in 10 und 50 Dimensionen gegen eine Referenz aus einem langen Lauf statt des exakten Radius (im Test mit einer kleinen Toleranz).
Wie groß ist der wahre Fehler gegen die Lücke?	Der Fehler der oberen Schranke ist im Median über den Verlauf etwa die Hälfte der Lücke: 0,500 bis 0,503 in 14 von 15 festen Wolken (drei Wolkenarten), 0,59 in einer Normalwolke (Seed 100001). Das Zertifikat überschätzt den Fehler also etwa um den Faktor 2. Beobachtung, kein Satz. Der Test verlangt ein Band um 0,5 (Median je Wolkenart, mindestens 14 Wolken sehr nahe daran).
Wie viele Schritte kostet die relative Lücke ε?	Etwa 0,5 bis 0,9 mal \(1/\varepsilon\), unabhängig von Punktzahl und Dimension (n·d von 100 bis 20 000; Median über fünf Normalwolken, ε ≥ 10⁻³; in einzelnen Wolken und bei feineren ε bis rund 1,0). Bei ε = 10⁻³ zwischen 682 und 866 Schritte; zehnmal mehr Genauigkeit kostet etwa zehnmal mehr Schritte (Verhältnis 9 bis 12 von ε = 0,01 auf 0,001, 7 bis 11 von 0,1 auf 0,01). Der Test lässt für diese Zahlen etwas breitere Bänder zu.
Findet die konvexe lokale Suche das Optimum? (Mittelpunkt-Verfahren, 2000 Schritte)	Von allen 100 Zufallsstarts in jeder der 15 Wolken endet der Radius höchstens 0,1 % über dem wahren (schlechtester gemessen 0,05 %; diese zweite Zahl prüft der Test nicht).
Wie oft trifft das Wechselverfahren die getrimmte Kugel? (100 Starts, n = 20, 4 aussortiert)	Trefferquote des globalen Optimums im Median 10 % (Normalwolke), 29 % (Haufen + Ausreißer), 25 % (zwei Haufen), in einzelnen Wolken 0 bis 40 % (Median aus nur fünf Wolken je Art; der Abstand zwischen 29 und 25 % ist nicht belastbar). Schlechtester Start im Median 35 % / 248 % / 10 % über dem Optimum, im Extremfall 277 %; 6 bis 9 verschiedene Endwerte im Median je Wolkenart. Die Zahlen gehören zu diesem Wechselverfahren und dieser Startverteilung.
Was kostet der Beweis ohne Konvexität?	Teilmengen, die der Beweis durch Aufzählen prüft: C(20, 4) = 4845, C(40, 6) = 3 838 380. Über Stützpunkte (Kugeln durch höchstens d + 1 Punkte): in der Ebene n = 20: 1330, n = 40: 10 660; in 10 Dimensionen bei n = 20: 784 605, bei n = 40 über 2 Milliarden (Rechnung dieser Seite: die Summe ist rund dreieinhalb Milliarden; die README nennt die Untergrenze). Die Zahl dieser Kugeln wächst mit \(n^{d+1}\).
Wie schnell ist der Weg über Stützpunkte in der Ebene?	Auf 20 Punkten einmal gemessen 0,06 s gegen 4 bis 14 s für die Aufzählung; nicht getestet, weil zeit- und plattformabhängig. Beide Wege fanden dasselbe Optimum; getestet ist die Übereinstimmung nur auf einer kleineren Instanz.

Zur Absicherung: der exakte Radius nach Welzl gegen die Kreise durch zwei und drei Punkte (40 Wolken), gegen scipy-SLSQP (24 Wolken, 2D und 3D) und gegen Stützpunkt-Aufzählung in 3D; das Dual gegen scipy auf dem Simplex; für die getrimmte Kugel Aufzählen gegen Stützpunkte (30 Wolken in 2D, 6 in 3D).

Was die Messung zeigt und was nicht

Frage	Antwort
Folgt aus „Fehler ≈ ½ Lücke“, dass die Lücke den Fehler immer doppelt überschätzt?	Nein. Es ist der Median über den Verlauf in den 15 festen Wolken (14 mal 0,500 bis 0,503, einmal 0,59); eine Vormessung bei der Planung der Demo zeigte über den Verlauf eine breitere Spanne (README: „Phase 0 sah über den Verlauf 0,37 bis 0,59“). Es gibt keinen Beweis dafür.
Gilt das Ergebnis für andere Kugelformen oder echte Standortdaten?	Nicht gemessen. Die Demo rechnet nur die euklidische Kugel (Luftlinie) und erzeugte Wolken.
Sind 10 %, 29 % und 25 % Trefferquote belastbare Unterschiede?	Nur grob: Der Median stammt aus nur fünf Wolken je Art, einzelne Wolken liegen zwischen 0 und 40 %; der Abstand zwischen 29 und 25 % ist nach README nicht belastbar. Der Test prüft diese Quoten als Bänder um die genannten Werte.
Zeigt die Handinstanz mit Radius 5 gegen 0,7071, wie oft das Wechselverfahren versagt?	Nein. Sie ist gebaut, um das Verfahren hängen zu lassen. Die Häufigkeit liefern nur die 100 Starts je Wolke.
Beweist die Messung, dass der Beweis ohne Konvexität teuer ist?	Sie zählt, wie viele Auswahlen oder Stützkugeln ein Beweis prüfen müsste. Dass es keinen billigeren Beweis gibt, folgt daraus nicht; die README spricht nur von keinem im Allgemeinen billigen Beweis.

Grenzen

• Nur die euklidische Kugel: in der Ebene, für die Experimente zur Rate auch in höheren Dimensionen. Andere Formen sind andere Kegelprogramme und kommen nicht vor.
• Das Zertifikat überschätzt den Fehler: „Fehler ≈ ½ Lücke“ ist eine Beobachtung, kein Satz. Sie gilt nicht in jeder Wolke (0,59 in einer Normalwolke); eine Vormessung bei der Planung zeigte eine breitere Spanne (0,37 bis 0,59). Es gibt keinen Beweis dafür.
• Die Rate ist gemessen, nicht abgeleitet: 0,5 bis 0,9 mal \(1/\varepsilon\) für Normalwolken bis ε = 10⁻³. Für 10⁻⁶ ergab eine einmalige Nachmessung (Ebene mit n = 50 und 200 Punkte in 10 Dimensionen, je 2 Wolken) 0,6 bis 1,0 Millionen Schritte; sie ist nicht Teil der Tests. Die Rate passt zur bekannten Größenordnung \(O(1/\varepsilon)\) für die Größe von Kernmengen der kleinsten Kugel, ist aber nicht daraus abgeleitet.
• Ohne Konvexität ist der Beweis teuer, aber nicht in jeder Dimension unbezahlbar: In der Ebene gibt es einen schnellen exakten Weg über alle Kugeln durch zwei oder drei Punkte; deren Zahl wächst mit \(n^{d+1}\). Die Aussage lautet daher: Ohne Konvexität wächst der Beweis mit der Dimension; die Lücke des konvexen Falls kostet in jeder Dimension \(O(n \cdot d)\) je Schritt.
• Das Wechselverfahren ist eine von vielen lokalen Suchen: Bessere Heuristiken (viele Starts, Verbesserungsschritte) treffen öfter, beweisen aber nichts. Die Trefferquoten gelten für dieses Verfahren und diese Startverteilung.
• Laufzeiten sind nicht reproduzierbar: Die Laufzeit je Teilmenge im Experiment 4 ist auf dem jeweiligen Server gemessen; getestet sind nur die Zahlen der Teilmengen und Stützpunkt-Kugeln.
• Starke Dualität von Hand: Die Aussage, dass die Slater-Bedingung hier erfüllt ist, ist eine Rechnung von Hand (Expander der Demo), nicht Teil der Tests.
• Konvexität allein genügt nicht: Bei anderen konvexen Problemen kann trotz Konvexität eine Dualitätslücke bleiben (so die Tabelle „Wo die Annahmen enden“ in der App). Dass der Beweis hier lückenlos wird, liegt an der starken Dualität dieser Aufgabe.

Verweise und Fortsetzung

Nach der README kommen Ellipsoid, Würfel und andere Formen, Kegel-Dualität mit Lücke und Innere-Punkte-Verfahren in späteren Stücken der Reihe; die Reihe baut ihre Löser selbst, Bibliotheken dienen nur als Gegenprobe. Welche Stücke das im Einzelnen sind, steht auf der Konzepte-Seite der Reihe (Knopf unten). Weitere Heuristiken für die getrimmte Kugel (Mehrfachstart mit Verbesserung, Simulated Annealing) sind in dieser Demo bewusst nicht umgesetzt.

Quellen

• Welzl, E. (1991): Smallest enclosing disks (balls and ellipsoids). In: Maurer, H. (Hrsg.): New Results and New Trends in Computer Science, Lecture Notes in Computer Science 555, Springer, 359–370 (exakte kleinste Kugel in erwarteter Linearzeit bei zufälliger Reihenfolge der Punkte).
• Bădoiu, M., Clarkson, K. L. (2003): Smaller core-sets for balls. Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), 801–802 (Kernmengen der Größe \(O(1/\varepsilon)\), unabhängig von der Dimension; die Rate der Demo ist daraus nicht abgeleitet).
• Frank, M., Wolfe, P. (1956): An algorithm for quadratic programming. Naval Research Logistics Quarterly 3, 95–110 (das Verfahren, auf das der Name „Frank-Wolfe“ zurückgeht).
• Boyd, S., Vandenberghe, L. (2004): Convex Optimization. Cambridge University Press, Kapitel 5 (schwache und starke Dualität, Slater-Bedingung).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/konvexitaet-zertifikat-demo.

Die Arbeiten von Welzl sowie Bădoiu und Clarkson wurden für diese Seite nicht nachgeschlagen; die Angaben stammen aus dem Expander „📐 Mathematische Formulierung“ der Demo (die README nennt nur die Namen). Frank und Wolfe sowie Boyd und Vandenberghe sind aus dem Gedächtnis ergänzt und nicht geprüft. Dass Konvexität neben „jedes lokale Minimum ist global“ den Beweis zum Mitnehmen liefert, ist die Kernaussage der Demo und wurde für diese Seite nicht an Lehrbüchern geprüft; die Herleitung der unteren Schranke und die beiden Handrechnungen sind Rechnungen dieser Seite.