proximal gradient method

Proximal gradient methods are a generalized form of projection used to solve non-differentiable convex optimization problems.

File:Frank_Wolfe_vs_Projected_Gradient.webm (in green).]]

Many interesting problems can be formulated as convex optimization problems of the form

$\operatorname{min}\limits_{x \in \mathbb{R}^N} \sum_{i=1}^n f_i(x)$

where $f_i: \mathbb{R}^N \rightarrow \mathbb{R},\ i = 1, \dots, n$ are possibly non-differentiable convex functions. The lack of differentiability rules out conventional smooth optimization techniques like the steepest descent method and the conjugate gradient method, but proximal gradient methods can be used instead.

Proximal gradient methods starts by a splitting step, in which the functions $f_1, . . . , f_n$ are used individually so as to yield an easily implementable algorithm. They are called proximal because each non-differentiable function among $f_1, . . . , f_n$ is involved via its proximity operator. Iterative shrinkage thresholding algorithm,

{{cite journal | last1=Daubechies | first1=I | last2=Defrise | first2 = M | last3 = De Mol| first3 = C|author3-link= Christine De Mol | title=An iterative thresholding algorithm for linear inverse problems with a sparsity constraint |journal= Communications on Pure and Applied Mathematics|volume=57 | issue=11 |year=2004|pages=1413–1457| bibcode=2003math......7152D | arxiv=math/0307152 |doi=10.1002/cpa.20042}} projected Landweber, projected gradient, alternating projections, alternating-direction method of multipliers, alternating

split Bregman are special instances of proximal algorithms.Details of proximal methods are discussed in {{cite arXiv |last1=Combettes |first1=Patrick L. |last2= Pesquet |first2=Jean-Christophe |title=Proximal Splitting Methods in Signal Processing|page=|year=2009 |eprint=0912.3522|class=math.OC }}

For the theory of proximal gradient methods from the perspective of and with applications to statistical learning theory, see proximal gradient methods for learning.

Projection onto convex sets (POCS)

One of the widely used convex optimization algorithms is projections onto convex sets (POCS). This algorithm is employed to recover/synthesize a signal satisfying simultaneously several convex constraints. Let $f_i$ be the indicator function of non-empty closed convex set $C_i$ modeling a constraint. This reduces to convex feasibility problem, which require us to find a solution such that it lies in the intersection of all convex sets $C_i$ . In POCS method each set $C_i$ is incorporated by its projection operator $P_{C_i}$ . So in each iteration $x$ is updated as

: $x_{k+1} = P_{C_1} P_{C_2} \cdots P_{C_n} x_k$

However beyond such problems projection operators are not appropriate and more general operators are required to tackle them. Among the various generalizations of the notion of a convex projection operator that exist, proximal operators are best suited for other purposes.

Examples

Special instances of Proximal Gradient Methods are

Notes

References

{{cite book

| last = Rockafellar

| first = R. T.

| authorlink = R. Tyrrell Rockafellar

| title = Convex analysis

| publisher = Princeton University Press

| year = 1970

| location = Princeton

}}

{{ cite book

| last1 = Combettes

| first1 = Patrick L.

| last2 = Pesquet

| first2 = Jean-Christophe

| title = Fixed-Point Algorithms for Inverse Problems in Science and Engineering

| volume = 49

| year = 2011

| pages = 185–212

}}

External links

Stephen Boyd and Lieven Vandenberghe Book, [https://web.stanford.edu/~boyd/cvxbook/ Convex optimization]
[https://web.stanford.edu/class/ee364a/ EE364a: Convex Optimization I] and [https://web.stanford.edu/class/ee364b/ EE364b: Convex Optimization II], Stanford course homepages
[https://people.eecs.berkeley.edu/~elghaoui/Teaching/EE227A/lecture18.pdf EE227A: Lieven Vandenberghe Notes] Lecture 18
[https://github.com/kul-forbes/ProximalOperators.jl ProximalOperators.jl]: a Julia package implementing proximal operators.
[https://github.com/kul-forbes/ProximalAlgorithms.jl ProximalAlgorithms.jl]: a Julia package implementing algorithms based on the proximal operator, including the proximal gradient method.
[http://proximity-operator.net/ Proximity Operator repository]: a collection of proximity operators implemented in Matlab and Python.

Category:Gradient methods