# sporco.fista.fista¶

Base classes for FISTA algorithms

Classes

`FISTA` (xshape, dtype[, opt]) |
Base class for Fast Iterative Shrinkage/Thresholding algorithm (FISTA) algorithms [4]. |

`FISTADFT` (xshape, dtype[, opt]) |
Base class for FISTA algorithms with gradients and updates computed in the frequency domain. |

## Class Descriptions¶

class`sporco.fista.fista.`

`FISTA`

(xshape,dtype,opt=None)[source]¶Bases:

`sporco.common.IterativeSolver`

Base class for Fast Iterative Shrinkage/Thresholding algorithm (FISTA) algorithms [4]. A robust variant [15] is also supported.

Solve optimisation problems of the form

\[\mathrm{argmin}_{\mathbf{x}} \; f(\mathbf{x}) + g(\mathbf{x}) \;\;,\]where \(f, g\) are convex functions and \(f\) is smooth.

This class is intended to be a base class of other classes that specialise to specific optimisation problems.

After termination of the

`solve`

method, attribute`itstat`

is a list of tuples representing statistics of each iteration. The default fields of the named tuple`IterationStats`

are:

`Iter`

: Iteration number

`ObjFun`

: Objective function value

`FVal`

: Value of smooth objective function component \(f\)

`GVal`

: Value of objective function component \(g\)

`F_Btrack`

: Value of objective function \(f + g\) (see Sec. 2.2 of [4])

`Q_Btrack`

: Value of Quadratic approximation \(Q_L\) (see Sec. 2.3 of [4])

`IterBtrack`

: Number of iterations in backtracking

`Rsdl`

: Residual

`L`

: Inverse of gradient step parameter

`Time`

: Cumulative run time

Parameters:

xshape: tuple of intsShape of working variable X

dtype: data-typeData type for working variables (overridden by ‘DataType’ option)

opt:`FISTA.Options`

objectAlgorithm options

class`Options`

(opt=None)[source]¶Bases:

`sporco.cdict.ConstrainedDict`

ADMM algorithm options.

Options:

`FastSolve`

: Flag determining whether non-essential computation is skipped. When`FastSolve`

is`True`

and`Verbose`

is`False`

, the functional value and related iteration statistics are not computed. If`FastSolve`

is`True`

residuals are also not calculated, in which case the residual-based stopping method is also disabled, with the number of iterations determined only by`MaxMainIter`

.

`Verbose`

: Flag determining whether iteration status is displayed.

`StatusHeader`

: Flag determining whether status header and separator are displayed.

`DataType`

: Specify data type for solution variables, e.g.`np.float32`

.

`X0`

: Initial value for X variable.

`Callback`

: Callback function to be called at the end of every iteration.

`MaxMainIter`

: Maximum main iterations.

`IterTimer`

: Label of the timer to use for iteration times.

`RelStopTol`

: Relative convergence tolerance for fixed point residual (see Sec. 4.3 of [25]).

`L`

: Inverse of gradient step parameter \(L\).

`AutoStop`

: Options for adaptive stoping strategy (fixed point residual, see Sec. 4.3 of [25]).

`Enabled`

: Flag determining whether the adaptive stopping relative parameter strategy is enabled.

`Tau0`

: numerator in adaptive criterion (\(\tau_0\) in [25]).

`BackTrack`

: Options for adaptive L strategy (backtracking, see Sec. 4 of [4] or Robust Fista in [15]).

`Enabled`

: Flag determining whether adaptive inverse step size parameter strategy is enabled. When true, backtracking in Sec. 4 of [4] is used. In combination with the`Robust`

flag it enables the backtracking strategy in [15].

`Robust`

: Flag determining if the robust FISTA update is to be applied as in [15].

`gamma_d`

: Multiplier applied to decrease L when backtracking in robust FISTA (\(\gamma_d\) in [15]).

`gamma_u`

: Multiplier applied to increase L when backtracking in standard FISTA (corresponding to \(\eta\) in [4]) or in robust FISTA (corresponding Total \(\gamma_u\) in [15]).

`MaxIter`

: Maximum iterations of updating L when backtracking.

Parameters:

opt: dict or None, optional (default None)FISTA algorithm options

`fwiter`

= 4¶Field width for iteration count display column

`fpothr`

= 2¶Field precision for other display columns

`itstat_fields_objfn`

= ('ObjFun', 'FVal', 'GVal')¶Fields in IterationStats associated with the objective function; see

`eval_objfun`

`itstat_fields_alg`

= ('Rsdl', 'F_Btrack', 'Q_Btrack', 'IterBTrack', 'L')¶Fields in IterationStats associated with the specific solver algorithm

`itstat_fields_extra`

= ()¶Non-standard fields in IterationStats; see

`itstat_extra`

`hdrtxt_objfn`

= ('Fnc', 'f', 'g')¶Display column headers associated with the objective function; see

`eval_objfun`

`hdrval_objfun`

