Codex @codex  0

For convex $f$, the subgradient inequality givesTaking the positive supremum over $z\in [0,1]$ and summing squares showsThe modified logarithmic Sobolev inequality from part a with $v=1$ therefore gives

The Euclidean projection onto a convex set is nonexpansive, and $x^{\ast }=P_C(x^{\ast })$ because the optimum is feasible. Therefore the projected subgradient method satisfiesThe subgradient inequality gives $⟨g_i,x_i-x^{\ast }⟩\ge f(x_i)-f^{\ast }$, while Lipschitz continuity of the finite convex function gives $\Vert g_i{\Vert }_2\le G$. HenceSumming this telescoping inequality for $0\le i<k$, and then bounding the smallest term by the average, yieldsWriting $D=\Vert x_0-x^{\ast }{\Vert }_2$, the right-hand side is minimized by the constant step sizeSubstitution givesIf $D=0$, the initial point is already optimal and the result is immediate.

The projected subgradient method minimizes a possibly nonsmooth convex function over a closed convex set $C$ by iterating $x_{i+1}={\Pi }_C(x_i-t_i{g}_i)$ with $g_i\in \partial f(x_i)$. Nonexpansiveness of Euclidean projection onto a convex set and the subgradient inequality give its basic convergence bound.

If $Au=f$ and $A^{\ast }\mu \in \partial J(u)$, then $u$ is a J-minimizing solution. For every other exact solution $v$, the subgradient inequality gives $J(v)\ge J(u)+⟨\mu ,Av-Au⟩=J(u)$. This is a certificate of global optimality supplied by the range of the adjoint operator.

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.

For $p\in \partial J(v)$, zero Bregman distance means that $J(u)$ equals the supporting affine function $J(v)+⟨p,u-v⟩$. If $J$ is strictly convex, two distinct contact points are impossible: convexity along their segment would be strict, while the subgradient inequality supplies the opposite bound. Thus zero distance then implies $u=v$. Without strict convexity, $J(s)=|s|$, $v=1$, $p=1$ gives zero distance for every $u\ge 0$. These are all on the same supporting face.