Cette page a été traduite par l'API Cloud Translation.

Contexte mathématique pour la protection contre la perte de données

Cette page contient des informations en mathématiques pour les développeurs et les utilisateurs avancés de PDLP, un résolveur de programmation linéaire et quadratique disponible dans OR-Tools. Il sert de référence pour certaines parties du code et n'est pas destiné à être lu seul. Les lecteurs intéressés doivent d'abord se familiariser avec l'article Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient, puis consulter le code, puis revenir à ce document lorsqu'il y fait référence.

Primal

La protection contre la perte de données prend en compte le problème de programmation quadratique convexe suivant.

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

où $A$ est une matrice $m \times n$ et $Q$ est une matrice $n \times n$ diagonale¹. Les vecteurs de limite supérieure $u^{c}$ et $u^{v}$ comportent des entrées dans $\mathbb{R} \cup {/7} \infty\}$, et les vecteurs de limite inférieure $l^{c}$ et $l^{v}$ comportent des entrées dans $\mathbb{R} \cup. -\infty\\}$. Nous supposons $l.

Double

Soit $a \in \mathbb{R}$. $[a]_+$ désigne sa partie positive et $[a]_-$ sa partie négative, c'est-à-dire $a = [a]_+ - [a]_-$. Lorsqu'elle est appliquée à un vecteur, les parties positives et négatives sont calculées par élément.

(le double du problème primale précédent est supérieur à $x \in \mathbb{R}^n$, $y \in\mathbb{R}^m$ et $r \in \mathbb{R}^n$. Le vecteur $y$ contient les doubles multiplicateurs sur les contraintes linéaires ($l^{c} \le Ax \$le \le$u).

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

Lorsque $Q = 0$, $x$ peut être supprimé du double, récupérant la dualité de la page de destination.

Double limite de variable

Nous indiquons que $y$ satisfait aux deux limites de variable si le $y$-term de l'objectif est fini, c'est-à-dire:

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

Dérivation à l'aide de la dualité conjuguée

Préliminaires

Utilisons $a \in \mathbb{R} \cup {/7}-\infty\}$ et $b \in \mathbb{R} \cup \{\infty\}$ avec $b \ge a$ et considérons l'intervalle $[a, b] \subseteq \mathbb{R} \cup {/7}-\infty, \infty, \infty, \in

Soit $\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup {/7} \infty\}$ la fonction indicateur de l'intervalle, c'est-à-dire $\mathcal{I}_{[a, b]}(x)$ est nul lorsque $x \in [a, b]ft$ et $x \in [a, b]ft$ et dans les autres cas

Définissez $p(y; a, b): \mathbb{R} \to \mathbb{R} \cup {/7}\infty\}$ comme:

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

Lorsque $a$ ou $b$ sont infinis, suivez l'arithmétique réelle étendue standard.

Résultat de base: $p(y; a, b) = (\mathcal{I}_{[a, b]})^*(y)$, où $(\cdot)^*$ indique le conjugué convexe.

Pour les vecteurs $l \subseteq $l \subseteq (\mathbb{R} \cup {/7}-\infty\})^n$ et $u \subseteq (\mathbb{R} \cup {/7}\infty\})^n$, la fonction indicateur $\mathcal{I}_{[l, u]} : \mathbb{R}^n \to}

Dérivation

Avec les variables auxiliaires $\tilde a \in \mathbb{R}^m$ et $\tilde x \in \mathbb{R}^n$, nous reformuleons le problème primaire comme suit:

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

En dupliquant les contraintes d'égalité, on obtient:

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

Échange des valeurs minimale et maximale et regroupement:

$$ \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 minimisation conjointe sur $x$, $\tilde x$ et $\tilde a$ se décompose. Pour $x$, nous voyons qu'un réducteur, s'il en existe un, satisfait $Qx + c - A^Ty = r$, auquel cas la valeur minimale est $-\frac{1}{2} x^TQx$. Pour $\tilde x$ et $\tilde a$, nous appliquons la définition des conjugués convexes avec de légers ajustements pour les signes.

Cela donne le double:

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

En élargissant la définition de $p$, nous obtenons le double indiqué en haut.

Formulation à la pointe de la selle

Le gradient hybride primale (voir Chambolle et Pock) cible un problème primaire de forme.

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

qui, par dualité conjuguée, équivaut au problème à la selle

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

Le PDLP convertit le problème de programmation quadratique convexe sous cette forme en définissant:

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

Comme dérivé précédemment, $h^*(y) = p(y; -u^c,-l^c)$ est une fonction convexe linéaire par morceaux. $g$ et $h^*$ peuvent tous deux accepter des valeurs infinies, ce qui limite efficacement les domaines de $x$ et $y$ respectivement.

Notez que l'opérateur proximal de $g$ peut être calculé sous forme fermée selon l'hypothèse de la PDLP selon laquelle $Q$ est diagonale, en tenant compte du fait que $g$ est séparable et que la propriété suivante est valable pour toutes les fonctions $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). $$