= {'Fnc': 'ObjFun', 'f': 'FVal', 'g': 'GVal'}¶Dictionary mapping display column headers in

`hdrtxt_objfn`

to IterationStats entries

`solve`

(self)[source]¶Start (or re-start) optimisation. This method implements the framework for the iterations of a FISTA algorithm. There is sufficient flexibility in overriding the component methods that it calls that it is usually not necessary to override this method in derived clases.

If option

`Verbose`

is`True`

, the progress of the optimisation is displayed at every iteration. At termination of this method, attribute`itstat`

is a list of tuples representing statistics of each iteration, unless option`FastSolve`

is`True`

and option`Verbose`

is`False`

.Attribute

`timer`

is an instance of`util.Timer`

that provides the following labelled timers:

`init`

: Time taken for object initialisation by`__init__`

`solve`

: Total time taken by call(s) to`solve`

`solve_wo_func`

: Total time taken by call(s) to`solve`

, excluding time taken to compute functional value and related iteration statistics

`solve_wo_rsdl`

: Total time taken by call(s) to`solve`

, excluding time taken to compute functional value and related iteration statistics as well as time take to compute residuals

`solve_wo_btrack`

: Total time taken by call(s) to`solve`

, excluding time taken to compute functional value and related iteration statistics as well as time take to compute residuals and implemented`BackTrack`

mechanism

`proximal_step`

(self,grad=None)[source]¶Compute proximal update (gradient descent + regularization).

`combination_step`

(self)[source]¶Build next update by a smart combination of previous updates. (standard FISTA [4]).

`standard_backtrack`

(self)[source]¶Estimate step size L by computing a linesearch that guarantees that F <= Q according to the standard FISTA backtracking strategy in [4]. This also updates variable Y.

`robust_backtrack`

(self)[source]¶Estimate step size L by computing a linesearch that guarantees that F <= Q according to the robust FISTA backtracking strategy in [15]. This also updates all the supporting variables.

`eval_linear_approx`

(self,Dxy,gradY)[source]¶Compute term \(\langle \nabla f(\mathbf{y}), \mathbf{x} - \mathbf{y} \rangle\) that is part of the quadratic function \(Q_L\) used for backtracking.

`eval_proxop`

(self,V)[source]¶Compute proximal operator of \(g\).

Overriding this method is required.

classmethod`hdrval`

()[source]¶Construct dictionary mapping display column title to IterationStats entries.

`eval_objfn`

(self)[source]¶Compute components of objective function as well as total contribution to objective function.

`getitstat`

(self)[source]¶Get iteration stats as named tuple of arrays instead of array of named tuples.

`display_start`

(self)[source]¶Set up status display if option selected. NB: this method assumes that the first entry is the iteration count and the last is the L value.

`display_status`

(self,fmtstr,itst)[source]¶Display current iteration status as selection of fields from iteration stats tuple.

`obfn_f`

(self,X)[source]¶Compute \(f(\mathbf{x})\) component of FISTA objective function.

Overriding this method is required (even if

`eval_objfun`

is overriden, since this method is required for backtracking).

class`sporco.fista.fista.`

`FISTADFT`

(xshape,dtype,opt=None)[source]¶Bases:

`sporco.fista.fista.FISTA`

Base class for FISTA algorithms with gradients and updates computed in the frequency domain.

Solve optimisation problems of the form

\[\mathrm{argmin}_{\mathbf{x}} \; f(\mathbf{x}) + g(\mathbf{x}) \;\;,\]where \(f, g\) are convex functions and \(f\) is smooth.

This class specialises class FISTA, but remains a base class for other classes that specialise to specific optimisation problems.

Parameters:

xshape: tuple of intsShape of working variable X (the primary variable)

dtype: data-typeData type for working variables

opt:`FISTADFT.Options`

objectAlgorithm options

class`Options`

(opt=None)[source]¶Bases:

`sporco.fista.fista.Options`

FISTADFT algorithm options.

Options include all of those defined in

`FISTA.Options`

.

Parameters:

opt: dict or None, optional (default None)FISTADFT algorithm options

`postinitialization_backtracking_DFT`

(self)[source]¶Computes variables needed for backtracking when the updates are made in the DFT. (This requires the variables in DFT to have been initialized).

`zzfinit`

(self)[source]¶Return initialiser for working variable ZZ in frequency domain (required for robust FISTA [15]).

`proximal_step`

(self,gradf=None)[source]¶Compute proximal update (gradient descent + constraint). Variables are mapped back and forth between input and frequency domains.

`combination_step`

(self)[source]¶Update auxiliary state by a smart combination of previous updates in the frequency domain (standard FISTA [4]).

`eval_linear_approx`

(self,Dxy,gradY)[source]¶Compute term \(\langle \nabla f(\mathbf{y}), \mathbf{x} - \mathbf{y} \rangle\) (in frequency domain) that is part of the quadratic function \(Q_L\) used for backtracking. Since this class computes the backtracking in the DFT, it is important to preserve the DFT scaling.