Diese Seite wurde von der Cloud Translation API übersetzt.

Mathematischer Hintergrund für PDLP

Diese Seite enthält mathematischen Hintergrund für Entwickler und fortgeschrittene Nutzer von PDLP, einem linearen und quadratischen Programmlöser, der in OR-Tools verfügbar ist. Er dient als Referenz für Teile des Codes und sollte nicht allein gelesen werden. Interessierte Leser sollten sich zuerst mit dem Artikel Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient vertraut machen, sich dann den Code ansehen und dann zu diesem Dokument zurückkehren, wenn der Code darauf verweist.

Primal – Primal

PDLP befasst sich mit dem folgenden konvexen quadratischen Programmierproblem:

$$ \begin{align} \min_x & \, c^Tx + \frac{1}{2}x^TQx \\ \text{s.t.}\; & l^{c} \le Ax \le u^{c} \\ & l^{v} \le x \le u^{v} \end{align} $$

Dabei ist $A$ eine $m \times-n$-Matrix und $Q$ eine diagonale, nicht negative $n \times-n$-Matrix¹. Die Vektoren der oberen Begrenzungen $u^{c}$ und $u^{v}$ enthalten Einträge in $\mathbb{R} \cup \infty\}$, und die unteren Vektoren $l^{c}$ und $l^{v}$ enthalten Einträge in $\mathbb{R} \cup ^${le{le ^${u} \cup\cup ^${l \cup\cup -\infty\}$.

Dual

Lassen Sie $a \in \Mathbb{R}$. $[a]_+$ soll seinen positiven Teil und $[a]_-$ den negativen Teil angeben, also $a = [a]_+ - [a]_-$. Wird auf einen Vektor angewendet, werden der positive und der negative Teil elementweise berechnet.

Das Duale des früheren Hauptproblems ist über $x \in \mathbb{R}^n$, $y \in \mathbb{R}^m$ und $r \in \mathbb{R}^n$. Der Vektor $y$ enthält doppelte Multiplikatoren auf den linearen Einschränkungen ($lbound dual{c} \le Axuc \le, \$le Axuc}, die $le Reduce-Kosten und $le Axuc}.

$$ \begin{align} \max_{x, y, r} & \, -\frac{1}{2}x^TQx + \left((l^{c})^T[y]_+ - (u^{c})^T[y]_- \right) + \left((l^{v})^T[r]_+ - (u^{v})^T[r]_- \right) \\ \text{s.t.}\; & Qx + c - A^Ty = r \end{align} $$

Wenn $Q = 0$ ist, kann $x$ aus dem Dualen entfernt werden, um so die LP-Dualität wiederherzustellen.

Grenzen zwischen zwei Variablen

Wir sagen, dass $y$ die Grenzen der zwei Variablen erfüllt, wenn der $y$-Begriff im Ziel begrenzt ist, also:

$$ y_i \geq 0 \qquad \text{if }u^c_i = \infty, \\ y_i \leq 0 \qquad \text{if }l^c_i = -\infty. $$

Konjugierte Dualität ableiten

Grundlegendes

Lass $a \in \mathbb{R} \cup \cup \{-\infty\}$ und $b \in \mathbb{R} \cup \{\infty\}$ mit $b \ge a$ und berücksichtige das Intervall $[a, b] \subseteq \mathbb{R} \cup \cup \infty, \in

Lassen Sie $\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup \infty\}$ die Indikatorfunktion des Intervalls sein, d. h. $\mathcal{I}_{[a, b]}(x)$ ist Null, wenn $x \in [a, b]$ ansonsten $.

Definieren Sie $p(y; a, b): \mathbb{R} \to \mathbb{R} \cup \infty\}$ als:

$$ p(y; a, b) = \begin{cases} ay & \text{ if } y < 0 \\ 0 & \text{ if } y = 0 \\ by & \text{ if } y > 0 \end{cases}. $$

Wenn $a$ oder $b$ unendlich sind, folgen Sie der standardmäßigen erweiterten reellen Arithmetik.

Einfaches Ergebnis: $p(y; a, b) = (\mathcal{I}_{[a, b]})^*(y)$, wobei $(\cdot)^*$ die konjugierte Konjugierte angibt.

