sporco.pgm.pgm¶
Base classes for PGM algorithms.
Classes
|
Base class for Proximal Gradient Method (PGM) algorithms (see for example Ch. |
|
Base class for PGM algorithms with gradients and updates computed in the frequency domain. |
Class Descriptions¶
- class sporco.pgm.pgm.PGM(*args, **kwargs)[source]¶
Bases:
IterativeSolver
Base class for Proximal Gradient Method (PGM) algorithms (see for example Ch. 10 of [5] and Sec. 4.2 and 4.3 of [39]). Algorithms such as FISTA [6] and a robust variant of FISTA [22] are 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, attributeitstat
is a list of tuples representing statistics of each iteration. The default fields of the named tupleIterationStats
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 [6]) when backtracking
Q_Btrack
: Value of Quadratic approximation \(Q_L\) (see Sec. 2.3 of [6]) when backtracking
IterBtrack
: Number of iterations in backtracking
Rsdl
: Residual
L
: Inverse of gradient step parameter
Time
: Cumulative run time
- Parameters:
- xshapetuple of ints
Shape of working variable X
- dtypedata-type
Data type for working variables (overridden by ‘DataType’ option)
- opt
PGM.Options
objectAlgorithm options
- class Options(opt=None)[source]¶
Bases:
ConstrainedDict
PGM algorithm options.
Options:
FastSolve
: Flag determining whether non-essential computation is skipped. WhenFastSolve
isTrue
andVerbose
isFalse
, the functional value and related iteration statistics are not computed. IfFastSolve
isTrue
residuals are also not calculated, in which case the residual-based stopping method is also disabled, with the number of iterations determined only byMaxMainIter
.
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 [33]).
L
: Inverse of gradient step parameter \(L\).
AutoStop
: Options for adaptive stopping strategy (fixed point residual, see Sec. 4.3 of [33]).
Enabled
: Flag determining whether the adaptive stopping relative parameter strategy is enabled.
Tau0
: numerator in adaptive criterion (\(\tau_0\) in [33]).
Monotone
: Flag determining whether a monotone PGM version from [7] is used. Default is False.
Momentum
: Momentum coefficient adaptation object. Standard options are Nesterov [6] (MomentumNesterov
), Linear [14] (MomentumLinear
), and GenLinear [40] (MomentumGenLinear
), but a custom class derived fromMomentumBase
may also be specified. Default isMomentumNesterov
.
StepSizePolicy
: non-iterative L adaptation object. Standard options are Cauchy [63] Sec. 3 (StepSizePolicyCauchy
), and Barzilai-Borwein [4] (StepSizePolicyBB
), but a custom class derived fromStepSizePolicyBase
may also be specified. Default is None, no non-iterative L adaptation. Note that in case that both step size and Backtrack strategies are enabled only Backtrack will be used.
Backtrack
: PGM backtracking options. Options are Standard [6] (BacktrackStandard
) and Robust [22] (BacktrackRobust
), but a custom class derived fromBacktrackBase
may also be specified. Default is None, no backtracking. Note that in case that both step size and Backtrack strategies are enabled only Backtrack will be used.
- Parameters:
- optdict or None, optional (default None)
PGM algorithm options
- defaults = {'AutoStop': {'Enabled': False, 'Tau0': 0.01}, 'Backtrack': None, 'Callback': None, 'DataType': None, 'FastSolve': False, 'IterTimer': 'solve', 'L': None, 'MaxMainIter': 1000, 'Momentum': <sporco.pgm.momentum.MomentumNesterov object>, 'Monotone': False, 'RelStopTol': 0.001, 'StatusHeader': True, 'StepSizePolicy': None, 'Verbose': False, 'X0': None}¶
Default content and allowed dict keys
- 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()[source]¶
Start (or re-start) optimisation. This method implements the framework for the iterations of a PGM 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
isTrue
, the progress of the optimisation is displayed at every iteration. At termination of this method, attributeitstat
is a list of tuples representing statistics of each iteration, unless optionFastSolve
isTrue
and optionVerbose
isFalse
.Attribute
timer
is an instance ofutil.Timer
that provides the following labelled timers:
init
: Time taken for object initialisation by__init__
solve
: Total time taken by call(s) tosolve
solve_wo_func
: Total time taken by call(s) tosolve
, excluding time taken to compute functional value and related iteration statistics
solve_wo_rsdl
: Total time taken by call(s) tosolve
, 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) tosolve
, excluding time taken to compute functional value and related iteration statistics as well as time take to compute residuals and implementedBacktrack
mechanism
- xstep(grad=None)[source]¶
Compute proximal update (gradient descent + regularization). Optionally, a monotone PGM version from [7] is available.
- ystep()[source]¶
Build next update by a smart combination of previous updates (standard PGM [6]). Optionally, a monotone PGM version from [7] is available.
- eval_linear_approx(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.
- classmethod hdrval()[source]¶
Construct dictionary mapping display column title to IterationStats entries.
- eval_objfn()[source]¶
Compute components of objective function as well as total contribution to objective function.
- display_start()[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(fmtstr, itst)[source]¶
Display current iteration status as selection of fields from iteration stats tuple.
- var_momentum()[source]¶
Most momentum coefficient methods require iteration but Nesterov requires current t.
- obfn_f(X)[source]¶
Compute \(f(\mathbf{x})\) component of PGM objective function.
Overriding this method is required (even if
eval_objfun
is overriden, since this method is required for backtracking).
- class sporco.pgm.pgm.PGMDFT(*args, **kwargs)[source]¶
Bases:
PGM
Base class for PGM 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 PGM, but remains a base class for other classes that specialise to specific optimisation problems.
- Parameters:
- xshapetuple of ints
Shape of working variable X (the primary variable)
- Nvtuple of ints
Shape of spatial indices of variable X (needed for DFT)
- axisNtuple of ints
Axis indices of spatial components of X (needed for DFT)
- dtypedata-type
Data type for working variables
- opt
PGMDFT.Options
objectAlgorithm options
- class Options(opt=None)[source]¶
Bases:
Options
PGMDFT algorithm options.
Options include all of those defined in
PGM.Options
.
- Parameters:
- optdict or None, optional (default None)
PGMDFT algorithm options
- defaults = {'AutoStop': {'Enabled': False, 'Tau0': 0.01}, 'Backtrack': None, 'Callback': None, 'DataType': None, 'FastSolve': False, 'IterTimer': 'solve', 'L': None, 'MaxMainIter': 1000, 'Momentum': <sporco.pgm.momentum.MomentumNesterov object>, 'Monotone': False, 'RelStopTol': 0.001, 'StatusHeader': True, 'StepSizePolicy': None, 'Verbose': False, 'X0': None}¶
Default content and allowed dict keys
- xstep(gradf=None)[source]¶
Compute proximal update (gradient descent + constraint). Variables are mapped back and forth between input and frequency domains. Optionally, a monotone PGM version from [7] is available.
- ystep()[source]¶
Update auxiliary state by a smart combination of previous updates in the frequency domain (standard PGM [6]). Optionally, a monotone PGM version from [7] is available.
- eval_linear_approx(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.