pyproximal.optimization.primal.HQS

pyproximal.optimization.primal.HQS(proxf, proxg, x0, tau, niter=10, z0=None, gfirst=True, callback=None, callbackz=False, show=False)

Half Quadratic splitting

Solves the following minimization problem using Half Quadratic splitting algorithm:

\[\begin{split}\mathbf{x},\mathbf{z} = \argmin_{\mathbf{x},\mathbf{z}} f(\mathbf{x}) + g(\mathbf{z}) \\ s.t. \; \mathbf{x}=\mathbf{z}\end{split}\]

where \(f(\mathbf{x})\) and \(g(\mathbf{z})\) are any convex function that has a known proximal operator.

Parameters

proxfpyproximal.ProxOperator

Proximal operator of f function

proxgpyproximal.ProxOperator

Proximal operator of g function

x0numpy.ndarray

Initial vector

taufloat or numpy.ndarray, optional

Positive scalar weight, which should satisfy the following condition to guarantees convergence: \(\tau \in (0, 1/L]\) where L is the Lipschitz constant of \(\nabla f\). Finally note that \(\tau\) can be chosen to be a vector of size niter such that different \(\tau\) is used at different iterations (i.e., continuation strategy)

niterint, optional

Number of iterations of iterative scheme

z0numpy.ndarray, optional

Initial z vector (not required when gfirst=True

gfirstbool, optional

Apply Proximal of operator g first (True) or Proximal of operator f first (False)

callbackcallable, optional

Function with signature (callback(x)) to call after each iteration where x is the current model vector

callbackzbool, optional

Modify callback signature to (callback(x, z)) when callbackz=True

showbool, optional

Display iterations log

Returns

xnumpy.ndarray

Inverted model

znumpy.ndarray

Inverted second model

Notes

The HQS algorithm can be expressed by the following recursion [1]:

\[\begin{split}\mathbf{z}^{k+1} = \prox_{\tau g}(\mathbf{x}^{k}) \\ \mathbf{x}^{k+1} = \prox_{\tau f}(\mathbf{z}^{k+1})\end{split}\]

for gfirst=False, or

\[\begin{split}\mathbf{x}^{k+1} = \prox_{\tau f}(\mathbf{z}^{k}) \\ \mathbf{z}^{k+1} = \prox_{\tau g}(\mathbf{x}^{k+1})\end{split}\]

for gfirst=False. Note that x and z converge to each other, however if iterations are stopped too early x is guaranteed to belong to the domain of f while z is guaranteed to belong to the domain of g. Depending on the problem either of the two may be the best solution.

1

D., Geman, and C., Yang, “Nonlinear image recovery with halfquadratic regularization”, IEEE Transactions on Image Processing, 4, 7, pp. 932-946, 1995.