This page contains mathematical background for developers and advanced users of PDLP, a linear and quadratic programming solver available in OR-Tools. It serves as reference for parts of the code and is not intended to be read on its own. Interested readers should first familiarize themselves with the paper, "Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient", then look at the code, then come back to this document when the code references it.
Primal
PDLP considers the following convex quadratic programming problem,
where $A$ is an $m \times n$ matrix and $Q$ is a symmetric $n \times n$ positive semidefinite matrix. The upper bound vectors $u^{c}$ and $u^{v}$ have entries in $\mathbb{R} \cup { \infty}$, and the lower bound vectors $l^{c}$ and $l^{v}$ have entries in $\mathbb{R} \cup { -\infty}$. We assume $l^{c} \le u^{c}$ and $l^{v} \le u^{v}$.
Dual
Let $a \in \mathbb{R}$. Let $[a]_+$ denote its positive part and $[a]_-$ denote its negative part, i.e., $a = [a]_+ - [a]_-$. When applied to a vector, the positive and negative parts are computed element-wise.
The dual of the above primal problem is over $x \in \mathbb{R}^n$, $y \in \mathbb{R}^m$, and $r \in \mathbb{R}^n$. The vector $y$ contains dual multipliers on the linear constraints ($l^{c} \le Ax \le u^{c}$). The vector $r$, called the reduced costs, contains dual multipliers on the bound constraints ($l^{v} \le x \le u^{v}$).
When $Q = 0$, we can drop $x$ from the dual, and we recover LP duality.
Dual variable bounds
We say that $y$ satisfies the dual variable bounds if the $y$-term in the objective is finite, that is:
Derivation via conjugate duality
Preliminaries
Let $a \in \mathbb{R} \cup {-\infty}$ and $b \in \mathbb{R} \cup {\infty}$ with $b \ge a$ and consider the interval $[a, b] \subseteq \mathbb{R} \cup {-\infty, \infty}$.
Let $\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup { \infty}$ be the indicator function of the interval, i.e., $\mathcal{I}_{[a, b]}(x)$ is zero when $x \in [a, b]$ and $\infty$ otherwise.
Define $p(y; a, b): \mathbb{R} \to \mathbb{R} \cup {\infty}$ as:
When $a$ or $b$ are infinite, follow standard extended real arithmetic.
Basic result: \(p(y; a, b) = (\mathcal{I}_{[a, b]})^*(y)\) where $(\cdot)^*$ denotes the convex conjugate.
For vectors $l \subseteq (\mathbb{R} \cup {-\infty})^n$ and $u \subseteq (\mathbb{R} \cup {\infty})^n$, the indicator function $\mathcal{I}_{[l, u]} : \mathbb{R}^n \to \mathbb{R} \cup { \infty}$ is defined analogously, and we define $p(y; l, u) = (\mathcal{I}_{[l, u]})^*(y) = \sum_{i=1}^n p(y_i; l_i, u_i)$.
Derivation
Introducing auxiliary variables $\tilde a \in \mathbb{R}^m$ and $\tilde x \in \mathbb{R}^n$, we restate the primal problem as:
Dualizing the equality constraints, we obtain:
Exchanging min/max and regrouping:
The joint minimization over $x$, $\tilde x$, and $\tilde a$ decomposes. For $x$ we see that a minimizer, if one exists, satisfies $Qx + c - A^Ty = r$, in which case the minimum value is $-\frac{1}{2} x^TQx$. For $\tilde x$ and $\tilde a$ we apply the definition of convex conjugates with minor adjustments for signs.
This yields the dual:
By expanding the definition of $p$, we obtain the dual stated at the top.
Saddle-point formulation
Primal-dual hybrid gradient (see Chambolle and Pock) targets a primal problem of the form
which by conjugate duality is equivalent to the saddle-point problem
PDLP coerces the convex quadratic programming problem into this form by setting:
- $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$
As derived above, \(h^*(y) = p(y; -u^c,-l^c)\) is a piecewise linear convex function. Both $g$ and $h^*$ can take infinite values, which effectively limits the domains of $x$ and $y$ respectively.
Note that the proximal operator of $g$ is computable in closed form under PDLP's assumption that $Q$ is diagonal, using the fact that $g$ is separable and the following property that holds for any functions \(f_1, f_2\):
For a proof of this fact, see e.g., Theorem 6.13 in First-Order Methods in Optimization. The resulting expression is given by
Reduced costs, dual residuals, and the corrected dual objective
The saddle point formulation only explicitly works with $(x,y)$; the reduced costs $r$ are implicit. In order to return $(x,y,r)$ when solving the saddle-point formulation, we choose an $r$ that approximately satisfies $Qx + c - A^Ty = r$, that is,
where $\tilde{r}$ are the dual residuals and $r$ are the reduced costs. Without this allocation of $Qx + c - A^T y$ between dual residuals and reduced costs, the objective value of the dual problem would be $-\infty$ whenever there is a non-zero reduced cost on an infinite bound. The term corrected dual objective is used to identify the objective value of the dual problem when $\tilde{r} = 0$. Thus the corrected dual objective always gives a lower bound on the objective value, but is often $-\infty$.
Rescaling
Suppose we are given a diagonal (column) rescaling matrix $C$ and a diagonal
(row) rescaling matrix $R$ with positive entries on the diagonal. Applying
rescaling as in ShardedQuadraticProgram::RescaleQuadraticProgram
, we obtain
the following transformed problem:
A solution to the original problem is recovered as $x = C\tilde x$. If $\tilde y$ is a dual solution and $\tilde r$ are reduced costs for the transformed problem, then $y = R\tilde y$ is a dual solution and $r = C^{-1}\tilde r$ are reduced costs for the original problem (derivation omitted).
Infeasibility identification
A certificate of primal infeasibility is a point $(y, r) \in \mathbb{R}^m \times \mathbb{R}^n$ satisfying:
The existence of such a point implies that the primal problem doesn't have a solution.
Similarly, a certificate of dual infeasibility is a point $x \in \mathbb{R}^n$ such that:
Note that the certificates for a linear program can be obtained by setting $Q=0$.