Bounding convex relaxations of process models from below by tractable black-box sampling

Several chemical engineering applications demand global optimization of nonconvex process models, including safety verification and determination of thermodynamic equilibria. Methods for determinisitic global optimization typically generate crucial bounding information by minimizing convex relaxations of the process model. However, gradients or subgradients of these convex relaxations may be unavailable in practice for several reasons, which may hinder computation of this bounding information. This article shows that useful, correct affine underestimators and lower bounds of convex relaxations may be generated tractably just by black-box sampling. No additional assumptions are required, and no subgradients or gradients must be computed at any point. Variants of these methods are presented to account for numerical error or noise in the sampling procedure. Several numerical examples are presented for illustration, including application of the new sampling-based underestimators in global optimization problems.