Subdifferential ($\partial f(x)$)

For a convex function $f$, the subdifferential at $x$ isThe point $x$ minimizes $f$ exactly when $0\in \partial f(x)$.

For a proper convex function finite at $x$, global minimality is equivalent to $0\in \partial f(x)$. This follows immediately from the defining subgradient inequality. Combined with a subdifferential sum rule, it converts a convex minimization problem into an inclusion, for example the equation defining a proximal operator.

Adding the two subgradient inequalities for $p\in \partial f(x)$ and $q\in \partial f(y)$ givesThus the subdifferential is a monotone operator. This inequality proves uniqueness of its resolvent: two solutions of $z\in x+\tau \partial f(x)$ must coincide when $\tau >0$.

For a convex function and $\tau >0$, the forward step is the set-valued explicit update $F_{\tau f}(x)=\{x-\tau p:p\in \partial f(x)\}$. It reduces to the usual gradient step when differentiable. In contrast, a backward step uses a subgradient at the new point and is the proximal operator for a proper closed convex function.

For a convex scalar function $f(x,y)$, the partial subdifferential ${\partial }_{y}f(x,y)$ means the subdifferential of $v\mapsto f(x,v)$ at $v=y$. It is not differentiation of a set-valued subdifferential. If this section is differentiable, the partial subdifferential is the singleton containing ${\nabla }_{y}f(x,y)$.

For a proper lower-semicontinuous convex functional on a real Hilbert space, $p\in \partial J(u)$ means $⟨v,p⟩-J(v)\le ⟨u,p⟩-J(u)$ for all $v$. Taking the supremum gives equality in the Fenchel–Young inequality: $J(u)+J^{\ast }(p)=⟨u,p⟩$. Apply the same argument to $J^{\ast }$ and use the Fenchel-Moreau theorem $J^{\ast \ast }=J$ to obtain the reciprocal subgradient condition.

For a finite convex function $h:\mathbb{R}\to \mathbb{R}$, the function $f(x)=h(c^{T}x+b)$ is convex. The subgradient inequality gives $c\partial h(u)\subseteq \partial f(x)$, where $u=c^{T}x+b$. Conversely, every subgradient $g$ of $f$ annihilates $\ker c^T$, because $f$ is constant on lines in those directions. For $c\ne 0$, write $g=cv$ and test the subgradient inequality at $y=x+(t-u)c/\Vert c{\Vert }_2^2$; this proves $v\in \partial h(u)$. For $c=0$, $f$ is constant and both sides are $\{0\}$ since a finite convex function on the real line has a nonempty subdifferential everywhere.

The subdifferential of the L1 norm consists of vectors $z$ with $z_j=\mathrm{sgn}({\beta }_j)$ when ${\beta }_j\ne 0$ and $z_j\in [-1,1]$ when ${\beta }_j=0$. These coordinate conditions give the Karush-Kuhn-Tucker conditions for Lasso and Square-root Lasso.

For proper convex functions under a standard relative-interior qualification,In particular, if $f$ is differentiable at $x$, then $\partial (f+g)(x)=\nabla f(x)+\partial g(x)$.