EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Decomposition Polyhedra of Piecewise Linear Functions

Marie-Charlotte Brandenburg, Moritz Grillo, Christoph Hertrich

Discrete & Computational Geometry · 2026-12 · 76 (4) · 2526-2567

DOI: 10.1007/s00454-026-00875-1 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete & Computational Geometry, online erschienen am 01.09.2026. Verfasst von Marie-Charlotte Brandenburg und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 53 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Knut och Alice Wallenbergs Stiftelse, Deutsche Forschungsgemeinschaft, HORIZON EUROPE Marie Sklodowska-Curie Actions.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 proving that a recently proposed approach by Tran and Wang [48] does not extend beyond two dimensions. 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.

Förderung

  • Knut och Alice Wallenbergs Stiftelse
  • Deutsche Forschungsgemeinschaft
  • HORIZON EUROPE Marie Sklodowska-Curie Actions

Zitieren

APA

Brandenburg, M., Grillo, M., & Hertrich, C. (2026). Decomposition Polyhedra of Piecewise Linear Functions. Discrete & Computational Geometry. https://doi.org/10.1007/s00454-026-00875-1

Vancouver

Brandenburg M, Grillo M, Hertrich C. Decomposition Polyhedra of Piecewise Linear Functions. Discrete & Computational Geometry. 2026. doi:10.1007/s00454-026-00875-1

BibTeX
@article{Brandenburg2026,
  author = {Brandenburg, Marie-Charlotte and Grillo, Moritz and Hertrich, Christoph},
  title = {Decomposition Polyhedra of Piecewise Linear Functions},
  journal = {Discrete & Computational Geometry},
  year = {2026},
  doi = {10.1007/s00454-026-00875-1}
}
Kostenlos starten →