1 Definition and basic concepts

A subgradient is a vector that generalizes the derivative for convex functions that may fail to be differentiable at a point. It gives a linear lower approximation to the function, capturing how the graph can be supported by a hyperplane. In convex analysis, subgradients are fundamental because they extend many ideas from smooth calculus to nonsmooth settings.

1.1 Convex functions

A function is convex when its value at a point on any line segment lies below or on the straight line joining the endpoint values. Equivalently, its epigraph forms a convex set. Convexity imposes a strong geometric structure, which makes supporting lines and hyperplanes natural tools for analysis.

1.2 Supporting hyperplanes

A supporting hyperplane touches a convex set without cutting through its interior. For the graph of a convex function, such a hyperplane can lie below the function and meet it at a chosen point. This geometric viewpoint motivates the definition of a subgradient as a slope that supports the function locally in a global way.

1.3 Subgradient at a point

For a convex function \(f\), a vector \(g\) is a subgradient at a point \(x\) if for every \(y\), \[ f(y) \ge f(x) + g^\top (y-x). \] The right-hand side is an affine function that underestimates \(f\). Any subgradient therefore describes a valid first-order lower bound at the point \(x\).

1.4 Subdifferential

The subdifferential of \(f\) at \(x\), often written \(\partial f(x)\), is the set of all subgradients at that point. It may contain one vector, many vectors, or be empty in some nonstandard settings. For convex functions on appropriate domains, the subdifferential summarizes all first-order supporting information at \(x\).

2 Properties

Subgradients preserve several familiar features of derivatives while allowing nondifferentiability. Their behavior is closely tied to the geometry of convex functions and to the structure of optimization problems.

2.1 Existence of subgradients

Subgradients exist at many interior points of convex functions under mild regularity conditions. In finite-dimensional spaces, a convex function typically has at least one subgradient at points where it is finite and locally well behaved. At boundary points or outside the effective domain, existence depends on the function and the ambient set.

2.2 Uniqueness and nonuniqueness

A differentiable point has exactly one subgradient, namely the gradient. At a nondifferentiable point, the subdifferential can contain many elements, reflecting multiple supporting slopes. This nonuniqueness is a key feature that allows subgradients to describe corners, kinks, and flat regions.

2.3 Relationship to differentiability

The subgradient concept reduces to ordinary calculus when a function is smooth, but it remains useful where classical derivatives fail. The size and shape of the subdifferential often indicate whether the function is locally smooth or nonsmooth.

2.3.1 Smooth points

At a smooth point, the function has a unique tangent plane. The subdifferential consists of a single vector equal to the gradient. In this case, the subgradient inequality becomes the usual first-order approximation from differential calculus.

2.3.2 Nondifferentiable points

At a kink or corner, there may be several supporting slopes. The subdifferential then forms a set, often a convex set itself, that captures all valid linear minorants. This makes subgradients particularly useful for piecewise-linear and piecewise-smooth functions.

2.4 Scaling and affine transformations

Subgradients behave predictably under simple transformations. Multiplying a function by a scalar scales its subgradients by the same factor, and adding an affine function shifts them accordingly. These rules help preserve optimization structure under changes of variables and objective normalization.

3 Examples

Concrete examples show how subgradients extend familiar slopes to common nonsmooth functions. Many standard models in optimization and analysis can be understood through these cases.

3.1 Absolute value function

For \(f(x)=x\), the function is differentiable everywhere except at \(x=0\). At positive values, the subgradient is \(1\); at negative values, it is \(-1\). At \(x=0\), the subdifferential is the interval \([-1,1]\), representing all slopes of lines that support the graph at the origin.

3.2 Maximum of functions

For the pointwise maximum of several convex functions, a subgradient is formed from subgradients of the active functions, those achieving the maximum value at the point. This reflects the idea that only the dominating pieces determine the local support. Such maxima are common in robust optimization and piecewise-linear modeling.

3.3 Norms

Norms are convex and often nondifferentiable at the origin. For example, the Euclidean norm has subgradient equal to the normalized vector away from zero, while at zero its subdifferential is the unit ball. Other norms, such as the \(L^1\) norm, have larger nonsmooth sets and are widely used in sparse optimization.

3.4 Indicator functions of convex sets

The indicator function of a convex set is zero on the set and infinite outside it. Its subdifferential at a point in the set is the normal cone, which consists of vectors pointing outward in a supporting sense. This links subgradients to constrained optimization and geometric separation.

4 Subgradient calculus

Subgradient calculus provides rules for combining subgradients of more complicated expressions from simpler ones. These formulas parallel familiar derivative rules but require convexity or related regularity conditions.

4.1 Sum rule

Under suitable assumptions, the subdifferential of a sum is the sum of the subdifferentials. This is especially useful when an objective is built from several convex terms, such as a data-fitting term and a regularizer. The rule supports modular analysis of optimization problems.

