Antecedentes matemáticos para PDLP

Esta página contiene antecedentes matemáticos para desarrolladores y usuarios avanzados de PDLP, un solucionador de problemas de programación lineal y cuadrático disponible en las herramientas de OR. Sirve como referencia para partes del código y no está pensada para leerse por sí sola. Los lectores interesados deben familiarizarse primero con el documento "Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient" (programación lineal a gran escala práctica con gradiente híbrido Primal-Dual). Luego, deben mirar el código y, luego, volver a este documento cuando el código haga referencia a él.

Primal

El PDLP considera el siguiente problema de programación cuadrático convexo:

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

donde $A$ es una matriz de $m \times n$ y $Q$ es una matriz diagonal no negativa de $n \times n$ 1. Los vectores de límite superior $u^{c}$ y $u^{v}$ tienen entradas en $\mathbb{R} \cop \{ \infty\}$, y los vectores de límite inferior $l^{c}$ y $l^{v}$ tienen entradas en $\mathbb{R} \cup \{ -\infty $^}$.

Dual

Supongamos que $a \in \mathbb{R}$. Supongamos que $[a]_+$ denota su parte positiva y $[a]_-$ denota su parte negativa, es decir, $a = [a]_+ - [a]_-$. Cuando se aplican a un vector, las partes positivas y negativas se calculan por elementos.

El doble del problema principal anterior es superior a $x \in \mathbb{R}^n$, $y \in \mathbb{R}^m$ y $r \in \mathbb{R}^n$. El vector $y$ contiene multiplicadores dobles en las restricciones lineales ($l^{c} \le Ax \le$}).

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

Cuando $Q = 0$, se puede quitar $x$ del doble y recuperar la dualidad del LP.

Límites variables duales

Se dice que $y$ satisface los límites de variables dobles si el término $y$ del objetivo es finito, es decir:

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

Derivación mediante la dualidad conjugada

Aspectos preliminares

Deja que $a \in \mathbb{R} \cup \{-\infty\}$ y $b \in \mathbb{R} \cup \{\infty\}$ con $b \ge a$ y considere el intervalo $[a, b] \subseteq}\mathbb{R} \cup \{-$inft.

Deja que $\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup \{ \infty\}$ sea la función indicadora del intervalo, es decir, $\mathcal{I}_{[a, b]}(x)$ es cero cuando $x \in$a, $a.

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

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

Cuando $a$ o $b$ son infinitos, sigue la aritmética real extendida estándar.

Resultado básico: $p(y; a, b) = (\mathcal{I}_{[a, b]})^*(y)$ donde $(\cdot)^*$ denota el conjugado convexo.

Para los vectores $l \subseteq (\mathbb{R} \cup \{-\infty\})^n$ y $u \subseteq (\mathbb{R} \cup \{\infty\})^n$, la función $\mathcal{I}_ análoga{[l, u]}

Derivación

Mediante la introducción de las variables auxiliares $\tilde a \in \mathbb{R}^m$ y $\tilde x \in \mathbb{R}^n$, reformulamos el problema principal de la siguiente manera:

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

Al duplicar las restricciones de igualdad, obtenemos lo siguiente:

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

Intercambio de mínimo con máximo y reagrupación:

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

Se descompone la minimización conjunta sobre $x$, $\tilde x$ y $\tilde a$. Para $x$, vemos que un minimizador, si existe uno, satisface $Qx + c - A^Ty = r$, en cuyo caso el valor mínimo es $-\frac{1}{2} x^TQx$. Para $\tilde x$ y $\tilde a$, aplicamos la definición de conjugados convexos con ajustes menores para los signos.

Esto produce el doble:

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

Al expandir la definición de $p$, obtenemos el doble indicado en la parte superior.

Formulación de punto de montura

El gradiente híbrido primo-dual (consulta Chambolle y Pock) se orienta a un problema principal de la forma

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

que, por la dualidad conjugada, equivale al problema de la posición

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

El PDLP coerciona el problema de programación cuadrático convexo a esta forma configurando lo siguiente:

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

Como se derivó antes, $h^*(y) = p(y; -u^c,-l^c)$ es una función convexa lineal a trozos. Tanto $g$ como $h^*$ pueden tomar valores infinitos, lo que limita de manera efectiva los dominios de $x$ y $y$, respectivamente.

Ten en cuenta que el operador proximal de $g$ es computable de forma cerrada bajo la suposición de PDLP de que $Q$ es diagonal, a partir del hecho de que $g$ es separable y la siguiente propiedad que contiene cualquier función $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). $$

