Constructing Optimal Piecewise Quadratic Approximations for Enhancing Deterministic Global Optimization

Mathematical optimization models for a wide range of problems are often nonlinear and computationally challenging. Traditionally, piecewise linear approximation (PWLA) is used to linearize these models, albeit at the cost of increasing problem size. This article explores the use of piecewise quadratic approximation (PWQA) in optimization, leveraging recent advances in solving mixed-integer quadratically constrained programs. We introduce new methods for constructing PWQAs, with both break points and approximation coefficients as decision variables, aiming to minimize the approximation error or the number of pieces. Mixed-integer models are developed to approximate two-dimensional discrete data and extended to univariate scalar functions through a sampling-and-refining strategy. Numerical examples demonstrate the effectiveness of the new PWQA construction approaches, and global optimization studies highlight the advantages of PWQA over PWLA and directly solving the original model.

History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis.

Funding: This research was supported by the National Science Foundation [Grant CBET-2026980].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0909) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0909). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.