4.2 Composition rules

When a convex function is composed with an affine mapping, subgradients transform in a straightforward way through the matrix transpose. More general compositions require additional monotonicity or convexity conditions. These rules are important in statistical estimation and constrained modeling.

4.3 Product-type rules

True product rules are less direct in convex analysis than in smooth calculus. For expressions involving products, one often rewrites the problem or uses specialized convexity arguments. As a result, subgradient formulas for products are more limited and context dependent.

4.4 Chain rule

The chain rule for subgradients describes how first-order information passes through composite mappings. In the affine case, it is particularly clean and widely used in optimization algorithms. More general chain rules may require regularity conditions to ensure exact formulas.

5 Optimality conditions

Subgradients provide a natural language for characterizing minimizers of convex functions. They replace the condition “gradient equals zero” with a broader set-valued criterion.

5.1 First-order necessary conditions

If a convex function attains a minimum at a point, then the zero vector must belong to its subdifferential there. This is the nonsmooth analogue of vanishing gradient conditions. It expresses that no feasible linear perturbation can decrease the function value.

5.2 Convex minimization

For convex minimization problems, the subdifferential criterion is also sufficient: if zero lies in the subdifferential, the point is globally optimal. This strong result is one reason convex optimization is so tractable. It converts a global problem into a first-order test.

5.3 Saddle points and duality

Subgradients also appear in saddle-point formulations and dual optimization. They help identify equilibria between primal and dual variables and describe supporting inequalities that underlie duality theory. In many models, subgradient conditions encode both optimality and constraint satisfaction.

6 Algorithms using subgradients

Because subgradients can be computed or estimated even when gradients do not exist, they form the basis of several iterative methods for optimization. These methods are often simple and robust, though slower than smooth-gradient techniques.

6.1 Subgradient method

The subgradient method updates the current point by moving opposite to a chosen subgradient. Unlike gradient descent, the chosen direction need not point directly toward the steepest decrease. The method is especially useful for large-scale convex problems with nonsmooth objectives.

6.2 Projected subgradient method

When optimization is constrained to a convex set, each step may be followed by a projection back onto the feasible region. This maintains feasibility throughout the iteration process. The projected subgradient method is common in resource allocation and learning with constraints.

6.3 Step-size selection

Step sizes play a central role in performance and convergence. Too large a step can cause instability, while too small a step can slow progress substantially. Typical choices include diminishing sequences and problem-specific schedules designed to balance progress and accuracy.

6.4 Convergence behavior

Subgradient algorithms generally converge more slowly than methods for smooth problems, often at sublinear rates. Their iterates may oscillate, especially near nonsmooth points, but averaged or best-so-far solutions often improve steadily. Despite modest speed, their simplicity and broad applicability make them valuable.

Several nearby ideas in analysis and optimization are closely connected to subgradients. Each provides a different perspective on first-order behavior or convex structure.

7.1 Gradient

The gradient is the classical derivative vector for differentiable multivariable functions. It is the unique subgradient at smooth points of a convex function. Subgradients extend the gradient concept to nonsmooth settings.

7.2 Directional derivative

The directional derivative measures instantaneous change in a specified direction. For convex functions, it is closely related to the subdifferential and can often be recovered from it. This connection helps translate geometric support conditions into one-dimensional rates of change.

7.3 Convex conjugate

The convex conjugate transforms a function into one defined by supremal affine majorization. Subgradients are central to the duality between a convex function and its conjugate. This relationship is fundamental in variational analysis and dual optimization.

7.4 Moreau envelope

The Moreau envelope smooths a convex function by infimal convolution with a quadratic term. It is useful for regularization and algorithm design because it replaces a nonsmooth function with a differentiable approximation. The proximal mapping associated with it is closely linked to subgradient ideas.

8 Applications

Subgradients are used across optimization-driven fields where nonsmooth objectives naturally arise. They help analyze models, prove optimality, and construct iterative solvers.

8.1 Machine learning

In machine learning, subgradients arise in loss functions with absolute-value or hinge-like terms, as well as in regularizers that promote sparsity. They are used in training models that involve piecewise-linear penalties and constrained objectives. Their flexibility makes them suitable for large-scale empirical risk minimization.

8.2 Signal processing

Signal processing often uses convex nonsmooth methods for denoising, compression, and sparse recovery. Subgradient-based techniques help handle penalties that encourage sparse or structured solutions. They also appear in formulations involving norms and indicator constraints.

8.3 Control and economics

In control theory and economics, convex nonsmooth models describe resource limits, costs, and equilibrium conditions. Subgradients provide a compact way to express optimality in systems with kinks or threshold effects. They are useful in analyzing policies, equilibria, and constrained decision problems.