Optimization of constrained and multidimensional black-box problems using convex hull approximation and single-dimension surrogate model
Conference Paper
Overview
Identity
Additional Document Info
View All
Overview
abstract
Copyright American Institute of Chemical Engineers. All rights reserved. Many important optimization problems in science and engineering are black-box, i.e., the analytical forms of the objective function and constraints are hidden or unknown. Identifying unknown feasible region and optimization of high-dimensional problems are the major challenges in black-box optimization. Evaluating black-box functions and their derivatives can be difficult, computationally expensive and unreliable, which limits the use of gradient-based optimization. One approach in derivative-free optimization is to replace expensive black-box functions with inexpensive surrogates through sampling and parameter estimation [1-6]. However, the accuracy of the surrogate models depends on the sampling set, surrogate function type, parameter estimation method, etc. These limitations often restrict the use of surrogate models to low-dimensional problems and few constraints, as the model size, complexity and parameters increase with the number of variables and constraints. In the first part of the work, we present a data-driven approximation of the feasible region of constrained black-box problems without using surrogate models for the constraints. Data-driven construction of convex region has been recently proposed [7]. In this work, we approximate a feasible region (convex or nonconvex, continuous or disjoint) as the region described by the convex hull of feasible samples and their neighboring points, while subtracting the infeasible samples and their neighboring points from the convex hull. We represent each sample and its neighboring points using a Euclidean ball with the sample as its center and with the radius proportional to the minimum constraint satisfaction (if the sample is feasible) or violation (if the sample is infeasible). We solve a linear optimization (LP) model to select the largest Euclidean balls while avoiding any intersection between the feasible and infeasible balls. This increases the accuracy of our convex hull-based approximation as we obtain more samples. The design of experiments (DoE) for new samples is now posed as a packing problem, which is a quadratically constrained program (QCP) and is solved to optimality using a global solver. Unlike surrogate model-based approaches, where we need to postulate a surrogate model and estimate the parameters for each constraint, our method exploits a single global parameter related to the size of the Euclidean balls, irrespective of the number of constraints. In the second part of the work, we propose a novel approach to address high-dimensional black-box problems. Instead of constructing multivariate models, we project the original n-dimensional problem as a separate single-dimensional problem. Specifically, we consider a problem of minimizing F(t), which geometrically can be interpreted as the projection of the original objective function f(xi), i = 1,, n taken in the t-space following certain conditions imposed on the projection and the relations between xiand t. We obtain F(t) such that the minimum of F(t) also corresponds to the solution of the original problem. The overall problem can be now decomposed into the following: fit a single-dimension surrogate model for F(t), minimize F(t) to approximately find t, find xicorresponding to t, and check critically measure for xi. This procedure is repeated iteratively in a trust region framework [8] to converge to an optimum t. The idea is extended to constrained problems by relating the objective function and constraint violations with tand applying filter technique [9] to converge to local optima. In the derivative-free optimization paradigm, these developments can be promising because of the use of (i) a global parameter to approximate the feasible region irrespective of the number of constraints, and (ii) a single-dimension surrogate model to approximate the objective function irrespective of the number of variables. The applicability of the methods described above will be demonstrated on both benchmark blackbox problems and chemical engineering applications.
