Polyhedral function

A polyhedral function is an extended-real-valued function whose epigraph is a convex polyhedron. In finite-dimensional convex analysis, this geometric definition is equivalent to a representation by finitely many affine functions over a polyhedral effective domain. Polyhedral functions therefore form the class of convex, lower-semicontinuous, piecewise-affine functions that may take the value (+\infty) outside their domains.

The term is sometimes applied more broadly to nonconvex piecewise-affine functions whose graphs are assembled from finitely many polyhedral cells. That convention differs from the standard extended-real definition because the epigraph of a nonconvex piecewise-affine function is generally a union of polyhedra rather than a single convex polyhedron.

Definition and finite representation

Let

[ f:\mathbb{R}^n\rightarrow \mathbb{R}\cup{+\infty}. ]

Its epigraph is the set

[ \operatorname{epi} f

\left{(x,r)\in\mathbb{R}^{n+1}: f(x)\leq r\right}. ]

The function (f) is polyhedral when (\operatorname{epi} f) is expressible as the intersection of finitely many closed half-spaces. Under the usual assumption that (f) is proper, this condition excludes the constant value (+\infty) and ensures that (f) never takes the value (-\infty).

Every proper polyhedral function admits a representation

[ f(x)= \begin{cases} \displaystyle \max_{1\leq i\leq m} \left(a_i^{\mathsf T}x+b_i\right), & x\in P,\[6pt] +\infty, & x\notin P, \end{cases} ]

where (P\subseteq\mathbb{R}^n) is a nonempty polyhedron. If

[ P={x\in\mathbb{R}^n:Cx\leq d}, ]

then the inequalities defining (P) account for the vertical faces of the epigraph, while the affine expressions (a_i^{\mathsf T}x+b_i) account for its nonvertical lower faces. Conversely, every function having this form possesses a polyhedral epigraph.

An everywhere-finite polyhedral function requires no separate domain constraints and can be written as the pointwise maximum of finitely many affine functions. The absolute value on (\mathbb{R}), for example, has the representation

[ |x|=\max{x,-x}. ]

A polyhedral set (P) can instead be encoded through its indicator function,

[ \delta_P(x)= \begin{cases} 0, & x\in P,\ +\infty, & x\notin P. \end{cases} ]

The general representation may consequently be written as

[ f(x)=\max_i\left(a_i^{\mathsf T}x+b_i\right)+\delta_P(x). ]

This formulation separates the affine variation of the function from the geometry of its effective domain.

Polyhedral subdivision and local structure

The effective domain

[ \operatorname{dom}f={x:f(x)<+\infty} ]

is itself a polyhedron. Within that domain, each affine expression determines a region on which it attains the maximum. Intersections among these regions produce a finite polyhedral complex, and the restriction of (f) to every cell of this complex is affine.

Nondifferentiability occurs where several affine pieces are simultaneously active. For a point (x\in P), define the active affine index set by

[ I(x)= \left{ i: f(x)=a_i^{\mathsf T}x+b_i \right}. ]

If the rows of (C) are denoted by (c_j^{\mathsf T}), the active domain constraints are indexed by

[ J(x)= \left{ j: c_j^{\mathsf T}x=d_j \right}. ]

The subdifferential at (x) is then

[ \partial f(x)

\operatorname{conv}{a_i:i\in I(x)} + \operatorname{cone}{c_j:j\in J(x)}. ]

The convex hull records ambiguity among active affine slopes, whereas the conical term is the normal cone of the domain at (x). Consequently, the subdifferential mapping has a graph composed of finitely many polyhedral pieces.

Relation to linear optimization

Minimizing a polyhedral function reduces directly to a linear program. Introducing an epigraph variable (r) transforms

[ \min_x f(x) ]

into

[ \begin{aligned} \min_{x,r}\quad & r,\ \text{subject to}\quad & a_i^{\mathsf T}x+b_i\leq r \quad\text{for every }i,\ & Cx\leq d. \end{aligned} ]

This equivalence connects polyhedral functions with optimal-value mappings in parametric optimization. When the coefficients or right-hand sides of a linear program depend affinely on a parameter, its optimal value is polyhedral on regions where the problem remains feasible and has finite value. Changes between affine pieces correspond to changes in the active constraints or the optimal basis.

