Decomposition Polyhedra of Piecewise Linear Functions
For researchers in optimization and neural network theory, this work provides a geometric characterization of minimal decompositions of CPWL functions, though the results are incremental and domain-specific.
The paper studies the decomposition of continuous piecewise linear (CPWL) functions into a difference of two convex CPWL functions, aiming to minimize the number of linear pieces. It disproves a recent approach, characterizes the set of decompositions as a polyhedron, and shows that minimal decompositions correspond to vertices. The framework yields improved neural network constructions for convex and nonconvex CPWL functions.
In this paper we contribute to the frequently studied question of how to decompose a continuous piecewise linear (CPWL) function into a difference of two convex CPWL functions. Every CPWL function has infinitely many such decompositions, but for applications in optimization and neural network theory, it is crucial to find decompositions with as few linear pieces as possible. This is a highly challenging problem, as we further demonstrate by disproving a recently proposed approach by Tran and Wang [Minimal representations of tropical rational functions. Algebraic Statistics, 15(1):27-59, 2024]. To make the problem more tractable, we propose to fix an underlying polyhedral complex determining the possible locus of nonlinearity. Under this assumption, we prove that the set of decompositions forms a polyhedron that arises as intersection of two translated cones. We prove that irreducible decompositions correspond to the bounded faces of this polyhedron and minimal solutions must be vertices. We then identify cases with a unique minimal decomposition, and illustrate how our insights have consequences in the theory of submodular functions. Finally, we improve upon previous constructions of neural networks for a given convex CPWL function and apply our framework to obtain results in the nonconvex case.