We present a data-driven approximation of the feasible region of constrained black-box problems. In the design of many engineering systems, one often needs to choose parameters such that the performance is maximized while satisfying physical, operational, and regulatory constraints. The performance objective and constraints may be obtained only through expensive function evaluation or process plant data. The derivatives in these cases are not always available or expensive to obtain. In such cases, it is often better to use derivative-free method for optimization. Although there is abundance of works/algorithms developed for bound-constrained or unconstrained black-box problems, there is limited literature that addresses constrained problems [1-6]. Recently, Zhang et al. [7] approximated the feasible region by polytopes and formulated it as a mixed-integer linear program. In this work, we approximate the 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 radius proportional to the minimum constraint satisfaction (if the sample is feasible) or violation (if the sample is infeasible). A linear programming problem is solved to choose the largest ball that avoids any intersection between feasible and infeasible samples. The procedure for the approximation of a feasible region proceeds iteratively. At each iteration, new samples are obtained via a computational design of experiments (DoE). The DoE is posed as a packing problem, which is a quadratically constrained program (QCP) and is solved to optimality using a global solver. This procedure is repeated in an iterative manner until the entire domain is mapped by set of convex-hulls and Euclidian balls. Once the feasible region is approximated, optimization is performed by developing surrogate model for the objective function. The algorithm is applied to several test problems and compared to existing solvers to test the effectiveness of the algorithm.
References:
[1] Liuzzi, G.; Lucidi, S. A derivative-free algorithm for inequality constrained nonlinear programming via smoothing of an penalty function. SIAM Journal on Optimization, 20(1):1-29, 2009.
[2] Bertsekas, D.P. Constrained Optimization and Lagrangian Multiplier Methods. Academic Press, New York, 1982.
[3] Xue, D.; Sun, W. On convergence analysis of a derivative-free trust region algorithm for constrained optimization with separable structure. Science China Mathematics, 57(6):1287-1302, 2014.
[4] Eason, J.P.; Biegler, L.T. A trust-region filter method for glass box/black box optimization. AICHE Journal, 62(9):3124-3136, 2016.
[5] Sampaio, Ph.R; Toint, Ph.L. Numerical experience with a derivative-free trust-funnel method for nonlinear optimization problems with general nonlinear constraints. Optimization methods and Software, 31(3):511-534, 2016.
[6] Augustin, F.; Marzouk, Y.M. NOWPAC: A provable convergent derivative-free nonlinear optimizer with path-augmented constraints. Technical report, Massachusetts Institute of Technology, 2014.
[7] Zhang, Q.; Grossmann, I. E.; Sundaramoorthy, A.; Pinto, J. M. Data-driven construction of convex region Surrogate models. Optimization and Engineering, 17(2):289-332, 2015.
