PGM¶
The fundamental class from which all PGM algorithms are derived is
PGM
, which supports problems of the form
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:
-
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 ofself.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. -
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 ofself.X
andself.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:
-
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 numberA tuple of field names in
PGM.itstat_fields_objfn
: Fields representing the objective function and and its individual termsRsdl
: Norm of residualF_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 fieldsTime
: 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).