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, that is, $a = [a]_+ - [a]_-$. When applied to a vector, the positive and negative parts are computed element-wise.

The dual of the earlier 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, that is, $\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 with 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 for example 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 define $r$ as $r = Qx + c - A^Ty$. The *corrected
dual objective* is the objective value of the dual problem, and always gives a
lower bound on the objective value, but is $-\infty$ whenever there is a
non-zero reduced cost on an infinite bound.

The reduced costs and dual objective reported by PDLP were changed between
OR-tools versions 9.7 and 9.8. To check which version applies, check the comment
describing `SolverResult::reduced_costs`

in `primal_dual_hybrid_gradient.h`

and
see if it mentions version 9.8.

#### Version 9.7 and earlier

In order to have a more meaningful dual value when the corrected dual objective
is $-\infty$, we also report a *dual objective* which ignores the infinite terms
in the objective value. The *dual residuals* are the values of $r$ from infinite
terms in the corrected dual objective, with 0 in the other components, and the
*reduced costs returned by PDLP* are the values of $r$ from the finite terms in
the corrected dual objective, with 0 in the other components (so that $r =
\mbox{residuals} + \mbox{reduced costs}$).

#### Version 9.8 and later

In order to have a more meaningful dual value when the corrected dual objective
is $-\infty$, we also report a *dual objective* which replaces the infinite
terms in the objective value with finite ones as follows: if one of the bounds
is finite, that bound is used instead of the infinite one; otherwise zero is
used for the bound. This choice preserves the concavity of the dual objective,
but does not necessarily give a lower bound on the objective value. The *dual
residuals* are the values of $r$ from infinite terms in the corrected dual
objective. The *reduced costs returned by PDLP* are $r$.

#### Treatment of some variable bounds as infinite

In both versions, if the solver option
`handle_some_primal_gradients_on_finite_bounds_as_residuals`

is `true`

(the
default), additional variable bounds may be treated as infinite when computing
the dual objective and dual residuals. In particular, if $|x_i - l^v_i| >
|x_i|$, $l^v_i$ is treated as if it were infinite, and similarly if $|x_i -
u^v_i| > |x_i|$, $u^v_i$ is treated as if it were infinite.

Note that `handle_some_primal_gradients_on_finite_bounds_as_residuals`

does not
affect the iterates computed; it only affects dual objective and residuals used
in termination tests and reported statistics.

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