(373x) Global Optimization of a Class of Black-Box Problems

There are many optimization problems in physics, chemistry, finance, computer science, engineering and operations research for which the analytical expressions of the objective and/or the constraints are unavailable. These are black-box problems where the derivative information is often not available or too expensive to approximate numerically. Obtaining guaranteed lower bound for these problems is a major challenge. We propose a data-driven global optimization method for a class of black-box for which valid lower bounds can be obtained by performing finite number of simulations.

First, a class of black-box problems [1] is considered for which the closed form of the objective and/or constraints are unknown, but it is possible to obtain a global upper bound on the diagonal Hessian elements. This allows the construction of an edge-concave underestimator with vertex polyhedral solution [2]. Evaluating this underestimator at the vertices results in a valid lower bound on the original black-box function. This lower bounding technique is incorporated within a branch-and-bound framework and is guaranteed to converge to ε-global optimum. The computational performance of the method is assessed on several box-constrained nonconvex black-box functions.

Furthermore, the objective function and/or constraints for optimization problems with embedded ODEs cannot be represented explicitly as a function of decision variables. However, it is possible to compute upper bounds of the diagonal elements of the Hessian [3] and this allows to construct tight edge-concave relaxations. Time dependent bounds on the state variables and the diagonal elements of the Hessian are computed by solving an auxiliary set of ODEs that are derived using differential inequalities. The proposed methodology is applied to several global dynamic optimization problems and compared to the existing approaches.

References:

[1] Bajaj, I. and Hasan, M. M. F. Deterministic global derivative-free optimization of black-box problems with bounded Hessian. Optimization Letters, 2019. DOI: https://doi.org/10.1007/s11590-019-01421-0

[2] Hasan, M. M. F. An edge concave underestimator for the global optimization of twice-differentiable nonconvex problems. Journal of Global Optimization, 71(4):735-752, 2018.

[3] Bajaj, I. and Hasan, M. M. F. Global dynamic optimization using edge-concave underestimator. Under Review.