Piecewise polynomial interpolations and approximations of one-dimensional functions through mixed integer linear programming

Abstract

Piecewise polynomial functions are extensively used to approximate general nonlinear functions or sets of data. In this work, we propose a mixed integer linear programming (MILP) framework for generating optimal piecewise polynomial approximations of varying degrees to nonlinear functions of a single variable. The nonlinear functions may be represented by discrete exact samplings or by data corrupted by noise. We studied two distinct approaches to the problem: (1) the generation of interpolating piecewise polynomial functions, in which the approximating function values in the extremes of each polynomial segment coincide with the original function values; and (2) a de facto approximation strategy in which the polynomial segments are free, except for the enforcement of continuity of the overall approximation. Our results from the implemented models show that the procedure is capable of efficiently approximating nonlinear functions and it has the added capability of allowing for the straightforward implementation of further constraints on solutions, such as the convexity of polynomial segments. Finally, the models for the generation of piecewise linear approximations and interpolations were applied for the linearization of mixed integer nonlinear programming (MINLP) models extracted from the MINLP library. These models were linearized by the reformulation of their nonlinearities as piecewise linear functions with varying numbers of segments, resulting in MILP models that were solved to optimality and the solutions from the linearized models were compared with global optimal solutions from the original problems.

Keywords:

• mixed integer linear programming
• one-dimensional nonlinear functions
• piecewise linear interpolation
• piecewise polynomial approximation