Härte einer beschränkten quadratischen Maximierung

7

Betrachten Sie die folgende quadratische Maximierung: mit \ begin {align} \ mathcal {X} = \ lbrace \ mathbf {x} \ in \ mathbb {R} ^ {n}: ~ \ | \ mathbf {x} \ | _ {2} = 1, \ | \ mathbf {x} \ | _ {0} \ le k \ rbrace, \ end {align} wobei \ mathbf {A} eine positive semidefinite Matrix und k \ le n ein Sparsity-Parameter ist. Dieses Problem ist NP-schwer, durch eine Reduzierung des Max-Clique-Problems.

maxxXxTAx
X={xRn: x2=1,x0k},
Akn

Ich interessiere mich für ein ähnliches Problem, das durch Auferlegen einer zusätzlichen Struktur für X . Angenommen, die n Variablen in x sind in k disjunkte Gruppen unterteilt. Wir beschränken die mögliche Menge auf Einheitslängenvektoren x mit einer aktiven Variablen pro Gruppe. Das heißt, X enthält wieder k sparsame Vektoren, aber die Unterstützung kann nicht beliebig sein; Es enthält (höchstens) einen Eintrag ungleich Null für jede der k Gruppen.

Beachten Sie, dass die realisierbare Menge in dem modifizierten Problem eine Teilmenge der vorherigen Maximierung ist, aber die Anzahl der realisierbaren Unterstützungen in der Anzahl der Variablen n (für entsprechend gewähltes k ) immer noch exponentiell sein kann .

Ich vermute, dass das modifizierte Problem auch NP-schwer ist. Irgendwelche Ideen, wie man das zeigt (oder widerlegt)? Fühlen Sie sich frei, Ihre Intuition zu teilen.

Megas
quelle
Ohne die Anforderung der Halbwertszeit sollte dies durch Reduktion von der unabhängigen Menge NP-hart sein. Angenommen, ist ein Graph mit Eckpunkten. Erstellen Sie eine Instanz des Problems mit Variablen und - Gruppen, eine Gruppe pro Vertex von . Das Setzen der ersten Variablen in der Gruppe von auf 1 entspricht dem Hinzufügen von zur unabhängigen Menge. Das Setzen der 2. Variablen ist so, als würde man der Menge kein hinzufügen . Jetzt können Sie eine Matrix , die die Anzahl der Kanten so minimiert dass beide in der Menge sind. Aber wird dasGN2NNvGvvvA(v,w)Ev,wAsemidefinit sein? Ich weiß es nicht.
DW
@DW, könnten Sie einfach den Laplace-Wert der Adjazenzmatrix verwenden? ist immer positiv semidefinit. L
Nicholas Mancuso
@NicholasMancuso, ich weiß es nicht! Interessante Idee.
DW
Wenn das einzige Problem darin besteht, dass das Argument nicht positiv semidefinit (PSD) ist ( ist nur symmetrisch), sollte es in Ordnung sein: Wir können die Maximierung immer auf lösen . Ich werde einen Blick auf den vorgeschlagenen Ansatz werfen und Sie wissen lassen! AAA+|λmin(A)|I
Megas
Ich habe einige Probleme damit, diesen Ansatz an mein Problem anzupassen. Für mich ist nicht binär; Es ist ein realer Einheitsnormvektor, der auch negative Einträge haben darf, was einige Schwierigkeiten beim Entwerfen von . Es sei denn, ich vermisse etwas Offensichtliches? Aber mir hat die Idee der Variablen gefallen . Ich werde weiter darüber nachdenken, ob ich etwas herausfinden kann, das darauf aufbaut. xA2N
Mega

Antworten:

2

(Ich habe die Antwort auf meine Frage gefunden, daher teile ich hier eine Skizze) .

Die quadratische Maximierung kann durch Reduktion des folgenden Problems als NP-hart gezeigt werden:

  • Wenn der Partitendiagramm , enthält eine Klasse.kG=(V1,,Vk,E)Gk

Beachten Sie, dass das letztere Problem ein (scheinbar) spezieller Fall des Max-Clique-Problems ist, der auf eine bestimmte Familie von Graphen beschränkt ist. Es kann jedoch gezeigt werden, dass es auch NP-vollständig ist, indem das allgemeine Max-Clique-Problem selbst reduziert wird (siehe hier) .

Let die Adjazenzmatrix bezeichnen . Sei eine beliebige Menge von Eckpunkten und bezeichnet die Haupt-Submatrix, die , dh ist die Adjazenz des durch induzierten Graphen . Wenn die Eckpunkte in eine Klasse in , sind alle nicht diagonalen Einträge von gleich und sein Haupteigenwert . In jedem anderen Fall, wennAGSkASS ASk×kSSkGAS1λ1(AS)=k1S ist keine Klasse, dann ist . Schließlich ist zu beachten , dass , da ist -partiten, a -clique (falls vorhanden) einen einzelnen Scheitelpunkt von jedem der Sätze enthalten , .kλ1(AS)<k1GkkVii=1,,k

Sei , wobei ist der kleinste Eigenwert von ; ist eine PSD-Matrix. Betrachten Sie ferner disjunkte Gruppen von Variablen, die den Mengen von . Wir lösen die quadratische Maximierung mit der Eingabe und den angegebenen Variablengruppen. Der maximale Zielwert ist gleichgenau dann, wenn eine Clique enthält .A=A+|λn(A)|Iλn(A)AAkV1,,VkGAk1+|λn(A)|Gk

Megas
quelle