Para obtener una prueba de este hecho, consulta, por ejemplo, el teorema 6.13 en Métodos de primer orden en la optimización. La expresión resultante se obtiene

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

Reducción de costos, doble residual y el objetivo doble corregido

La formulación de puntos de silla de montar solo funciona de manera explícita con $(x,y)$; los costos reducidos $r$ son implícitos. Para que se muestre $(x,y,r)$ cuando resuelvas la fórmula del punto de cálculo, definimos $r$ como $r = Qx + c - A^Ty$. El objetivo doble corregido es el valor objetivo del problema doble y siempre brinda un límite inferior en el valor objetivo, pero es $-\infty$ reducido en el costo no limitado.

Los costos reducidos y el objetivo doble informados por el PDLP se cambiaron entre las versiones 9.7 y 9.8 de las herramientas de OR. Para verificar qué versión se aplica, revisa el comentario que describe SolverResult::reduced_costs en primal_dual_hybrid_gradient.h y comprueba si menciona la versión 9.8.

Versión 9.7 y anteriores

Para tener un valor doble más significativo cuando el objetivo doble corregido es $-\infty$, también informamos un objetivo doble que ignora los términos infinitos en el valor objetivo. Los residuales dobles son los valores de $r$ de términos infinitos en el objetivo doble corregido, con 0 en los otros componentes, y los costos reducidos que muestra el PDLP son los valores de $r$ de los términos finitos en el objetivo doble corregido, con 0 en los otros componentes (para que $r = \mbox{residuals} + \mbox{reducido).

Versión 9.8 y posteriores

Para tener un valor doble más significativo cuando el objetivo doble corregido es $-\infty$, también informamos un objetivo doble que reemplaza los términos infinitos en el valor objetivo con unos finitos, de la siguiente manera: si uno de los límites es finito, se usa ese límite en lugar del infinito; de lo contrario, se usa cero para el límite. Esta opción preserva la concavidad del objetivo doble, pero no necesariamente da un límite inferior en el valor objetivo. Los residuales dobles son los valores de $r$ provenientes de términos infinitos en el objetivo doble corregido. Los costos reducidos que muestra PDLP son $r$.

Tratar algunos límites variables como infinitos

En ambas versiones, si la opción de resolución handle_some_primal_gradients_on_finite_bounds_as_residuals es true (la opción predeterminada), los límites variables adicionales se pueden tratar como infinitos cuando se calculan el objetivo doble y los residuales dobles. En particular, si $|x_i - l^v_i| > |x_i|$, $l^v_i$ se trata como si fuera infinito, y del mismo modo si $|x_i - u^v_i| > |x_i|$, $u^v_i$ se trata como si fuera infinito.

Ten en cuenta que handle_some_primal_gradients_on_finite_bounds_as_residuals no afecta las iteraciones calculadas; solo afecta a los objetivos dobles y los residuales que se usan en las pruebas de finalización y las estadísticas informadas.

Redimensionamiento

Supongamos que se nos proporcionan una matriz de reescalamiento diagonal (columna) $C$ y una matriz de reescalamiento diagonal (fila) $R$ con entradas positivas en la diagonal. Si aplicas el cambio de escala como en ShardedQuadraticProgram::RescaleQuadraticProgram, obtenemos el siguiente problema transformado:

$$ \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 solución al problema original se recupera como $x = C\tilde x$. Si $\tilde x$ es una solución doble y $\tilde r$ se reducen los costos para el problema transformado, entonces $y = R\tilde y$ es una solución dual y $r = C^{-1}\tilde r$ se reducen los costos para el problema original (derivaciones omitidas).

Identificación de inviabilidad

Un certificado de inviabilidad primaria es un punto $(y, r) \in \mathbb{R}^m \times \mathbb{R}^n$ que satisface:

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

La existencia de ese punto implica que el problema principal no tiene una solución.

Del mismo modo, un certificado de inviabilidad dual es un punto $x \in \mathbb{R}^n$ tal 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} $$

Ten en cuenta que los certificados para un programa lineal se pueden obtener si configuras $Q=0$.

  1. Una matriz objetivo semidefinida simétrica positiva $S$ se puede convertir a esta forma si se factoriza $S$ como $S = R^T R$ (por ejemplo, una factorización de Colesky), introduciendo variables adicionales $z$ definidas por las restricciones $R x funcione z = 0$, de modo que $x^T S x = z^T z$. ↩