scico.optimize.pgm

PGM solvers and auxiliary classes.

Classes

AdaptiveBBStepSize([kappa])	Adaptive Barzilai-Borwein method to determine step size.
BBStepSize()	Scheme for step size estimation based on Barzilai-Borwein method.
LineSearchStepSize([gamma_u, maxiter])	Line search for estimating the step size for PGM solvers.
PGMStepSize()	Base class for computing the PGM step size.
RobustLineSearchStepSize([gamma_d, gamma_u, ...])	Robust line search for estimating the accelerated PGM step size.

class scico.optimize.pgm.PGMStepSize

Bases: object

Base class for computing the PGM step size.

Base class for computing the reciprocal of the step size for PGM solvers.

The PGM solver implemented by PGM addresses a general proximal gradient form that requires the specification of a step size for the gradient descent step. This class is a base class for methods that estimate the reciprocal of the step size (\(L\) in PGM equations).

Attributes:

pgm (PGM) – PGM solver object to which the solver is attached.

internal_init(pgm)

Second stage initializer to be called by PGM.__init__.

Parameters:

pgm (PGM) – Reference to PGM object to which the StepSize object is to be attached.

update(v)

Hook for updating the step size in derived classes.

Hook for updating the reciprocal of the step size in derived classes. The base class does not compute any update.

Parameters:

v (Union[Array, BlockArray]) – Current solution or current extrapolation (if accelerated PGM).

Return type:

float

Returns:

Current reciprocal of the step size.

class scico.optimize.pgm.BBStepSize

Bases: PGMStepSize

Scheme for step size estimation based on Barzilai-Borwein method.

The Barzilai-Borwein method [6] estimates the step size \(\alpha\) as

\[\begin{split}\mb{\Delta x} = \mb{x}_k - \mb{x}_{k-1} \; \\ \mb{\Delta g} = \nabla f(\mb{x}_k) - \nabla f (\mb{x}_{k-1}) \; \\ \alpha = \frac{\mb{\Delta x}^T \mb{\Delta g}}{\mb{\Delta g}^T \mb{\Delta g}} \;\;.\end{split}\]

Since the PGM solver uses the reciprocal of the step size, the value \(L = 1 / \alpha\) is returned.

When applied to complex-valued problems, only the real part of the inner product is used. When the inner product is negative, the previous iterate is used instead.

Attributes:

pgm (PGM) – PGM solver object to which the solver is attached.

Initialize a BBStepSize object.

update(v)

Update the reciprocal of the step size.

Parameters:

v (Union[Array, BlockArray]) – Current solution or current extrapolation (if accelerated PGM).

Return type:

float

Returns:

Updated reciprocal of the step size.

class scico.optimize.pgm.AdaptiveBBStepSize(kappa=0.5)

Bases: PGMStepSize

Adaptive Barzilai-Borwein method to determine step size.

Adaptive Barzilai-Borwein method to determine step size in PGM, as introduced in [59].

The adaptive step size rule computes

\[\begin{split}\mb{\Delta x} = \mb{x}_k - \mb{x}_{k-1} \; \\ \mb{\Delta g} = \nabla f(\mb{x}_k) - \nabla f (\mb{x}_{k-1}) \; \\ \alpha^{\mathrm{BB1}} = \frac{\mb{\Delta x}^T \mb{\Delta x}} {\mb{\Delta x}^T \mb{\Delta g}} \; \\ \alpha^{\mathrm{BB2}} = \frac{\mb{\Delta x}^T \mb{\Delta g}} {\mb{\Delta g}^T \mb{\Delta g}} \;\;.\end{split}\]

The determination of the new steps size is made via the rule

\[\begin{split}\alpha = \left\{ \begin{matrix} \alpha^{\mathrm{BB2}} & \mathrm{~if~} \alpha^{\mathrm{BB2}} / \alpha^{\mathrm{BB1}} < \kappa \; \\ \alpha^{\mathrm{BB1}} & \mathrm{~otherwise} \end{matrix} \right . \;,\end{split}\]

with \(\kappa \in (0, 1)\).

Since the PGM solver uses the reciprocal of the step size, the value \(L = 1 / \alpha\) is returned.

When applied to complex-valued problems, only the real part of the inner product is used. When the inner product is negative, the previous iterate is used instead.

Attributes:

pgm (PGM) – PGM solver object to which the solver is attached.

Initialize a AdaptiveBBStepSize object.

Parameters:

kappa (float) – Threshold for step size selection \(\kappa\).

update(v)

Update the reciprocal of the step size.

Parameters:

v (Union[Array, BlockArray]) – Current solution or current extrapolation (if accelerated PGM).

Return type:

float

Returns:

Updated reciprocal of the step size.

class scico.optimize.pgm.LineSearchStepSize(gamma_u=1.2, maxiter=50)

Bases: PGMStepSize

Line search for estimating the step size for PGM solvers.

Line search for estimating the reciprocal of step size for PGM solvers. The line search strategy described in [8] estimates \(L\) such that \(f(\mb{x}) <= \hat{f}_{L}(\mb{x})\) is satisfied with \(\hat{f}_{L}\) a quadratic approximation to \(f\) defined as

\[\hat{f}_{L}(\mb{x}, \mb{y}) = f(\mb{y}) + \nabla f(\mb{y})^H (\mb{x} - \mb{y}) + \frac{L}{2} \left\| \mb{x} - \mb{y} \right\|_2^2 \;,\]

with \(\mb{x}\) the potential new update and \(\mb{y}\) the current solution or current extrapolation (if accelerated PGM).

Attributes:

pgm (PGM) – PGM solver object to which the solver is attached.

Initialize a LineSearchStepSize object.

Parameters:

• gamma_u (float) – Rate of increment in \(L\).

• maxiter (int) – Maximum iterations in line search.

update(v)

Update the reciprocal of the step size.

Parameters:

v (Union[Array, BlockArray]) – Current solution or current extrapolation (if accelerated PGM).

Return type:

float

Returns:

Updated reciprocal of the step size.

class scico.optimize.pgm.RobustLineSearchStepSize(gamma_d=0.9, gamma_u=2.0, maxiter=50)

Bases: LineSearchStepSize

Robust line search for estimating the accelerated PGM step size.

A robust line search for estimating the reciprocal of step size for accelerated PGM solvers.

The robust line search strategy described in [22] estimates \(L\) such that \(f(\mb{x}) <= \hat{f}_{L}(\mb{x})\) is satisfied with \(\hat{f}_{L}\) a quadratic approximation to \(f\) defined as

\[\hat{f}_{L}(\mb{x}, \mb{y}) = f(\mb{y}) + \nabla f(\mb{y})^H (\mb{x} - \mb{y}) + \frac{L}{2} \left\| \mb{x} - \mb{y} \right\|_2^2 \;,\]

with \(\mb{x}\) the potential new update and \(\mb{y}\) the auxiliary extrapolation state.

Attributes:

pgm (PGM) – PGM solver object to which the solver is attached.

Initialize a RobustLineSearchStepSize object.

Parameters:

• gamma_d (float) – Rate of decrement in \(L\).

• gamma_u (float) – Rate of increment in \(L\).

• maxiter (int) – Maximum iterations in line search.

update(v)

Update the reciprocal of the step size.

Parameters:

v (Union[Array, BlockArray]) – Current solution or current extrapolation (if accelerated PGM).

Return type:

float

Returns:

Updated reciprocal of the step size.