Pour une preuve de ce fait, consultez par exemple le théorème 6.13 dans Méthodes de premier ordre en optimisation. L'expression résultante est donnée par

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

Réduction des coûts, double résidus et correction du double objectif

La formulation du point final ne fonctionne explicitement qu'avec $(x,y)$. Les coûts réduits $r$ sont implicites. Afin de renvoyer $(x,y,r)$ lors de la résolution de la formule de la formule, nous définissons $r$ comme $r = Qx + c - A^Ty$. Le double objectif corrigé est la valeur objective du double problème, et définit toujours la limite inférieure de la valeur d'objectif, mais est toujours de $-\infty$ à partir d'un coût non limité.

Les coûts réduits et le double objectif indiqués par la protection contre la perte de données ont été modifiés entre les versions 9.7 et 9.8 de l'outil OR. Pour savoir quelle version s'applique, consultez le commentaire décrivant SolverResult::reduced_costs dans primal_dual_hybrid_gradient.h et vérifiez s'il mentionne la version 9.8.

Versions 9.7 et antérieures

Afin d'avoir une valeur double plus significative lorsque l'objectif corrigé est $-\infty$, nous signalons également un double objectif qui ignore les termes infinis de la valeur d'objectif. Les dual résiduals (résiduels doubles) correspondent aux valeurs de $r$ issues des termes infinis dans l'objectif double corrigé, avec 0 dans les autres composants, et les coûts réduits renvoyés par PDLP sont les valeurs de $r$ provenant des termes finis dans le double objectif corrigé, avec 0 dans les autres composants (de sorte que $r =\mbox{residuals} + mbox{residuals} + mbox{residuals} + mbox{residuals} + mbox{residuals} + mbox{residuals} + mbox{residuals} + mbox{residuals} + mbox{residuals} + mbox{residuals} + mbox{residuals} + mbox{residuals} + mbox{residuals} + mbox{residuals} +

Versions 9.8 et ultérieures

Pour obtenir une double valeur plus significative lorsque l'objectif corrigé est $-\infty$, nous indiquons également un double objectif qui remplace les termes infinis de la valeur d'objectif par des termes finis, comme suit: si l'une des limites est finie, cette limite est utilisée à la place de la limite infinie. Sinon, la valeur zéro est utilisée. Ce choix préserve la concavité du double objectif, mais ne donne pas nécessairement une limite inférieure à la valeur de l'objectif. Les deux résiduels sont les valeurs de $r$ à partir de termes infinis dans l'objectif double corrigé. Les coûts réduits renvoyés par la protection contre la perte de données sont de $r$.

Traitement de certaines limites de variables comme infinies

Dans les deux versions, si l'option de résolution handle_some_primal_gradients_on_finite_bounds_as_residuals est true (valeur par défaut), les limites de variables supplémentaires peuvent être traitées comme infinies lors du calcul de l'objectif double et des résidus doubles. En particulier, si $|x_i - l^v_i| > |x_i|$, $l^v_i$ est traité comme s'il était infini, et de même si $|x_i - u^v_i| > |x_i|$, $u^v_i$ est traité comme s'il était infini.

Notez que handle_some_primal_gradients_on_finite_bounds_as_residuals n'affecte pas les itérations calculées. Il n'affecte que les objectifs doubles et les résidus utilisés dans les tests d'arrêt et les statistiques consignées.

Redimensionnement

Supposons que nous recevions une matrice de redimensionnement $C$ en diagonale (colonne) et une matrice de redimensionnement en diagonale ($R$) avec des entrées positives sur la diagonale. En appliquant le rescaling comme dans ShardedQuadraticProgram::RescaleQuadraticProgram, nous obtenons le problème transformé suivant:

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

Une solution au problème d'origine est récupérée comme $x = C\tilde x$. Si $\tilde y$ est une double solution et que $\tilde r$ sont des coûts réduits pour le problème transformé, $y = R\tilde y$ est une solution double et $r = C^{-1}\tilde r$ sont omis des coûts pour le problème d'origine (dérivation).

Identification de l'impossibilité

Un certificat d'infaisabilité primale est un point $(y, r) \in \mathbb{R}^m \times \mathbb{R}^n$ satisfaisant:

$$ \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'existence d'un tel point implique que le problème primaire n'a pas de solution.

De même, un certificat de double infaisabilité est un point $x \in \mathbb{R}^n$ tel que:

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

Notez que vous pouvez obtenir les certificats d'un programme linéaire en définissant $Q=0$.

Une matrice objectif semi-définie symétrique $S$ peut être convertie sous cette forme en factorisant $S$ comme $S = R^T R$ (par exemple, une factorisation de Cholesky), en introduisant des variables supplémentaires $z$ définies par des contraintes $R x - z = 0$, de sorte que $x^T S x = z^T z.