Genaue Algorithmen für nicht konvexe quadratische Programmierung

Bei dieser Frage geht es um quadratische Programmierprobleme mit Box-Constraints (Box-QP), also um Optimierungsprobleme des Formulars

minimiere vorbehaltlich von . $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}$ $\mathbf{x} \in [0,1]^n$

Wenn positiv semidefinit wäre, wäre alles schön und konvex und einfach, und wir könnten das Problem in Polynomzeit lösen. $A$

Auf der anderen Seite, wenn man die Einstückigkeit constraint hatte konnten wir das Problem mit der Zeit leicht lösen , mit roher Gewalt. Für die Zwecke dieser Frage ist dies relativ schnell. $\mathbf{x} \in \{0,1\}^n$ $O(2^n \cdot \mathrm{poly}(n))$

Aber was ist mit dem nicht konvexen kontinuierlichen Fall? Was ist der schnellste bekannte Algorithmus für allgemeine Box-QPs?

Zum Beispiel können wir diese in mäßig exponentieller Zeit, beispielsweise lösen , oder sind die Worst-Case - Komplexität der bekanntesten Algorithmen etwas viel Schlimmeres? $O(3^n \cdot \mathrm{poly}(n))$

Hintergrund: Ich habe einige ziemlich kleine Box-QPs, die ich eigentlich gerne lösen würde, und ich war ein wenig überrascht zu sehen, wie schlecht einige kommerzielle Softwarepakete selbst bei sehr kleinen Werten von abschneiden . Ich begann mich zu fragen, ob es eine TCS-Erklärung für diese Beobachtung gibt. $n$

ds.algorithms optimization exp-time-algorithms Jukka Suomela
quelle

Kannst du das auch für PSD

genau lösen ? Die Lösung kann irrational sein, nicht wahr? Wenn Sie bereit sind additiv zu verlieren

vielleicht kann man einen exponentiellen Algorithmus erhalten durch Brute-Force-Methode über ein ausreichend feines Gitter zu tun. Nur ein vager Vorschlag.

A

$A$

ϵ

$\epsilon$

Chandra Chekuri

Nachteil ist, dass die "Basis" des Exponenten ungefähr

, aber vielleicht kann eine geschickte Rastertechnik für "kleine"

1 / ϵ

$1/\epsilon$

n

$n$

Suresh Venkat

@ChandraChekuri: Annäherungen sind vollkommen in Ordnung, wenn Sie z. B.

. Ein brachiales Überwinden eines solch feinen Gitters ist jedoch nicht möglich.

ϵ = 10^{- 9}

$\epsilon = 10^{-9}$

Jukka Suomela

Durch die Eliminierung von Quantifizierern auf realen geschlossenen Feldern ist es immer möglich, diese Systeme exakt zu lösen.

Wenn

zulässig ist, können Sie die Funktion auf jeder Seite des Würfels optimieren, indem Sie die Optimalitätskriterien erster Ordnung aufschreiben.

O (3^{n})

$O(3^n)$

Yoshio Okamoto

Antworten:

Eine optimale Lösung liegt auf einem Gesicht. So können wir alle Flächen des Würfels durchgehen und alle stationären Punkte auf jeder der Flächen finden.

Hier ist ein konkreteres Verfahren. Eine Fläche des Würfels kann durch zwei disjunkte Indexmengen und charakterisiert werden . Für wir und für wir . Sei aus den verbleibenden nicht fixierten Einträgen von . Durch diese Festlegung wird die Zielfunktion in die folgende Form gebracht: $I_0$ $I_1$ $i \in I_0$ $x_i = 0$ $i \in I_1$ $x_i = 1$ $\tilde{x}$ $x$

{\tilde{x}}^{⊤} \tilde{A} \tilde{x} + {\tilde{c}}^{⊤} \tilde{x} + d,

$\tilde{x}^{\top} \tilde{A} \tilde{x} + \tilde{c}^{\top} \tilde{x} + d,$

$\tilde{A}$ $\tilde{c}$ $d$ $0 < \tilde{x} < 1$

Zu diesem Zweck nehmen wir die Differenzierung der Zielfunktion, um zu erhalten

\frac{1}{2} \tilde{A} \tilde{x} + \tilde{c} = 0.

$\frac{1}{2} \tilde{A} \tilde{x} + \tilde{c} = 0.$

Durch Lösen dieses linearen Gleichungssystems erhalten Sie die stationären Punkte, die Kandidaten für optimale Lösungen. Wir gehen alle durch, überprüfen den Zustand und wählen einen mit dem minimalen Zielwert aus.

Die Gesamtzeitkomplexität ist ungefähr so $O(3^n \text{poly}(n))$ da die Anzahl der Gesichter der $n$ -Würfel ist $3^n$ und ein lineares Gleichungssystem kann in Polynomzeit gelöst werden. Die Raumkomplexität ist in polynomial $n$ .

Yoshio Okamoto
quelle

Warum liegt eine optimale Lösung auf einem Gesicht mit einer nicht konvexen

f

$f$ ?

Cody

@cody: Das liegt daran, dass jedes Polytop die disjunkte Vereinigung seiner Gesichter ist.

Yoshio Okamoto

Was wäre wenn

f

$f$ ist kubisch oder quartisch? Hält diese Eigenschaft noch?

Cody

@cody: Die Eigenschaft ist immer noch gültig, aber wir müssen eine algebraische Gradgleichung mehr als einmal lösen. Ich fürchte, das ist für multivariate Fälle nicht trivial.

Yoshio Okamoto