FISTA¶
The fundamental class from which all FISTA algorithms are derived is
FISTA
, 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 fista.fista
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 FISTA
should override/define the
methods and attributes in the following sections.
Initialisation¶
The __init__
method of the derived class should call the
FISTA
__init__
method to ensure proper initialisation.
State variable \(\mathbf{x}\) is initialised to zero by
FISTA.xinit
. This method should be overridden if a different
initialization is desired.
Update Steps¶
The FISTA 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\). 
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 method should set
self.Y
as a function ofself.X
andself.Xprv
. 
The bactracking process is an adaptive process to find the optimal step size for the gradient descent (\(L^{1}\)). Backtracking updates
self.L
until the condition \(F \leq Q_L\) is satisfied. These are defined as\[F(\mathbf{x}) = f(\mathbf{x}) + g(\mathbf{x}) \;,\]and
\[Q_L(\mathbf{x},\mathbf{y}) = f(\mathbf{y}) + \langle \mathbf{x}  \mathbf{y}, \nabla f(\mathbf{y}) \rangle + \frac{L}{2} \left\ \mathbf{x}  \mathbf{y} \right\_2^2 + g(\mathbf{x}) \;.\]The backtracking process is optional. It is performed when the
BackTrack
mechanism is enabled.
A derived class implementing a fullyspecified FISTA problem (as
opposed to a partial specialisation) must define
FISTA.eval_proxop
, FISTA.eval_grad
and
FISTA.eval_R
. It is usually not necessary to override
FISTA.compute_backtracking
since it is defined in
FISTA
in terms of calls to FISTA.eval_grad
,
FISTA.eval_R
and FISTA.proximal_step
.
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 number A tuple of field names in
FISTA.itstat_fields_objfn
: Fields representing the objective function and and its individual terms Rsdl
: Norm of residualF_Btrack
: Evaluation of \(F\) (if backtracking is enabled)Q_Btrack
: Evaluation of \(Q_L\) (if backtracking is enabled)IterBTrack
: Number of iterations used in backtracking (if backtracking is enabled)L
: Inverse of gradient step size. A tuple of field names in
FISTA.itstat_fields_extra
: Optional extra fields Time
: Cumulative run time
In most cases a derived class will simply override
FISTA.itstat_fields_objfn
and
FISTA.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 FISTA.iteration_stats
,
which expects that self.IterationStats
follows the structure
defined by IterativeSolver.itstat_fields
. Tuples of values
corresponding to the fields defined in
FISTA.itstat_fields_objfn
and
FISTA.itstat_fields_extra
should be returned by
FISTA.eval_objfn
and FISTA.itstat_extra
respectively.
In FISTA
, FISTA.itstat_fields_objfn
is defined as
the tuple ('ObjFun', 'FVal', 'GVal')
, and
FISTA.eval_objfn
constructs the corresponding field values by
calls to FISTA.obfn_f
and FISTA.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 FISTA.obfn_f
and
FISTA.obfn_g
in a derived class, but in most cases one would
instead override FISTA.itstat_fields_objfn
and
FISTA.eval_objfn
(and possibly
FISTA.itstat_fields_extra
and FISTA.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 FISTA.display_start
,
FISTA.display_status
, FISTA.display_end
, and the
state of the BackTrack
flag. 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 FISTA.hdrtxt
returns a tuple of strings which
will be displayed as the headings for the displayed columns of
iteration statistics, and class method FISTA.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 FISTA.hdrtxt_objfn
and FISTA.hdrval_objfun
,
which respectively define the header strings and mappings for the
statistics related to the objective function (see
FISTA.itstat_fields_objfn
and FISTA.eval_objfn
in
IterationStats Construction).