Global Optimization Of Nonconvex Piecewise Linear Regression Splines

Abstract

Global optimization has been applied to a wide variety of science and engineering design problems. Although numerous global optimization techniques have been developed and studied for decades, when used for complex systems such as the design of an aircraft or an automobile, the results are impractical or not completely satisfactory. One of the main drawbacks is the computational CPU time required to solve these problems. The majority of design problems require a significant number of experiments or simulations in order to find a globally best solution; however a single simulation can take between seconds and days to finish. One way to address the challenge of reducing these computation times is by building approximation models, known as <italic>meta-models</italic> or <italic>surrogate models</italic>. A surrogate model mimics the original model with a reduced number of simulations and has statistical properties that help develop patterns. With a surrogate model, an optimization method can then be applied to locate an optimum in an easier and faster manner; these methods are also well known as surrogate based global optimization methods. In recent years, a number of these types of approaches have been proposed. Some of the most representatives meta-models are: polynomial regression, multivariate adaptive regression splines, radial basis functions, and kriging.The surrogate model used in this study is Multivariate Adaptive Regression Splines (MARS). MARS is a flexible statistical modeling method, particularly useful for high-dimensional problems involving interactions and curvature. MARS terms are based on truncated linear functions, where interaction terms are formed as products. Hence, the univariate terms are piecewise linear, but the interaction terms are not. To enable use of fast mixed integer linear programming methods, the interaction terms of a MARS model are transformed to piecewise linear forms, which are more suitable for optimization. Thus, the purpose of this research is to develop and demonstrate a deterministic global optimization method for a non-convex piecewise linear function generated by a modified version of MARS subject to constraints that include both linear regression models and piecewise linear MARS models. A new mixed integer linear programming (MILP) problem that can optimize the piecewise linear MARS model is formulated by introducing binary integer variables and a new set of inequalities to the model. The MILP problem is then solved by branch-and-bound, which is a widely used algorithm for solving various optimization problems. The MILP problem is adjusted to enable flexibility to handle both continuous and categorical variables. This method is illustrated in an automotive crash safety system design case study for a major US automaker, where satisfactory computational results were obtained. The proposed method is compared with an evolutionary optimization algorithm.