Numerische Genauigkeit in der Quadratsummenmethode?

13

Ich habe etwas über die Quadratsummenmethode (SOS) aus der Umfrage von Barak & Steurer und den Vorlesungsunterlagen von Barak gelesen . In beiden Fällen werden Probleme mit der numerischen Genauigkeit unter den Teppich gekehrt.

Nach meinem (zugegebenermaßen eingeschränkten) Verständnis der Methode sollte Folgendes zutreffen:

Wenn ein beliebiges System von Polynomgleichungen über reelle Variablen , wobei alle Parameter ( , und Grad jeder Einschränkung) sind, ist der Grad " " "( ) SOS-Methode findet eine zufriedenstellende Zuordnung der Variablen oder beweist, dass keine in der -Zeit existiert . E O ( 1 ) n | E | 2 n = O ( 1 ) O ( 1 )xRnO(1)n|E|2n=O(1)O(1)

Meine erste Frage ist, ob die obige Behauptung wahr ist (gibt es ein naives Argument, das SOS nicht verwendet, um dies zu lösen?). Die zweite Frage ist, wo die numerische Genauigkeit hineinpasst. Wenn ich eine Zuordnung erhalten möchte, die alle Einschränkungen innerhalb der additiven Genauigkeit erfüllt , wie hängt die Laufzeit von ? Insbesondere ist es Polynom?1 / εε1/ε

Die Motivation hierfür ist beispielsweise, einen Divide-and-Conquer-Ansatz auf ein großes System anzuwenden, bis der Basisfall ein System der Größe ist.O(1)

EDIT: Von Barak-Steurer, scheint es , dass der „Grad sum-of-Squares - Algorithmus“ auf S. 9 (und die Absätze zu ihm führen up) definieren alle Probleme für die Lösungen über , und in der Tat die Definition einer Pseudoverteilung in Abschnitt 2.2 ist over . Jetzt sehe ich aus Lemma 2.2 jedoch, dass eine Lösung / Widerlegung bei Grad ohne binäre Variablen nicht garantiert ist.lRR2n

So kann ich meine Frage ein wenig verfeinern. Wenn Ihre Variablen nicht binär sind, besteht die Sorge darin, dass die Folge der Ausgaben nicht endlich ist (vielleicht nicht einmal monoton ansteigend?). Die Frage ist also: nimmt immer noch zu? Und wenn ja, wie weit müssen Sie gehen, um additive Genauigkeit ?φ(l)φ(l)ε

Obwohl dies nicht wahrscheinlich nichts ändern, passiere ich mein System wissen erfüllbar ist (es gibt keine Widerlegung jeden Grad), so dass ich wirklich nur um besorgt bin , wie groß l Bedürfnisse zu sein. Schließlich bin ich an einer theoretischen Lösung interessiert, nicht an einem numerischen Löser.

Jeremy Kun
quelle

Antworten:

1

Hier ist Boaz Baraks Kommentar zu diesem Thema:

Wir gehen der numerischen Genauigkeit auf den Grund - die eher "traditionelle" SOS-Literatur von Parrilo, Lasserre usw. befasst sich mit diesen Fragen (siehe z. B. Monique Laurents Umfragen und die darin enthaltenen Referenzen). Es ist bekannt , dass , dass die Hierarchie monoton ist (es ist nicht schwer zu sehen ist , dass eine gewisses Maß psuedo-Verteilung insbesondere ein Grad ist eins), und dass es in endlichem Grad für jeden festen Satz von Gleichungen konvergieren (das ist der Positivstellensatz). Der genaue Grad kann variieren. Wenn alle Koeffizienten der Polynome begrenzt sind und Sie versuchen, zwischen dem Fall zu unterscheiden, dass es eine Lösung gibt, und dem Fall, dass in einer Zuweisung eine der Gleichungen durch , dann könnte man dies zu einem diskretisieren.l - 1 δll1ϵδ-net für Bezug auf die Anzahl der Variablen, den Grad der Gleichungen und . Unter der Annahme, dass das Netz ausreichend "nett" und "würfelförmig" ist, sollte der erforderliche Grad ungefähr der Größe des Netzes entsprechen.ϵδϵ

Kaveh
quelle
Gepostet als Antwort, um zu vermeiden, dass der Community-Bot die Frage in Zukunft erneut stellt.
Kaveh
1

