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/ .