Questa pagina è stata tradotta dall'API Cloud Translation.

Sfondo matematico per PDLP

Questa pagina contiene un background matematico per sviluppatori e utenti avanzati di PDLP, un risolutore di programmazione lineare e quadratica disponibile in OR-Tools. Serve come riferimento per parti del codice e non deve essere letto da solo. I lettori interessati dovrebbero prima acquisire familiarità con l'articolo "Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient", quindi esaminare il codice e tornare a questo documento quando il codice vi fa riferimento.

Primale

PDLP considera il seguente problema di programmazione quadratica convessa:

$$ \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} $$

dove $A$ è una matrice $m \times n$ e $Q$ è una matrice diagonale non negativa $n \times n$ ¹. I vettori del limite superiore $u^{c}$ e $u^{v}$ hanno voci in $\mathbb{R} \cup \{ \infty\}$, mentre i vettori del limite inferiore $l^{c}$ e $l^{v}$ hanno voci in $\mathbb{R} \cup \{ -\infty${c.

Dual

Sia $a \in \mathbb{R}$. Sia $[a]_+$ che indichi la sua parte positiva e $[a]_-$ indica la sua parte negativa, ovvero $a = [a]_+ - [a]_-$. Quando applicate a un vettore, le parti positive e negative vengono calcolate dal punto di vista dell'elemento.

Il doppio del problema principale precedente è superiore a $x \in \mathbb{R}^n$, $y \in \mathbb{R}^m$ e $r \in \mathbb{R}^n$. Il vettore $y$ contiene moltiplicatori doppi nei vincoli lineari ($l^{c} \le Ax \le u^{c}ap p

$$ \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} $$

Quando $Q = 0$, $x$ può essere eliminato dal doppio, recuperando la dualità LP.

Limiti variabili doppi

Diciamo che $y$ soddisfa i limiti della doppia variabile se il $y$-term nell'obiettivo è finito, ovvero:

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

Derivazione utilizzando la dualità coniugata

Eliminatorie

Lascia $a \in \mathbb{R} \cup \{-\infty\}$ e $b \in \mathbb{R} \cup \{\infty\}$ con $b \ge a$ e considera l’intervallo $[a, b] \subseteq \mathbb{R} \cup \{-\infty\}$.

Sia $\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup \{ \infty\}$ la funzione indicatore dell'intervallo, ovvero $\mathcal{I}_{[a, b]}(x)$ è zero quando $x \in [a, b]$ e $\infty$.

Definisci $p(y; a, b): \mathbb{R} \to \mathbb{R} \cup \{\infty\}$ come:

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

Quando $a$ o $b$ sono infiniti, segui l'aritmetica reale estesa standard.

Risultato di base: $p(y; a, b) = (\mathcal{I}_{[a, b]})^*(y)$ dove $(\cdot)^*$ indica il coniugato convesso.

Per i vettori $l \subseteq (\mathbb{R} \cup \{-\infty\})^n$ e $u \subseteq (\mathbb{R} \cup \{\infty\})^n$, la funzione indicatore $\mathcal{I}_ \{[l, u]} : \mathbb{R}^n}

Derivazione

Introdundo le variabili ausiliarie $\tilde a \in \mathbb{R}^m$ e $\tilde x \in \mathbb{R}^n$, riportiamo il problema principale come:

$$ \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} $$

Dualizzando i vincoli di uguaglianza, otteniamo:

$$ \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) $$

Scambio minimo con massimo e riraggruppamento:

$$ \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) $$

La minimizzazione congiunta di $x$, $\tilde x$ e $\tilde a$ si decompone. Per $x$ vediamo che un minimo di riduzione, se presente, soddisfa $Qx + c - A^Ty = r$, in questo caso il valore minimo è $-\frac{1}{2} x^TQx$. Per $\tilde x$ e $\tilde a$ applichiamo la definizione di coniugati convessi con piccole regolazioni per segni.

Questo produce la duplice funzione:

$$ \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} $$

Ampliando la definizione di $p$, otteniamo il duplice indicato in alto.

Formulazione a sella

Il gradiente ibrido primo-doppio (vedi Chambolle e Pock) riguarda un problema principale del modulo.

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

che, per coniugazione della dualità, equivale al problema della punta a sella

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

PDLP forza il problema di programmazione quadratica convessa a questa forma impostando:

$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)$
K $ = -A$

Come derivato in precedenza, $h^*(y) = p(y; -u^c,-l^c)$ è una funzione convessa lineare a tratti. Sia $g$ che $h^*$ possono assumere valori infiniti, che limitano di fatto i domini di $x$ e $y$ rispettivamente.

Nota che l'operatore prossimale di $g$ è calcolabile in forma chiusa in base al presupposto di PDLP che $Q$ sia diagonale, partendo dal fatto che $g$ è separabile e la seguente proprietà, che vale per qualsiasi funzione $f_1, f_2$:

