(136f) Unipopt: Univariate Projection-Based Optimization without Derivatives

Many design and optimization problems are challenging black-box problems where, due to various reasons, it is not possible to obtain reliable derivative information [1-6]. This has led to the growing importance of derivative-free optimization (DFO). Despite developments in the past, the scale of the problems that can be solved by DFO solvers are relatively small compared to exact gradient-based methods. They also often converge to local optima [7], which may be prohibitive for many applications. In this work, we present a novel derivative-free framework UNIPOPT (UNIvariate Projection-based OPTimization) that is based on projecting all the samples onto a univariate space defined by summation of the decision variables [8]. The projection of the samples results in a point-to-set mapping of the projected variable to multiple function values. We illustrate that a univariate function exists on this map such that its minima is the same as that of the original function. The UNIPOPT framework is based on two key algorithms: (i) EPIC (Envelope PredIctor and Corrector) that identifies the points on this univariate function that is the lower envelope of the point-to-set map, and (ii) LEO (Lower Envelope Optimization) that uses these samples identified by EPIC to optimize the lower envelope.

We have extensively tested the UNIPOPT framework using many test problems from literature. For instance, we applied it to solve 393 bound-constrained black-box problems comprising of 232 nonconvex smooth problems and 161 convex nonsmooth problems taken from Rios and Sahinidis [7]. Its performance has been compared to other DFO solvers such as BOBYQA, ORBIT, SNOBFIT and IMFIL. For the test suite of nonconvex smooth problems, UNIPOPT finds solutions within 1% of the global minima for 10–65% more problems compared to these solvers. For convex nonsmooth problems, UNIPOPT can solve 20-30% more problems to 1% global optimality. In terms of convergence, we show that UNIPOPT converges to local minima when certain conditions are satisfied. The UNIPOPT framework is further extended to handle constrained black-box problems. Specifically, we will present the performance of the algorithm against other DFO solvers that can handle constraints for 92 numerical problems taken from GlobalLib. UNIPOPT finds solutions within 1% of the global optimality for 20-52% more problems than those solved by the other solvers.

References:

[1] Agarwal, A., Biegler, L. T. and Zitney, S. E. A superstructure-based optimal synthesis of PSA cycles for post-combustion CO­₂ capture. AIChE Journal, 56(7):1813-1828, 2010.

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

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

[4] Jia, Z., Davis, E., Muzzio, F. J. and Ierapetritou, M. G. Predictive modeling for pharmaceutical processes using kriging and response surface. Journal of Pharmaceutical Innovation, 4(4):174-186, 2009.

[5] Beykal, B., Boukouvala, F., Floudas, C. A. and Pistikopoulos, E. N. Optimal design of energy systems using constrained grey-box multi-objective optimization, Computers and Chemical Engineering, 2018, https://doi.org/10.1016/j.compchemeng.2018.02.017.

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

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

[8] Bajaj, I. and Hasan, M. M. F. UNIPOPT: Univariate projection-based optimization without derivatives. Under Review.

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