Problem types and algorithms

Warning

This page is under construction, and may be incomplete.

Depending on the structure a problem can be reduced to, different types of algorithms will apply. The major distinctions are in the number of objective terms, whether any of them is differentiable, whether they are composed with some linear mapping (which in general complicates evaluating the proximal mapping). Based on this we can split problems, and algorithms that apply to them, in three categories:

Two-terms: $f + g$
Three-terms: $f + g + h$
Primal-dual: $f + g + h \circ L$

In what follows, the list of available algorithms is given, with links to the documentation for their constructors and their underlying iterator type.

Two-terms: $f + g$

This is the most popular model, by far the most thoroughly studied, and an abundance of algorithms exist to solve problems in this form.

Algorithm	Assumptions	Oracle	Implementation	References
Proximal gradient	$f$ smooth	$\nabla f$, $\operatorname{prox}_{\gamma g}$	`ForwardBackward`	Pierre-Louis Lions, Bertrand Mercier (1979)
Douglas-Rachford		$\operatorname{prox}_{\gamma f}$, $\operatorname{prox}_{\gamma g}$	`DouglasRachford`	Jonathan Eckstein, Dimitri P Bertsekas (1992)
Fast proximal gradient	$f$ convex, smooth, $g$ convex	$\nabla f$, $\operatorname{prox}_{\gamma g}$	`FastForwardBackward`	Paul Tseng (2008), Amir Beck, Marc Teboulle (2009)
PANOC	$f$ smooth	$\nabla f$, $\operatorname{prox}_{\gamma g}$	`PANOC`	Lorenzo Stella, Andreas Themelis, Pantelis Sopasakis, Panagiotis Patrinos (2017)
ZeroFPR	$f$ smooth	$\nabla f$, $\operatorname{prox}_{\gamma g}$	`ZeroFPR`	Andreas Themelis, Lorenzo Stella, Panagiotis Patrinos (2018)
Douglas-Rachford line-search	$f$ smooth	$\operatorname{prox}_{\gamma f}$, $\operatorname{prox}_{\gamma g}$	`DRLS`	Andreas Themelis, Lorenzo Stella, Panagiotis Patrinos (2020)
PANOC+	$f$ locally smooth	$\nabla f$, $\operatorname{prox}_{\gamma g}$	`PANOCplus`	Alberto De Marchi, Andreas Themelis (2021)

ProximalAlgorithms.ForwardBackward — Function

ForwardBackward(; <keyword-arguments>)

Constructs the forward-backward splitting algorithm [1].

This algorithm solves optimization problems of the form

minimize f(x) + g(x),

where f is smooth.

The returned object has type IterativeAlgorithm{ForwardBackwardIteration}, and can be called with the problem's arguments to trigger its solution.

Arguments

maxit::Int=10_000: maximum number of iteration
tol::1e-8: tolerance for the default stopping criterion
stop::Function: termination condition, stop(::T, state) should return true when to stop the iteration
solution::Function: solution mapping, solution(::T, state) should return the identified solution
verbose::Bool=false: whether the algorithm state should be displayed
freq::Int=100: every how many iterations to display the algorithm state
display::Function: display function, display(::Int, ::T, state) should display a summary of the iteration state
kwargs...: additional keyword arguments to pass on to the ForwardBackwardIteration constructor upon call

References

Lions, Mercier, “Splitting algorithms for the sum of two nonlinear operators,” SIAM Journal on Numerical Analysis, vol. 16, pp. 964–979 (1979).

source

ProximalAlgorithms.ForwardBackwardIteration — Type

ForwardBackwardIteration(; <keyword-arguments>)

Iterator implementing the forward-backward splitting algorithm [1].

This iterator solves optimization problems of the form

minimize f(x) + g(x),

where f is smooth.

Three-terms: $f + g + h$

When more than one non-differentiable term is there in the objective, algorithms from the previous section do not in general apply out of the box, since $\operatorname{prox}_{\gamma (g + h)}$ does not have a closed form unless in particular cases. Therefore, ad-hoc iteration schemes have been studied.

Algorithm	Assumptions	Oracle	Implementation	References
Davis-Yin	$f$ convex and smooth, $g, h$ convex	$\nabla f$, $\operatorname{prox}_{\gamma g}$, $\operatorname{prox}_{\gamma h}$	`DavisYin`	Damek Davis, Wotao Yin (2017)

ProximalAlgorithms.DavisYin — Function

DavisYin(; <keyword-arguments>)

Constructs the Davis-Yin splitting algorithm [1].

This algorithm solves convex optimization problems of the form

minimize f(x) + g(x) + h(x),

where f is smooth.

The returned object has type IterativeAlgorithm{DavisYinIteration}, and can be called with the problem's arguments to trigger its solution.

Arguments

maxit::Int=10_000: maximum number of iteration
tol::1e-8: tolerance for the default stopping criterion
stop::Function: termination condition, stop(::T, state) should return true when to stop the iteration
solution::Function: solution mapping, solution(::T, state) should return the identified solution
verbose::Bool=false: whether the algorithm state should be displayed
freq::Int=100: every how many iterations to display the algorithm state
display::Function: display function, display(::Int, ::T, state) should display a summary of the iteration state
kwargs...: additional keyword arguments to pass on to the DavisYinIteration constructor upon call

References

