Polynomial-size convex difference decompositions
A function $f : \mathbb{R}^d \to \mathbb{R}$ is continuous piecewise affine if it is affine on each cell of some finite complete polyhedral complex in $\mathbb{R}^d$; its number of pieces is the smallest number of $d$-dimensional cells of such a complex. For a convex such function this is the number of its distinct affine components. Every continuous piecewise affine function is a difference of two convex ones (Melzer for positively homogeneous functions; Kripfganz and Schulze). For positively homogeneous functions on $\mathbb{R}^2$, Tran and Wang constructed a decomposition with the fewest pieces, unique up to adding a linear function; Brandenburg, Grillo and Hertrich showed that their construction does not extend beyond dimension two. They also showed that if $f$ is affine on the cells of a regular polyhedral complex with $\tilde q$ cells of dimension $d$, then $f = g - h$ with $g, h$ convex, continuous, piecewise affine on the same complex, so each with at most $\tilde q$ pieces. Hertrich, Basu, Di Summa and Skutella showed that if $f$ has $p$ distinct affine components, one can take $g$ and $h$ with at most $p^{2d+1}$ pieces each.
Problem. Is there a polynomial $p$ such that for every $d \ge 1$ and every continuous piecewise affine $f : \mathbb{R}^d \to \mathbb{R}$ with $q$ pieces there are convex continuous piecewise affine $g, h : \mathbb{R}^d \to \mathbb{R}$ with $f = g - h$, each with at most $p(d, q)$ pieces? The polynomial, and so its degree, must not depend on $d$, $q$ or $f$.
Source: Brandenburg, Grillo and Hertrich (2026), Problem 9.1 (arXiv 2024).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO, OC
- Keywords
- AIM Open Applied Problems, DC decompositions, piecewise linear functions, polyhedral complexes
References
@article{brandenburg2026,
author = {Brandenburg, Marie-Charlotte and Grillo, Moritz and Hertrich, Christoph},
title = {Decomposition polyhedra of piecewise linear functions},
journal = {Discrete Comput. Geom.},
year = {2026},
doi = {10.1007/s00454-026-00875-1},
eprint = {2410.04907},
archivePrefix = {arXiv},
}
@incollection{melzer1986,
author = {Melzer, D.},
title = {On the expressibility of piecewise-linear continuous functions as the difference of two piecewise-linear convex functions},
booktitle = {Quasidifferential Calculus},
series = {Math. Programming Stud.},
volume = {29},
publisher = {Springer},
year = {1986},
pages = {118--134},
doi = {10.1007/BFb0121142},
}
@article{kripfganz1987,
author = {Kripfganz, A. and Schulze, R.},
title = {Piecewise affine functions as a difference of two convex functions},
journal = {Optimization},
volume = {18},
number = {1},
year = {1987},
pages = {23--29},
doi = {10.1080/02331938708843210},
}
@article{tran2024,
author = {Tran, Ngoc M. and Wang, Jidong},
title = {Minimal representations of tropical rational functions},
journal = {Algebr. Stat.},
volume = {15},
number = {1},
year = {2024},
pages = {27--59},
doi = {10.2140/astat.2024.15.27},
}
@article{hertrich2023,
author = {Hertrich, Christoph and Basu, Amitabh and Di Summa, Marco and Skutella, Martin},
title = {Towards lower bounds on the depth of {ReLU} neural networks},
journal = {SIAM J. Discrete Math.},
volume = {37},
number = {2},
year = {2023},
pages = {997--1029},
doi = {10.1137/22M1489332},
eprint = {2105.14835},
archivePrefix = {arXiv},
}
@misc{aim-polynomial-convex-difference-decomposition,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Polynomial-size convex difference decompositions}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/617-polynomial-convex-difference-decomposition.md},
note = {Entry 617 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00890, "Polynomial-size convex difference decompositions", clopen.solutions.