Subgradient method
= Subgradient method
{wiki}
The subgradient method minimizes a possibly nonsmooth <convex function> by choosing $g_k\in\partial f(x_k)$ and iterating
$$
x_{k+1}=x_k-t_kg_k.
$$
If the <subgradients> are bounded by $G$ and a minimizer is within distance $R$ of $x_0$, a suitable constant or diminishing <step size> finds objective error at most $\epsilon$ in $O(R^2G^2/\epsilon^2)$ iterations.