Davis, Yin. "A Three-Operator Splitting Scheme and its Optimization Applications", Set-Valued and Variational Analysis, vol. 25, no. 4, pp. 829–858 (2017).

source

ProximalAlgorithms.DavisYinIteration — Type

DavisYinIteration(; <keyword-arguments>)

Iterator implementing the Davis-Yin splitting algorithm [1].

This iterator solves convex optimization problems of the form

minimize f(x) + g(x) + h(x),

where f is smooth.

Primal-dual: $f + g + h \circ L$

When a function $h$ is composed with a linear operator $L$, the proximal operator of $h \circ L$ does not have a closed form in general. For this reason, specific algorithms by the name of "primal-dual" splitting schemes are often applied to this model.

Algorithm	Assumptions	Oracle	Implementation	References
Chambolle-Pock	$f\equiv 0$, $g, h$ convex, $L$ linear operator	$\operatorname{prox}_{\gamma g}$, $\operatorname{prox}_{\gamma h}$, $L$, $L^*$	`ChambollePock`	Antonin Chambolle, Thomas Pock (2011)
Vu-Condat	$f$ convex and smooth, $g, h$ convex, $L$ linear operator	$\nabla f$, $\operatorname{prox}_{\gamma g}$, $\operatorname{prox}_{\gamma h}$, $L$, $L^*$	`VuCodat`	Bằng Công Vũ (2013), Laurent Condat (2013)
AFBA	$f$ convex and smooth, $g, h$ convex, $L$ linear operator	$\nabla f$, $\operatorname{prox}_{\gamma g}$, $\operatorname{prox}_{\gamma h}$, $L$, $L^*$	`AFBA`	Puya Latafat, Panagiotis Patrinos (2017)

ProximalAlgorithms.ChambollePock — Function

ChambollePock(; <keyword-arguments>)

Constructs the Chambolle-Pock primal-dual algorithm [1].

This algorithm solves convex optimization problems of the form

minimize g(x) + h(L x),

where g and h are possibly nonsmooth, and L is a linear mapping.

The returned object has type IterativeAlgorithm{AFBAIteration}, and can be called with the problem's arguments to trigger its solution.

Arguments

maxit::Int=10_000: maximum number of iteration
tol::1e-5: tolerance for the default stopping criterion
stop::Function: termination condition, stop(::T, state) should return true when to stop the iteration
solution::Function: solution mapping, solution(::T, state) should return the identified solution
verbose::Bool=false: whether the algorithm state should be displayed
freq::Int=100: every how many iterations to display the algorithm state
display::Function: display function, display(::Int, ::T, state) should display a summary of the iteration state
kwargs...: additional keyword arguments to pass on to the AFBAIteration constructor upon call

References

Chambolle, Pock, "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging", Journal of Mathematical Imaging and Vision, vol. 40, no. 1, pp. 120-145 (2011).

source

ProximalAlgorithms.ChambollePockIteration — Function

ChambollePockIteration(; <keyword-arguments>)

Iterator implementing the Chambolle-Pock primal-dual algorithm [1].

This iterator solves convex optimization problems of the form

minimize g(x) + h(L x),

where g and h are possibly nonsmooth, and L is a linear mapping.

See also: AFBAIteration, ChambollePock.

This iteration is equivalent to AFBAIteration with theta=2, f=Zero(), l=IndZero(); for all other arguments see AFBAIteration.

References

Chambolle, Pock, "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging", Journal of Mathematical Imaging and Vision, vol. 40, no. 1, pp. 120-145 (2011).

source

ProximalAlgorithms.VuCondat — Function

VuCondat(; <keyword-arguments>)

Constructs the Vũ-Condat primal-dual algorithm [1, 2].

This algorithm solves convex optimization problems of the form

minimize f(x) + g(x) + (h □ l)(L x),

where f is smooth, g and h are possibly nonsmooth and l is strongly convex. Symbol □ denotes the infimal convolution, and L is a linear mapping.

The returned object has type IterativeAlgorithm{AFBAIteration}, and can be called with the problem's arguments to trigger its solution.

Arguments

maxit::Int=10_000: maximum number of iteration
tol::1e-5: tolerance for the default stopping criterion
stop::Function: termination condition, stop(::T, state) should return true when to stop the iteration
solution::Function: solution mapping, solution(::T, state) should return the identified solution
verbose::Bool=false: whether the algorithm state should be displayed
freq::Int=100: every how many iterations to display the algorithm state
display::Function: display function, display(::Int, ::T, state) should display a summary of the iteration state
kwargs...: additional keyword arguments to pass on to the AFBAIteration constructor upon call

References

Condat, "A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms", Journal of Optimization Theory and Applications, vol. 158, no. 2, pp 460-479 (2013).
Vũ, "A splitting algorithm for dual monotone inclusions involving cocoercive operators", Advances in Computational Mathematics, vol. 38, no. 3, pp. 667-681 (2013).

source

ProximalAlgorithms.VuCondatIteration — Function

VuCondatIteration(; <keyword-arguments>)

Iterator implementing the Vũ-Condat primal-dual algorithm [1, 2].

This iterator solves convex optimization problems of the form

minimize f(x) + g(x) + (h □ l)(L x),

where f is smooth, g and h are possibly nonsmooth and l is strongly convex. Symbol □ denotes the infimal convolution, and L is a linear mapping.

This iteration is equivalent to AFBAIteration with theta=2; for all other arguments see AFBAIteration.