A linear programming approach to difference-of-convex piecewise linear approximation

We address the problem of finding continuous piecewise linear (CPWL) approximations of deterministic functions of any dimension that satisfy any predefined error-tolerance, while keeping the number of polytopes that partition the approximation domain low. Specifically, we focus on overcoming the major computational bottleneck of the CPWL Approximation Algorithm (CPWL-AA) that has been proposed in the recent literature. CPWL-AA uses the difference-of-convex CPWL representation to search CPWL approximations which can partition the approximation domain to have polytopes of any shape. A computational bottleneck of the method is to solve a mixed-integer linear program (MILP) in which the number of binary variables is large for many problems of practical interest. In this paper, we overcome this by introducing a method that obtains a high quality solution of the MILP by iteratively solving a linear program (LP). We further reduce the computational expense by developing a method that treats some constraints in the LP problem as lazy constraints. Through a computational study we demonstrate that the proposed methods substantially reduce the computation time of CPWL-AA, while maintaining high quality CPWL approximations. With this, we demonstrate that we can generate CPWL approximations that satisfy predefined error-tolerances on functions of up to five dimensions within reasonable solution times.