{l

Ableitung

Durch die Einführung der Hilfsvariablen $\tilde a \in \mathbb{R}^m$ und $\tilde x \in \mathbb{R}^n$ wird das Grundproblem neu formuliert:

$$ \begin{align} \min_{x, \tilde x, \tilde a} & \, c^Tx + \frac{1}{2}x^TQx + \mathcal{I}_{[l^c,u^c]}(\tilde a) + \mathcal{I}_{[l^v,u^v]}(\tilde x) \\ \text{s.t.}\; & \tilde a = Ax \\ & \tilde x = x \end{align} $$

Wenn Sie die Gleichheitseinschränkungen verdoppeln, erhalten wir:

$$ \min_{x, \tilde x, \tilde a} \max_{y, r} c^Tx + \frac{1}{2}x^TQx + y^T\tilde a - y^TAx + r^T\tilde x - r^Tx + \mathcal{I}_{[l^c,u^c]}(\tilde a) + \mathcal{I}_{[l^v,u^v]}(\tilde x) $$

Min. mit Max austauschen und Neugruppierungen:

$$ \max_{y, r} \min_{x, \tilde x, \tilde a} c^Tx + \frac{1}{2}x^TQx - y^TAx - r^Tx + \left( \mathcal{I}_{[l^c,u^c]}(\tilde a) + y^T\tilde a \right) + \left(\mathcal{I}_{[l^v,u^v]}(\tilde x) + r^T\tilde x \right) $$

Die gemeinsame Minimierung über $x$, $\tilde x$ und $\tilde a$ zerlegt. Für $x$ sehen wir, dass ein Minimierer, sofern vorhanden, $Qx + c - A^Ty = r$ erfüllt. In diesem Fall ist der Minimalwert $-\frac{1}{2} x^TQx$. Bei $\tilde x$ und $\tilde a$ wenden wir die Definition von konjugierten Konjugierten mit kleineren Anpassungen für Vorzeichen an.

Daraus ergibt sich Folgendes:

$$ \begin{align} \max_{x, y, r} & \, -\frac{1}{2}x^TQx - p(-y, l^c, u^c) - p(-r, l^v, u^v) \\ \text{s.t.}\; & Qx + c - A^Ty = r \end{align} $$

Durch Erweitern der Definition von $p$ erhalten wir den oben angegebenen Dual.

Formulierung mit Sattelspitzen

Der Primal-Dual-Hybrid-Farbverlauf (siehe Chambolle und Pock) zielt auf ein Hauptproblem der Form

$$ \begin{align} \min_x f(x) + g(x) + h(Kx) \end{align} $$

Die konjugierte Dualität entspricht dem Sattelpunktproblem.

$$ \begin{align} \min_x \max_y f(x) + g(x) + y^TKx - h^*(y) \end{align} $$

PDLP erzwingt das Problem der konvexen quadratischen Programmierung in dieses Format, indem Folgendes festgelegt wird:

$f(x) = 0$

$g(x) = c^T x + \frac{1}{2} x^T Q x + \mathcal{I}_{[l^v, u^v]}(x)$

$h(a) = \mathcal{I}_{[-u^c,-l^c]}(a)$

$T = -A$

Wie zuvor abgeleitet, ist $h^*(y) = p(y; -u^c,-l^c)$ eine stückweise lineare konvexe Funktion. Sowohl $g$ als auch $h^*$ können unendliche Werte annehmen, wodurch die Domains von $x$ bzw. $y$ effektiv eingeschränkt werden.

Beachten Sie, dass der proximale Operator von $g$ in geschlossener Form berechnet werden kann, wenn PDLP unter der Annahme, dass $Q$ diagonal ist, die Tatsache berechnet, dass $g$ trennbar ist und die folgende Eigenschaft für alle Funktionen $f_1, f_2$ gilt:

$$ f_2(t) = f_1(t) + \frac{\mu}{2} t^2 \Rightarrow \mathrm{prox}_{\lambda f_2}(t) = \mathrm{prox}_{\frac{\lambda}{1 + \lambda \mu} f_1}\left( \frac{t}{1 + \lambda \mu} \right). $$

Einen Beweis dafür finden Sie im Beispielsatz 6.13 unter Methoden der ersten Reihenfolge bei der Optimierung. Der resultierende Ausdruck ist durch

$$ \begin{equation} \mathrm{prox}_{\lambda g}(x) = \mathrm{proj}_{[l^v, u^v]}\left( (I + \lambda Q)^{-1} (x - \lambda c) \right) \end{equation} $$

Reduzierte Kosten, doppelte Residuen und das korrigierte doppelte Ziel

Die Sattelpunktformulierung funktioniert nur explizit mit $(x,y)$; die reduzierten Kosten $r$ sind implizit. Um bei der Lösung der Sattelpunktformulierung $(x,y,r)$ zurückzugeben, definieren wir $r$ als $r = Qx + c - A^Ty$. Das korrigierte duale Ziel ist der objektive Wert des doppelten Problems. Es gibt immer eine untere Grenze für die Zielgrenze, aber bei unendlichen Kosten um $ \infty$.

Die reduzierten Kosten und das doppelte Ziel, die von PDLP gemeldet wurden, haben sich zwischen den ODER-Tools-Versionen 9.7 und 9.8 geändert. Wenn Sie wissen möchten, welche Version zutrifft, sehen Sie sich den Kommentar an, der SolverResult::reduced_costs in primal_dual_hybrid_gradient.h beschreibt, und prüfen Sie, ob Version 9.8 erwähnt wird.

Version 9.7 und niedriger

Um einen sinnvolleren Dual-Wert zu erhalten, wenn das korrigierte duale Ziel „$-\infty$“ ist, melden wir auch ein Dual Objective, das die unendlichen Terme im Zielwert ignoriert. Die dualen Residuen sind die Werte von $r$ aus unendlichen Bedingungen im korrigierten Dual Objective, mit 0 in den anderen Komponenten, und die reduzierten Kosten, die von PDLP zurückgegeben sind, sind die Werte von $r$ aus den endlichen Bedingungen im korrigierten Dual Objective, mit 0 in den anderen Komponenten (so dass $r = \mbox{reiduals} + \mbox{reiduals}).

Version 9.8 und höher

Um einen sinnvolleren Dual-Wert zu erhalten, wenn das korrigierte duale Ziel $-\infty$ ist, melden wir auch ein duales Ziel, das die unendlichen Begriffe im Zielwert wie folgt durch endliche Ausdrücke ersetzt: Wenn einer der Grenzen endlich ist, wird diese Grenze anstelle der unendlichen verwendet. Andernfalls wird für die Begrenzung Null verwendet. Diese Auswahl bewahrt die Konkavität des doppelten Ziels auf, gibt jedoch nicht unbedingt eine Untergrenze für den Zielwert. Die Dual-Residuen sind die Werte von $r$ aus unendlichen Ausdrücken im korrigierten dualen Ziel. Die reduzierten Kosten, die von PDLP zurückgegeben werden betragen r$.

Behandlung einiger variabler Grenzen als unendlich

Wenn in beiden Versionen die Solver-Option handle_some_primal_gradients_on_finite_bounds_as_residuals auf true (Standardeinstellung) gesetzt ist, können zusätzliche Variablengrenzen bei der Berechnung des dualen Ziels und der dualen Residuen als unendlich behandelt werden. Insbesondere gilt: Wenn $|x_i - l^v_i| > |x_i|$, $l^v_i$, als wäre es unendlich, und $|x_i - u^v_i| > |x_i|$, $u^v_i$ wird so behandelt, als wäre es unendlich.

Beachten Sie, dass handle_some_primal_gradients_on_finite_bounds_as_residuals keinen Einfluss auf die berechneten Iterationen hat. Er wirkt sich nur auf Dual-Ziele und Residuen aus, die in Beendigungstests und gemeldeten Statistiken verwendet werden.

Skalierung wird angepasst

Angenommen, wir erhalten eine diagonale (Spalte) neu skalierende Matrix $C$ und eine diagonale (Zeile) neu skalierende Matrix $R$ mit positiven Einträgen auf der Diagonalen. Bei Anwendung der Neuskalierung wie in ShardedQuadraticProgram::RescaleQuadraticProgram erhalten wir die folgende transformierte Problem:

$$ \begin{align} \min_{\tilde x} & \, (Cc)^T{\tilde x} + \frac{1}{2}{\tilde x}^T(CQC){\tilde x} \\ \text{s.t.}\; & Rl^{c} \le RAC\tilde x \le Ru^{c} \\ & C^{-1}l^{v} \le \tilde x \le C^{-1}u^{v} \end{align} $$

Eine Lösung für das ursprüngliche Problem wird mit $x = C\tilde x$ wiederhergestellt. Wenn $\tilde y$ eine doppelte Lösung ist und $\tilde r$ geringere Kosten für das transformierte Problem darstellt, dann ist $y = R\tilde y$ eine doppelte Lösung und $r = C^{-1}\tilde r$ geringere Kosten für das ursprüngliche Problem (Ableitung).

Identifizierung der Nichtdurchführbarkeit

Ein Zertifikat der Grundundurchführbarkeit ist der Punkt $(y, r) \in \mathbb{R}^m \times \mathbb{R}^n$ erfüllt:

$$ \begin{equation} \left((l^{c})^T[y]_+ - (u^{c})^T[y]_- \right) + \left((l^{v})^T[r]_+ - (u^{v})^T[r]_- \right) > 0 \\ -A^T y = r . \end{equation} $$

Die Existenz eines solchen Punkts impliziert, dass es für das ursprüngliche Problem keine Lösung gibt.

Ebenso ist ein Zertifikat der doppelten Nichtdurchführbarkeit ein Punkt $x \in \Mathbb{R}^n$, sodass:

$$ \begin{equation} Qx = 0 \\ c^T x < 0 \\ (Ax)_i \begin{cases} = 0 & \text{if }l^c_i , u^c_i \in \mathbb{R}, \\ \geq 0 & \text{if }l^c_i \in \mathbb{R}, u^c_i = \infty, \\ \leq 0 & \text{if }l^c_i = -\infty, u^c_i \in \mathbb{R}, \end{cases} \\ x_i \begin{cases} = 0 & \text{if }l^v_i , u^v_i \in \mathbb{R}, \\ \geq 0 & \text{if }l^v_i \in \mathbb{R}, u^v_i = \infty, \\ \leq 0 & \text{if }l^v_i = -\infty, u^v_i \in \mathbb{R}. \end{cases} \end{equation} $$

Die Zertifikate für ein lineares Programm erhalten Sie, indem Sie $Q=0$ festlegen.

Eine symmetrische positive semidefinite Zielmatrix $S$ kann in diese Form umgewandelt werden, indem $S$ als $S = R^T R$ (z. B. eine Cholesky-Faktorisierung) faktorisiert wird. Dabei werden zusätzliche Variablen $z$ eingeführt, die durch die Einschränkungen $R x – z = 0$ definiert sind, sodass $x^T S x = z^T z$ ist. ↩