On the Minimum Number of Linear Pieces Required to Approximate Nonlinear Functions under an Accuracy Constraint
Abstract
The approximation of nonlinear functions by piecewise linear functions is a tool commonly used when dealing with mixed-integer nonlinear problems. Typically, by replacing nonlinearities by piecewise linear functions one can transform the problem into a mixed-integer linear problem, which may be substantially easier to solve. However, using approximate functions can produce solutions that are infeasible for the original problem or far from optimal. To control these errors it is useful to bound the error created during the function approximation process. Moreover, obtaining a piecewise linear function with few pieces usually results in an easier to solve mixed-integer linear problem. This leads us to study the Corridor Fitting Problem. It consists in building a piecewise linear function with the minimum number of pieces which approximates a nonlinear function given a bound on the approximation error on each point of the domain. The Corridor Fitting Problem has primarily been addressed for univariate functions or via heuristic approaches for multivariate functions. Notably, for the latter setting, no exact algorithms or established relaxations are currently known. In this work, we explore this aspect and propose exploitable relaxations of the Corridor Fitting Problem in Rm based on a discretization of the domain. We show that a structure of hypergraph coloring problem is induced by the discretization of the domain. We define four relaxations making use of this hypergraph coloring problem. We provide new best upper bounds for the classical instance set in R2 and we derive the first lower bounds for these instances, closing more than a third of the instances from the literature.
Related
- On the Accuracy of Approximate Leave-One-Out with Blockwise Nonsmooth Regularization in High-dimensions
- Constraint Qualifications and Regularity Conditions for Nonlinear Constraint Systems
- Distances on Finite Constraint Systems and LICQ Radii in Nonlinear Programming
- Admissibility-Preserving Constraint Lifting for Conditional Deadbeat Control of Discrete-Time Nonlinear Systems
- ε-𝒱𝒰 spaces and approximate leaves\\ for sublinear composite functions
BibTeX
@misc{duguet2026minimum,
title = {{On the Minimum Number of Linear Pieces Required to Approximate Nonlinear Functions under an Accuracy Constraint}},
author = {Aloïs Duguet and Sandra Ulrich Ngueveu and François Lamothe},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28794},
eprint = {2609.28794},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28794},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - On the Minimum Number of Linear Pieces Required to Approximate Nonlinear Functions under an Accuracy Constraint
AU - Aloïs Duguet
AU - Sandra Ulrich Ngueveu
AU - François Lamothe
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.28794
UR - https://arxiv.org/abs/2609.28794
AB - The approximation of nonlinear functions by piecewise linear functions is a tool commonly used when dealing with mixed-integer nonlinear problems. Typically, by replacing nonlinearities by piecewise linear functions one can transform the problem into a mixed-integer linear problem, which may be substantially easier to solve. However, using approximate functions can produce solutions that are infeasible for the original problem or far from optimal. To control these errors it is useful to bound the error created during the function approximation process. Moreover, obtaining a piecewise linear function with few pieces usually results in an easier to solve mixed-integer linear problem. This leads us to study the Corridor Fitting Problem. It consists in building a piecewise linear function with the minimum number of pieces which approximates a nonlinear function given a bound on the approximation error on each point of the domain. The Corridor Fitting Problem has primarily been addressed for univariate functions or via heuristic approaches for multivariate functions. Notably, for the latter setting, no exact algorithms or established relaxations are currently known. In this work, we explore this aspect and propose exploitable relaxations of the Corridor Fitting Problem in Rm based on a discretization of the domain. We show that a structure of hypergraph coloring problem is induced by the discretization of the domain. We define four relaxations making use of this hypergraph coloring problem. We provide new best upper bounds for the classical instance set in R2 and we derive the first lower bounds for these instances, closing more than a third of the instances from the literature.
ER -