Subgradienter

Subgradienter is a term used in optimization to denote an algorithm or practitioner that uses subgradients to minimize a function, especially when the function is convex and possibly nondifferentiable. The idea is to replace the gradient with a subgradient, which provides a linear lower bound on the function.

In convex analysis, a vector g is a subgradient of a function f at x if f(y) ≥ f(x) + g^T(y − x) for all y in the domain. The set of all subgradients at x is called the subdifferential, denoted ∂f(x). If f is differentiable at x, ∂f(x) contains only the gradient ∇f(x). Subgradient-based methods use elements g_k ∈ ∂f(x_k) to guide updates.

A typical subgradienter implements an iterative update such as x_{k+1} = x_k − α_k g_k, where g_k ∈ ∂f(x_k) and α_k > 0 is a step size. In constrained problems, the update is often followed by a projection onto a feasible set C: x_{k+1} = P_C(x_k − α_k g_k). A common variant is the averaged subgradient method, which uses the average of iterates to improve convergence behavior.

Convergence properties rely on convexity and step-size rules. For convex f with diminishing steps satisfying ∑ α_k = ∞ and ∑ α_k^2 < ∞, the function values converge to the optimum, with sublinear rates generally of order O(1/√k). Strong convexity or additional structure can yield faster rates. Extensions include the use of Clarke subdifferentials for certain nonconvex problems and specialized variants like proximal or bundle methods that enhance performance.

Applications of subgradient-based approaches include large-scale machine learning problems, regularized optimization (such as L1 penalties), and other nondifferentiable objectives where gradient-based methods are unsuitable.