Mathematical Programming Formulations for Piecewise Polynomial Functions

This paper studies mathematical programming formulations for solving optimization problems with piecewise polynomial (PWP) constraint functions. We elaborate on suitable polynomial bases as a means of efficiently representing PWPs in mathematical programs, comparing and drawing connections between the monomial basis, the Bernstein basis, and B-splines. The theory is presented for both continuous and semi-continuous PWPs. Using a disjunctive formulation, we then exploit the characteristic of common polynomial basis functions to significantly reduce the number of nonlinearities, and to suggest a bound-tightening technique for PWP constraints. Upon a standard big-M reformulation yielding an MINLP model, we derive three extensions using logarithmic number of binary variables, Bernstein cuts and an expanded Bernstein basis. Numerical results from solving three test sets of MINLPs to global optimality compares the formulations. The proposed framework shows promising numerical performance, and facilitates the solution of PWP-constrained optimization problems using standard MINLP software.

Article

Download

View Mathematical Programming Formulations for Piecewise Polynomial Functions