Piecewise affine functions and polyhedral sets

Abstract

We present a number of characterizations of piecewise affine and piecewise linear functions defined on finite-dimensional normed vector spaces. In particular, we prove that a real-valued function is piecewise affine [resp., piecewise linear] if both its epigraph and its hypograph are (nonconvex) polyhedral sets [resp., polyhedral cones]. Also, we show that the collection of all piecewise affine [resp., piecewise linear] functions coincides with the smallest vector lattice containing the vector space of affine [resp. linear] functions. Furthermore, we prove that a function is piecewise affine [resp. piecewise linear] if it can be represented as a difference of two convex [resp. sublinear] polyhedral functions.