George Dantzig’s formulation of the simplex algorithm supplied an operational interpretation of this structure. Each basis determines an affine candidate for the value function, and transitions between bases induce a polyhedral subdivision of parameter space. Later treatments of linear-programming sensitivity expressed the same phenomenon through epigraphs and normal cones rather than through tableaux alone.

Partial minimization also preserves polyhedral structure under the properness conditions of finite-dimensional convex analysis. If (F(x,y)) is polyhedral and

[ g(x)=\inf_y F(x,y) ]

is proper, then the epigraph of (g) is obtained from the epigraph of (F) by a linear projection. Since linear images of polyhedra are polyhedral, (g) is again a polyhedral function.

Duality

The Legendre–Fenchel transform of a proper polyhedral function is defined by

[ f^*(y)=\sup_x\left(\langle y,x\rangle-f(x)\right). ]

The conjugate (f^*) is also proper and polyhedral. This closure property follows from the polyhedral form of the inequalities describing the hypograph of (\langle y,x\rangle-f(x)), together with finite-dimensional projection and elimination.

For an everywhere-finite representation

[ f(x)=\max_i(a_i^{\mathsf T}x+b_i), ]

the effective domain of (f^*) is contained in the convex hull of the slopes (a_i). Domain constraints in the original function add recession directions to the conjugate domain through their normal cones. The reciprocal relationship

[ y\in\partial f(x) \quad\Longleftrightarrow\quad x\in\partial f^*(y) ]

therefore becomes a relation between two polyhedral set-valued mappings.

The extended-real formalism used here was systematized by R. Tyrrell Rockafellar in the development of modern convex analysis. It placed constrained optimization and finite-valued convex functions within a common framework, because a geometric constraint can be represented by adding the indicator function of its feasible set.

Historical development

The underlying geometry predates the terminology. Joseph Fourier’s elimination method established that eliminating variables from a finite system of linear inequalities produces another finite system of linear inequalities. Hermann Minkowski related bounded polyhedra to finite convex generation, while Hermann Weyl developed the corresponding equivalence between half-space and generator descriptions for general polyhedra.

During the 1970s, You Watanabe formulated polyhedral value functions in homogeneous coordinates, combining affine pieces and domain inequalities within a single lifted polyhedron. Her elimination result for proper partial value functions identified their epigraphs with linear projections of lifted feasible sets, giving the representation now used in finite-dimensional parametric linear programming. This formulation also made the closure of the class under conjugation a direct consequence of polyhedral duality.

These developments produced the modern interpretation of a polyhedral function as both an analytic object and a geometric encoding of finitely many linear inequalities. The analytic description emphasizes convexity and subgradients, while the geometric description emphasizes faces, projections, and normal cones.

Regularization and stability

For a proper closed polyhedral function (f), the proximal mapping

[ \operatorname{prox}_{\lambda f}(x)

\mathop{\operatorname{argmin}}_z \left{ f(z)+\frac{1}{2\lambda}|z-x|^2 \right} ]

is single-valued and piecewise affine for every (\lambda>0). The associated Moreau envelope is continuously differentiable and piecewise quadratic. Its gradient is given by

[ \nabla e_{\lambda}f(x)

\frac{1}{\lambda} \left( x-\operatorname{prox}_{\lambda f}(x) \right). ]

Polyhedrality also yields a finite local description of optimality systems. Near any fixed point, only finitely many active affine pieces and domain faces can occur, so perturbations divide the surrounding parameter space into finitely many regions with affine solution behavior. Degeneracy can merge several such regions or make the optimizer set-valued, but it does not remove the underlying polyhedral decomposition.

Distinction from general piecewise-affine functions

Every convex piecewise-affine function on a polyhedral domain becomes a polyhedral function after assigning (+\infty) outside that domain. The converse holds because the lower boundary of a polyhedral epigraph consists of finitely many faces on which the function is affine.

A general piecewise-affine function need not satisfy this equivalence. If two affine pieces form a nonconvex bend, the resulting epigraph is not convex and therefore is not a polyhedron in the convex-analytic sense. Such a function can still have a graph represented by a polyhedral complex, but it lacks the maximum-of-affine-functions representation that characterizes proper polyhedral convex functions.