将分段线性函数分解为凸函数差，寻找最少线性片段的解法。
Decomposition Polyhedra of Piecewise Linear Functions
- 固定多面复形后，分解集合形成多面体结构。
- 最小分解对应该多面体的顶点，且存在唯一解的情形可判定。
- 适用于优化与神经网络构造，尤其对非凸情形有突破。
本文研究连续分段线性（CPWL）函数分解为两个凸CPWL函数之差的方法。尽管每个CPWL函数有无穷多种分解方式，但在优化和神经网络理论中，需寻找线性片段最少的分解，这极具挑战性。我们通过反例推翻了近期由Tran和Wang提出的简化方法。为此，我们假设一个固定的多面复形以限定非线性区域，证明分解集合构成两个平移锥的交集所形成的多面体。我们进一步表明，不可约分解对应该多面体的有界面，而最小分解必为顶点。我们识别出具有唯一最小分解的情形，并揭示其在子模函数理论中的意义。最后，改进了已有凸CPWL函数的神经网络构造方法，并将框架拓展至非凸情况。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。