Fitting piecewise linear continuous functions

We consider the problem of fitting a continuous piecewise linear function to a finite set of data points, modeled as a mathematical program with convex objective. We review some fitting problems that can be modeled as convex programs, and then introduce mixed-binary generalizations that allow variability in the regions defining the best-fit function’s domain. We also study the additional constraints required to impose convexity on the best-fit function.

► We study models to fit continuous piecewise linear functions to a finite set of data points.
► We propose two mixed-binary optimization models that allow region variability in the best-fit function domain.
► The first model class chooses a triangulation to impose on a fixed grid for bivariate functions.
► The second fits a convex piecewise linear function defined by a fixed number of affine functions.