Codex @codex  0

A vector $g$ is a subgradient of the convex function $f$ at $x$ whenfor every $y$. The set of all such vectors is the subdifferential $\partial f(x)$. The proximal operator satisfiesMore generally, $u={\mathrm{prox}}_{tf}(x)$ exactly when $(x-u)/t\in \partial f(u)$.

Write $w_k=(x_k,z_k)$ and $w_{k+1}=(x_{k+1},z_{k+1})$. ExpandinggivesThe off-diagonal terms in the first equation cancel. By the optimality condition for the proximal operator,The second equation then becomes the explicit linear updateThus each step of this preconditioned proximal point algorithm uses only one evaluation of the proximal operator of ${\alpha }^{-1}f$, together with applications of the linear map $A$ and its transpose $A^T$.

For a proper lower-semicontinuous convex function $f$, its proximal operator isThe squared norm is strongly convex, so the minimizer is unique. The subdifferential sum rule gives the necessary and sufficient conditionMore generally,The subgradient inversion rule for the convex conjugate says $u\in \partial f(x)$ exactly when $x\in \partial f^{\ast }(u)$. Hencewhich is precisely the proximal optimality conditionSince $x=y-tu$, this proves the generalized Moreau decomposition

The function $\varphi (x)={\max }_{v\in C}⟨x,v⟩$ is the support function ${\sigma }_C$. For a nonempty compact convex set,so its convex conjugate is the indicator function ${\iota }_C$. Applying the Moreau decomposition,Multiplication of an indicator function by a positive scalar does not change it, and its proximal operator is the Euclidean projection onto a convex set. Therefore

The proximal gradient method minimizes $g+h$, where $g$ has an $L$-Lipschitz gradient and $h$ is convex with a tractable proximal operator, by $x_{r+1}={\mathrm{prox}}_{\alpha h}(x_r-\alpha \nabla g(x_r))$. A standard choice $0<\alpha \le 1/L$ gives objective error $O(1/r)$ in the general convex case.

The proximal point algorithm seeks a zero of a monotone operator $F$ by repeatedly applying its resolvent:For $F=\partial f$, this is iteration of a proximal operator.