Proximal gradient method: Difference between revisions

Revision as of 12:24, 16 December 2022

Latest revision as of 12:28, 21 June 2025

(6 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|Form of projection}}

{{more footnotes|date=November 2013}}

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

[[File:Frank_Wolfe_vs_Projected_Gradient.webm|thumb|A comparison between the iterates of the projected gradient method (in red) and the [[Frank–Wolfe algorithm|Frank-Wolfe method]] (in green).]]

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

<math>

\operatornamemin_{min}\limits_mathbf{x} \in \mathbb{R}^Nd} \sum_{i=1}^n f_i(\mathbf{x})

</math>

where <math>f_i: \mathbb{R}^Nd \rightarrow \mathbb{R},\ i = 1, \dots, n</math> are possibly non-differentiable [[convex functions]]. The lack of differentiability rules out conventional smooth optimization techniques like the [[Gradient descent|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 <math>f_1, . . . , f_n</math> are used individually so as to yield an easily [[wikt:implementable|implementable]] algorithm. They are called [[proximal]] because each non-differentiable function among <math>f_1, . . . , f_n</math> is involved via its [[Proximal operator|proximity operator]]. Iterative shrinkage thresholding algorithm,<ref>

Line 23 ⟶ 24:

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

</math>

However beyond such problems [[projection operator]]s 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, proximityproximal operators are best suited for other purposes.

== Examples ==