Ich denke, meine Antwort ist wahrscheinlich unzureichend, aber es bleibt der Vollständigkeit halber (obwohl Boaz's Kommentare unten für wahrscheinlich eine bessere Antwort sehen)

Wenn wir uns auf boolesche Variablen beschränken, kann die Behauptung gesehen werden, wenn für alle i [ n ] mit der Beobachtung, dass Grad 2 n Pseudoverteilungen tatsächliche Verteilungen sind, das heißt, angenommen, Sie haben eine Pseudoverteilung μ ( x ) über Lösungen x Ihrer Polynomgleichungen E, die erfüllt:(xi21)Ei[n]2nμ(x)xE

undx { - 1 , 1 } n μ ( x ) p 2 ( x ) 0 für alle Polynome p mit einem Grad von höchstens nx{1,1}nμ(x)x{1,1}nμ(x)p2(x)0pn

Grad Polynome umfassen jedoch das Indikatorpolynom (zum Beispiel x 1 = 1 , x 2 = - 1 , x 3 = 1 hat 2 - 3 ( 1 + x 1 ) ( 1 - x 2 ) ( 1 + x 3 ), welches ist an anderer Stelle Null und 1 für diese Zuordnung). Also μ ( x ) 0 für alle x {nx1=1,x2=1,x3=123(1+x1)(1x2)(1+x3)μ(x)0 , also schließen wir, dass μ eine tatsächliche Verteilung über die Lösungen von E ist . Grad ℓ- Pseudoverteilungen können durch Verwendung einer semidefiniten Programmierung ermittelt werden, um einen zugeordneten Grad ℓ- Pseudoerwartungsoperator in n O ( ) -Zeit zu ermitteln , sodass wir die tatsächliche Verteilung μ in der Zeit n O ( n ) unter Verwendung dieser Pseudoerwartung ermitteln können. Erwartung (jetzt eine tatsächliche Erwartung), um alle Momente von μ zu finden .x{1,1}nμEnO()μnO(n)μ

Also, wenn , dann können Sie eine Verteilung der Lösungen auf E in O ( 1 ) -Zeit finden. Natürlich garantiert die Brute-Force-Suche dasselbe.|E|=O(1)EO(1)

Wenn die Lösungen jedoch nicht unbedingt boolesch sind, reichen Grad- Pseudoerwartungen nicht aus, um eine Verteilung über Lösungen zu finden. Wie oben zu sehen ist, hängt der Beweis, dass Grad 2 n Pseudoverteilungen tatsächliche Verteilungen sind, von der Tatsache ab, dass Grad n Polynome ausreichen, um einzelne Zuordnungen herauszusuchen, was im Allgemeinen nicht zutrifft. Eine andere Sichtweise ist, dass boolesche variable Polynome berücksichtigt werden2n2nn , also ist der Grad jedes Monoms höchstens n .mod(xi2)n

Beispielsweise könnte man in Betracht ziehen, jede Binärvariable durch eine 4-stellige Variable zu ersetzen, indem beispielsweise . Dann müssten Sie einen Grad 4 n Pseudoerwartung haben, um die Wiederherstellung einer Verteilung über Lösungen zu gewährleisten.(xi21)(xi24)E4n

Für theoretische Garantien scheint es, dass die Approximation einer Wurzel eines Polynomensystems auch als Smales 17. Problem bezeichnet wird, und anscheinend gibt es einen randomisierten (Las Vegas) Polynom-Zeit-Algorithmus, der dies löst - siehe http://arxiv.org /pdf/1211.1528v1.pdf . Beachten Sie, dass dies im Blum-Shub-Smale-Modell zu sein scheint, sodass reale Operationen das Primitive sind. Ich bin mir nicht sicher, ob dies die Garantie bietet, die Sie benötigen.

Joe Bebel
quelle
Ich glaube, ich habe dies nicht klargestellt: Meine Variablen sind in R , da ich sonst einfach eine triviale O ( 2 n ) = O ( 1 ) -Suche über den booleschen Hyperkubus durchführen könnte. Ich habe die Frage aktualisiert, um dies widerzuspiegeln. SDP / SOS betrifft auch Probleme bei der Optimierung von Eingaben, oder? xiRO(2n)=O(1)
Jeremy Kun
Ups, mein Fehler! Ja, es gilt für allgemeinere Einstellungen, obwohl wir oft davon ausgehen, dass wir uns im Hypercube befinden. Ich habe meine Antwort aktualisiert, obwohl meine Antwort weniger klar sein wird, als ich gehofft hätte.
Joe Bebel
10
Wir gehen der numerischen Genauigkeit auf den Grund - die eher "traditionelle" SOS-Literatur von Parrilo, Lasserre usw. befasst sich mit diesen Fragen (siehe z. B. Monique Laurents Umfragen und die darin enthaltenen Referenzen). Es ist bekannt , dass , dass die Hierarchie monoton ist (es ist nicht schwer zu sehen ist , dass eine gewisses Maß psuedo-Verteilung insbesondere ein Grad ist l - 1 eins), und dass es in endlichem Grad für jeden festen Satz von Gleichungen konvergieren (das ist der Positivstellensatz). 1
Boaz Barak
9
..Der genaue Grad kann variieren. Wenn im Allgemeinen alle Koeffizienten der Polynome begrenzt sind und Sie versuchen, zwischen dem Fall zu unterscheiden, dass eine Lösung vorliegt, und dem Fall, dass in einer Zuweisung eine der Gleichungen um , könnte man dies zu einem δ diskretisieren - net für δ, bezogen auf die Anzahl der Variablen, den Grad der Gleichungen und ϵ , und dann (vorausgesetzt, das Netz ist ausreichend "schön" und "würfelförmig") sollte der erforderliche Grad ungefähr die Größe des Netzes betragen. ϵδδϵ
Boaz Barak
4
@ BoazBarak vielleicht könnte dies eine Antwort sein?
Suresh Venkat