(183n) Global Optimization of a Class of Black-Box Problems with Bounded Hessian

Data-driven optimization is a practical alternative to optimize problems for a class of problems with unknown algebraic form of the objective function and/or constraints [1-5]. Trust-region based algorithms [6-7] have been proposed in the literature that guarantees convergence to first-order critical point if the model is full linear. However, global optimization of black-box problems is a challenging problem. In this work, we are interested in deterministic global optimization of bound constrained black-box problems.

Constructing a valid underestimator is a major impediment for applying branch and bound algorithm on black-box problems. Note that the lower bound at a node is calculated by minimizing the relaxed problem. Therefore, an underestimator whose minima can be found by performing finite number of evaluations is desirable for it to be used in global optimization of black-box problems.

To this end, edge-concave underestimator is an attractive alternative [8] because its minima lie at one of the corner points. To determine the underestimator, the upper bound of the diagonal elements of the hessian of the original function are needed. Therefore, if we assume to know the maximum of the upper bound of the diagonal elements of the hessian matrix, we can evaluate the underestimator at different x values. When we evaluate the edge-concave underestimator at all the corner points, then the minimum of these points is a valid lower bound of the original function.

In this work, we present a global optimization scheme based on a branch and bound framework. At each node, a valid lower bound is found using the scheme from previous paragraph and BOBYQA [9] is used to find the upper bound. The algorithm is implemented on problems listed in [8 (Table 3)] and all the problems converge to ε-global optimality. For many problems, the number of function evaluations and the nodes explored are economical. For instance, for problem 1 (n=5), the number of nodes explored and function evaluations to obtain global minima are 8 and 240 respectively. For problem 4 (n=5), the number of nodes explored and required function evaluations are 44 and 970 respectively. The algorithm will be implemented on several problems and compared with other DFO solvers to illustrate its effectiveness.

References:

[1] Liu, J., Ploskas, N. and Sahinidis, N. V. Tuning BARON using derivative-free optimization algorithms. Journal of Global Optimization, 1-27, 2018, https://doi.org/10.1007/s10898-018-0640-3.

[2] Fernandes, F. A. Optimization of fischer-tropsch synthesis using neural networks. Chemical Engineering & Technology, 29(4):449-453, 2006.

[3] Palmer, K. and Realff, M. Metamodeling approach to optimization of steady-state flowsheet simulations: Model generation. Chemical Engineering Research and Design, 80(7):760-772, 2002.

[4] Iyer, S. S., Bajaj, I., Balasubramanian, P. and Hasan, M. M. F. Integrated carbon capture and conversion to produce syngas: Novel process design, intensification, and optimization. Industrial & Engineering Chemistry Research, 56(30), 8622-8648, 2017.

[5] Arora, A., Bajaj, I., Iyer, S. S. and Hasan, M. M. F. Optimal synthesis of periodic sorption enhanced reaction processes with application to hydrogen production. Computers and Chemical Engineering, 115, 89-111, 2018.

[6] Conn, A. R., Scheinberg, K. and Vicente, L. N. Global convergence of general derivative-free trust-region algorithms to first-and second-order critical points. SIAM Journal on Optimization, 20(1):387-415, 2009.

[7] Eason, J. P. and Biegler, L. T. A trust region filtter method for glass box/black box optimization. AIChE Journal, 62(9):3124-3136, 2016.

[8] Hasan, M. M. F. An edge-concave underestimator for the global optimization of twice-differentiable nonconvex problems. Journal of Global Optimization, 1-18, 2018 https://doi.org/10.1007/s10898-018-0646-x.

[9] Powell, M. J. D. The BOBYQA algorithm for bound constrained optimization without derivatives. Cambridge, NA Report NA2009/06, University of Cambridge, Cambridge, 2009.