$$ 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). $$

Per una dimostrazione di questo fatto, vedi ad esempio il Teorema 6.13 in Metodi di ordine di primo livello nell'ottimizzazione. L'espressione risultante è data

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

Costi ridotti, doppi residui e il duplice obiettivo corretto

La formulazione del punto a sella funziona esplicitamente solo con $(x,y)$; i costi ridotti $r$ sono impliciti. Per restituire $(x,y,r)$ quando risolvi la formulazione del punto a sella, definiamo $r$ come $r = Qx + c - A^Ty$. Il doppio obiettivo corretto è il valore obiettivo del duplice problema e assegna sempre un limite inferiore al valore obiettivo, ma è $-\infty$ ogni volta che vi è un costo infinito ridotto su un limite diverso da zero.

I costi ridotti e il duplice obiettivo segnalati da PDLP sono stati modificati tra le versioni 9.7 e 9.8 degli strumenti OR. Per verificare quale versione si applica, controlla il commento che descrive SolverResult::reduced_costs in primal_dual_hybrid_gradient.h e controlla se menziona la versione 9.8.

Versione 9.7 e precedenti

Per avere un duplice valore più significativo quando il duplice obiettivo corretto è $-\infty$, segnaliamo anche un doppio obiettivo che ignora i termini infiniti nel valore dell'obiettivo. I doppi residui sono i valori di $r$ dai termini infiniti nel doppio obiettivo corretto, con 0 negli altri componenti, mentre i costi ridotti restituiti da PDLP sono i valori di $r$ dai termini finiti nel doppio obiettivo corretto, con 0 negli altri componenti (in modo che $r = \mbox{residuals} + \m}${reduced).

Versione 9.8 e successive

Per avere un valore doppio più significativo quando il duplice obiettivo corretto è $-\infty$, segnaliamo anche un doppio obiettivo che sostituisce i termini infinito nel valore obiettivo con quelli finiti come segue: se uno dei limiti è finito, viene utilizzato quel limite al posto di quello infinito; in caso contrario viene utilizzato zero per il limite. Questa scelta preserva la concavità del duplice obiettivo, ma non attribuisce necessariamente un limite inferiore al valore obiettivo. I doppi residui sono i valori di $r$ dei termini infiniti nell'obiettivo doppio corretto. I costi ridotti restituiti da PDLP sono pari a r$.

Trattamento di alcuni limiti variabili come infiniti

In entrambe le versioni, se l'opzione del risolutore handle_some_primal_gradients_on_finite_bounds_as_residuals è true (valore predefinito), i limiti di variabili aggiuntivi possono essere considerati infiniti quando si calcolano il doppio obiettivo e i residui doppi. In particolare, se $|x_i - l^v_i| > |x_i|$, $l^v_i$ viene trattato come se fosse infinito, e allo stesso modo se $|x_i - u^v_i| > |x_i|$, $u^v_i$ viene trattato come se fosse infinito.

Tieni presente che handle_some_primal_gradients_on_finite_bounds_as_residuals non influisce sulle iterazioni calcolate, ma solo sul doppio obiettivo e sui residui utilizzati nei test di terminazione e nelle statistiche segnalate.

Scalabilità in corso...

Supponiamo di avere a disposizione una matrice di ridimensionamento diagonale (colonna) $C$ e una matrice di ridimensionamento diagonale (riga) $R$ con voci positive sulla diagonale. Applicando il ridimensionamento come in ShardedQuadraticProgram::RescaleQuadraticProgram, otteniamo il seguente problema trasformato:

$$ \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} $$

Una soluzione al problema originale viene recuperata come $x = C\tilde x$. Se $\tilde y$ è una soluzione doppia e $\tilde r$ sono costi ridotti per il problema trasformato, allora $y = R\tilde y$ è una soluzione doppia e $r = C^{-1}\tilde r$ sono i costi ridotti del problema originale (derivazione omessa).

Identificazione dell'impossibilità

Un certificato di infattibilità primaria è un punto $(y, r) \in \mathbb{R}^m \times \mathbb{R}^n$ che soddisfa:

$$ \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} $$

L'esistenza di un punto di questo tipo implica che il problema principale non ha una soluzione.

Analogamente, un certificato di doppia infattibilità è un punto $x \in \mathbb{R}^n$ per il quale:

$$ \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} $$

Tieni presente che i certificati per un programma lineare possono essere ottenuti impostando $Q=0$.

Una matrice dell'obiettivo semidefinito positivo simmetrico $S$ può essere convertita in questa forma fattorizzando $S$ come $S = R^T R$ (ad esempio, una fattorizzazione di Cholesky), introducendo variabili aggiuntive $z$ definite dai vincoli $R x - z = 0$, in modo che $x^T S x = z^T z$.