mrpro.algorithms.optimizers.pdhg

mrpro.algorithms.optimizers.pdhg(f: ProximableFunctionalSeparableSum | ProximableFunctional | None, g: ProximableFunctionalSeparableSum | ProximableFunctional | None, operator: LinearOperator | LinearOperatorMatrix | None, initial_values: Sequence[Tensor], max_iterations: int = 32, tolerance: float = 0, primal_stepsize: float | None = None, dual_stepsize: float | None = None, relaxation: float = 1.0, initial_relaxed: Sequence[Tensor] | None = None, initial_duals: Sequence[Tensor] | None = None, callback: Callable[[PDHGStatus], None] | None = None) → tuple[Tensor, ...][source]

Primal-Dual Hybrid Gradient Algorithm (PDHG).

Solves the minimization problem

\(\min_x f(K x) + g(x)\)

with linear operator \(K\) and proper, convex, lower-semicontinous functionals \(f\) and \(g\).

PDHG is a primal-dual algorithm that performs the following steps

\[z_{k+1} = \mathrm{prox}_{\sigma f^{\ast}}(z_k + \sigma K \bar{x}_k), x_{k+1} = \mathrm{prox}_{\tau g}(x_k - \tau K^H z_{k+1}), \bar{x}_{k+1} = x_{k+1} + \theta(x_{k+1} - x_k),\]

where \(\mathrm{prox}\) denotes the proximal operator and \(f^{\ast}\) is the convex conjugate of the functional \(f\). Thereby, \(\tau\) and \(\sigma\) are the primal and dual step sizes, respectively (see further below) and \(\theta\in [0,1]\).

The operator can be supplied as a LinearOperator or as a \(m\times n\) -LinearOperatorMatrix, \(f\) and \(g\) can either be single functionals or ProximableFunctionalSeparableSum of m, or n, respectively, functionals.

Thus, this implementation solves the problem

\(\min_{x=(x_1,\ldots,x_n)} \sum_{i=1}^m f_i\big( (Kx)_i\big) + \sum_{j=1}^n g_j(x_j)\).

If neither primal nor dual step size are supplied, they are both chosen as \(1/||K||_2\). If only one of them is supplied, the other is chosen such that

\(\tau \sigma = 1/||K||_2\),

where \(1/||K||_2\) denotes the operator-norm of \(K\). Note that the computation of the operator-norm can be computationally expensive and that if no stepsizes are provided, the algorithm runs a power iteration to obtain the upper bound for the stepsizes.

For a warm start, the initial relaxed primal and dual variables can be supplied. These might be obtained from the status object of a previous run.

Parameters:

  • f (ProximableFunctionalSeparableSum | ProximableFunctional | None) – Functional f in the problem definition. If set to None, it is interpreted as the zero-functional.

  • g (ProximableFunctionalSeparableSum | ProximableFunctional | None) – Functional g in the problem definition. If set to None, it is interpreted as the zero-functional.

  • operator (LinearOperator | LinearOperatorMatrix | None) – Linear operator or matrix of linear operators; if set to None, it is interpreted as the Identity-operator.

  • initial_values (Sequence[Tensor]) – initial guess of the solution.

  • max_iterations (int, default: 32) – maximum number of iterations.

  • tolerance (float, default: 0) – tolerance for relative change of the primal solution; if set to zero, max_iterations of pdhg are run.

  • dual_stepsize (float | None, default: None) – dual step size.

  • primal_stepsize (float | None, default: None) – primal step size.

  • relaxation (float, default: 1.0) – relaxation parameter, 1.0 is no relaxation.

  • initial_relaxed (Sequence[Tensor] | None, default: None) – relaxed primals, used for warm start.

  • initial_duals (Sequence[Tensor] | None, default: None) – dual variables, used for warm start.

  • callback (Callable[[PDHGStatus], None] | None, default: None) – callback function called after each iteration.