PGM

The fundamental class from which all PGM algorithms are derived is PGM, which supports problems of the form

\[\mathrm{argmin}_{\mathbf{x}} \; f(\mathbf{x}) + g(\mathbf{x}) \;\;,\]

where \(f, g\) are convex functions and \(f\) is smooth. All the updates are made in input domain.

Additional classes within the pgm.pgm module support less general forms of problem; this specialisation allows for a smaller number of methods that have to be overriden in derived classes.

Classes derived from PGM should override/define the methods and attributes in the following sections.

See pgm.bpdn.BPDN as an example of a class derived from PGM.

Initialisation

The __init__ method of the derived class should call the PGM __init__ method to ensure proper initialisation.

State variable \(\mathbf{x}\) is initialised to zero by PGM.xinit. This method should be overridden if a different initialization is desired.

Update Steps

The PGM updates steps are defined by the following methods:

• PGM.xstep

  Compute

  \[\mathbf{x}^{(j+1)} = \mathrm{prox}_{t}(g) \left( \mathbf{y}^{(j)} - \frac{1}{L}\; \nabla_{\mathbf{x}} f(\mathbf{y}^{(j)}) \right) \;,\]

  where the proximal operation is defined as:

  \[\mathrm{prox}_{t}(g)\left( \mathbf{x} \right) = \mathrm{argmin}_{\mathbf{u}} \;\; g(\mathbf{u}) + \frac{1}{2 t} \left\| \mathbf{u} - \mathbf{x} \right\|_2^2 \; .\]

  This method should set self.X as a function of self.Y and gradient of \(f\).

  Optionally, a monotone PGM version from [7] is available. The monotone version evaluates the functional value at the new update \(\mathbf{x}^{(j+1)}\). If this update causes an increment on the objective function \(f(\mathbf{x}) + g(\mathbf{x})\) then it will revert to the previous iterate \(\mathbf{x}^{(j)}\). The PGM.ystep is also modified in monotone PGM.

• PGM.ystep

  Compute

  \[\mathbf{y}^{(j+1)} = \mathbf{x}^{(j+1)} + \frac{t^{(j)} - 1}{t^{(j+1)}} \left( \mathbf{x}^{(j+1)} - \mathbf{x}^{(j)} \right) \;,\]

  with

  \[t^{(j+1)} = \frac{1}{2} \left( 1 + \sqrt{1 + 4 \; (t^{(j)})^2} \right) \;,\]

  starting with \(t^{(1)} = 1\). This corresponds to the Nesterov’s momentum update. Other updates of the momentum coefficient \(t^{(j+1)}\) are available by deriving from MomentumBase.

  This method should set self.Y as a function of self.X and self.Xprv. (This method is part of the standard PGM formulation [6].)

  The update for the monotone PGM version from [7] corresponds to

  \[\mathbf{y}^{(j+1)} = \mathbf{x}^{(j+1)} + \frac{t^{(j)}}{t^{(j+1)}} \left( \mathbf{z}^{(j+1)} - \mathbf{x}^{(j+1)} \right) + \frac{t^{(j)} - 1}{t^{(j+1)}} \left( \mathbf{x}^{(j+1)} - \mathbf{x}^{(j)} \right) \;,\]

  with \(\mathbf{z}^{(j+1)}\) the proximal mapping computed in PGM.xstep (which may not correspond to \(\mathbf{x}^{(j+1)}\) if it has been replaced by the previous iterate due to the monotone restriction).

A derived class implementing a fully-specified PGM problem (as opposed to a partial specialisation) must define PGM.prox_g, PGM.grad_f, PGM.obfn_f and PGM.obfn_g.

Residual Evaluation

The following methods support evaluation of the residuals:

• PGM.rsdl

  This method has to be defined according to the stopping criterion to use. (It could be the relative difference between consecutive \(\mathbf{x}\) iterates or a fixed point residual evaluating the difference between \(\mathbf{x}\) and \(\mathbf{y}\) states).

Iteration Statistics

There is a flexible but relatively complex mechanism supporting the recording of statistics such as objective function and residual values for each iteration.

IterationStats Definition

These statistics are recorded as a collections.namedtuple class, self.IterationStats. The fields of this namedtuple are defined by class method IterativeSolver.itstat_fields, which returns a tuple of fields consisting of the following components:

• Iter : Iteration number

• A tuple of field names in PGM.itstat_fields_objfn : Fields representing the objective function and and its individual terms

• Rsdl : Norm of residual

• F_Btrack : Evaluation of \(F\) (if backtrack is enabled)

• Q_Btrack : Evaluation of \(Q_L\) (if backtrack is enabled)

• IterBTrack : Number of iterations used in backtrack (if backtrack is enabled)

• L : Inverse of gradient step size.

• A tuple of field names in PGM.itstat_fields_extra : Optional extra fields

• Time : Cumulative run time

In most cases a derived class will simply override PGM.itstat_fields_objfn and PGM.itstat_fields_extra to customise the desired iteration statistics fields, but if more flexibility is required, IterativeSolver.itstat_fields should be overridden.

IterationStats Construction

The actual construction of the self.IterationStats namedtuple for each iteration is performed by PGM.iteration_stats, which expects that self.IterationStats follows the structure defined by IterativeSolver.itstat_fields. Tuples of values corresponding to the fields defined in PGM.itstat_fields_objfn and PGM.itstat_fields_extra should be returned by PGM.eval_objfn and PGM.itstat_extra respectively.

In PGM, PGM.itstat_fields_objfn is defined as the tuple ('ObjFun', 'FVal', 'GVal'), and PGM.eval_objfn constructs the corresponding field values by calls to PGM.obfn_f and PGM.obfn_g, which are expected to return the values of \(f(\mathbf{x})\) and \(g(\mathbf{x})\) respectively. In the simplest case it is sufficient to just define PGM.obfn_f and PGM.obfn_g in a derived class, but in most cases one would instead override PGM.itstat_fields_objfn and PGM.eval_objfn (and possibly PGM.itstat_fields_extra and PGM.itstat_extra as well).

Status Display

When option Verbose is enabled, a summary of the iterations statistics is printed to the standard output. The printing of this summary is controlled by PGM.display_start, PGM.display_status, PGM.display_end, and the state of the Backtrack auxiliary class. These methods will usually not need to be overridden since there is a flexible method of customising the information displayed by these methods.

Class method PGM.hdrtxt returns a tuple of strings which will be displayed as the headings for the displayed columns of iteration statistics, and class method PGM.hdrval constructs a dictionary that defines a mapping between these column heading strings and corresponding field names in the self.IterationStats namedtuple. These two methods can be overridden if necessary, but in most cases it is sufficient to override PGM.hdrtxt_objfn and PGM.hdrval_objfun, which respectively define the header strings and mappings for the statistics related to the objective function (see PGM.itstat_fields_objfn and PGM.eval_objfn in IterationStats Construction).