(461e) A Predictor-Corrector Algorithm for Projection-Based Derivative-Free Optimization

With the advent of high-fidelity, complex process modeling and simulation in many areas including computational fluid dynamics-based reactor design [1], Nonlinear Algebraic and Partial Differential Equations (NAPDE)-based multiscale optimization [2] and image processing [3], data-driven methods are gaining more importance than ever. Most often, these optimization problems are formulated as black-box problems where the objective function and/or constraints cannot be expressed analytically as explicit functions of decision variables. This implies that the values of the objective and/or constraints become available only after performing a full-scale simulation and, therefore, derivative information of the objective and/or constraints is expensive. To this end, derivative free optimization (DFO) [4] has emerged as a promising approach to optimize black-box problems [5]. DFO techniques is being increasingly applied in process systems engineering for superstructure optimization [6], process optimization [7-9] and flowsheet optimization [10]. Existing model-based trust region approaches generally take less number of evaluations for smooth problems but they often converge to local minima.

In this work, we present an algorithm to address bound-constrained and multi-dimensional black-box problems based on projection onto a one-dimensional space. Specifically, we consider a problem of minimizing G(t), which can be interpreted as the projection of the original objective function f(x_i), i = 1, …, n taken in the t-space such that t is linear combination of x_i. Additionally, we also provide useful properties of the univariate function G(t) and show that the minimum of G(t) also corresponds to the minimum of f(x). This enables us to solve the original optimization problem in two steps. The first step involves identifying G(t) and is referred as the inner loop [11]. In this work, the inner loop is applied at discrete values of t(t₁, t₂, ..., t_k). Once the solution at the previous t(t_k-1) is known, sensitivity theorem [12] is utilized to obtain close solution for the inner loop at next t(t_k). The second step is optimizing the univariate function G(t) to find the solution of the original problem. We also propose an alternate projection by normalizing t. We compare the performance of the two projections with existing DFO solvers. The step length, α, where α = t_k - t_k-1, is another critical parameter in determining the number of evaluations taken by the algorithm. We have considered and compared two strategies related to the step length. The first strategy uses a fixed or uniform step length. The second strategy uses an adaptive approach where the value of α is revised as the algorithm proceeds, based on the number of evaluations taken in the previous inner loop.

We have tested the algorithm to solve several high-dimensional test problems. For instance, we are able to find the global solution of a 50-dimensional test problem (emfl_eps) in 40,747 evaluations. We also obtain the solutions of explin2, expquad and qrtquad (each of which are 120-dimensional problems) using 85521, 62760 and 89484 function evaluations, respectively. The algorithm is applied to a large set of test problems taken from [5] and compared to existing model-based DFO solvers. The proposed approach performs superior relative to ORBIT [13] and SNOBFIT [14].

 

References:

[1] Zimmermann, S.; Taghipour, F. CFD Modeling of the Hydrodynamics and Reaction Kinetics of FCC Fluidized-Bed Reactors. Industrial and Engineering Chemistry Research, 44 (26):9818–9827, 2005.

[2] Hasan, M. M. F.; First, E. L..; and Floudas, C. A. Cost-effective CO2 capture based on in silico screening of zeolites and process optimization. Physical Chemistry Chemical Physics, 15(40):17601-17618, 2013.

[3] Oeuvray, R.; Bierlaire, M. A new derivative free algorithm for the medical image registration problem. International Journal of Modelling and Simulation,27(2):115-124, 2007.

[4] 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.

[5] Rios, L. M.; Sahinidis, N.V. Derivative-free optimization: a review of algorithms and comparison of software implementations. Journal of Global Optimization, 56(3):1247–1293, 2013.

[6] Henao, C. A.; Maravelias, C. T. Surrogate-based superstructure optimization framework. AIChE Journal, 57(5):1216-1232, 2011.

[7] Nuchitprasittichai, A.; Cremaschi, S. Optimization of CO2 capture process with aqueous amines using response surface methodology. Computers & Chemical Engineering, 35(8):1521-1531, 2011.

[8] Agarwal, A.; Biegler L.T. A trust-region framework for constrained optimization using reduced order modeling. Optimization and Engineering, 14(1):3-35, 2013.

[9] Boukouvala, F.; Hasan, M. M. F.; Floudas, C. A. Global optimization of general constrained grey-box models: new method and its application to constrained PDEs for pressure swing adsorption. Journal of Global Optimization, 67(1):3-42, 2017.

[10] Caballero, J. A.; Grossmann, I. E. An algorithm for the use of surrogate models in modular flowsheet optimization. AIChE Journal, 54(10):2633-2650, 2008.

[11] Bajaj, I.; Hasan, M.M.F. A Novel Derivative-Free Optimization Method based on Single Dimension Projection. In the Proceedings of FOCAPO/CPC, 2017.

[12] Fiacco, A.V. Introduction to sensitivity and stability analysis in nonlinear programming. Academic Press, New York, 1984.

[13] Wild, S.M.; Regis, R.G.; Shoemaker, C.A. ORBIT: Optimization by radial basis function interpolation in trust-regions. SIAM Journal on Scientific Computing, 30(6):3197-3219, 2008.

[14] Huyer, W.; Neumaier, A. SNOBFIT – Stable Noisy Optimization by Branch and Fit. ACM Transactions on Mathematical Software, 35(2):1-25, 2008.