(522e) Scalable Global Algorithms for Stochastic Nonlinear Programming

Many large-scale nonlinear programs (NLPs) are block structured and weakly coupled [1,2] (i.e., the NLP is composed of block subproblems problems connected by few complicating variables). For example, a two-stage stochastic program has multiple scenarios connected by first stage variables. Problems arising from parameter estimation and machine learning can also fit in this category.

This presentation introduces a new global optimization algorithm for block structured NLPs that uses a specialized branch and bound strategy. For each node in the branch and bound scheme, a lower bound is constructed by relaxing coupling constraints between complicating variables and an upper bound is constructed by fixing the complicating variables. A key advantage of this approach is that both lower bounding and upper bounding problems can be decomposed into blocks that are solved in parallel to global and local optimality, respectively. Another key property of this approach is that, because the gap between the upper bound and lower bound converges to zero as the bounds of the coupling variables converges to zero, we only need to perform branching on the complicating variables. A similar approach has been recently proposed for stochastic MINLPs [5].

We show how the algorithm can be easily implemented in Julia and interfaced to modeling languages such as JuMP and PLASMO. Our implementation also contains typical global optimization algorithmic features such as convexification, outer approximation, feasibility-based bound tightening (FBBT), optimality-based bound tightening (OBBT), and local search. Numerical experiments are performed on a stochastic optimization formulation for controller tuning and a parameter estimation formulation for microbial community models. We compare the computational results with the commercial solver BARON [3] and with open-source solver SCIP [4], and we show that the new approach achieves significant speedups.

References:

[1] Kang, J., Cao, Y., Word, D.P. and Laird, C.D., 2014. An interior-point method for efficient solution of block-structured NLP problems using an implicit Schur-complement decomposition. Computers & Chemical Engineering, 71, pp.563-573.

[2] Kang, J., Chiang, N., Laird, C.D. and Zavala, V.M., 2015, December. Nonlinear programming strategies on high-performance computers. In Decision and Control (CDC), 2015 IEEE 54th Annual Conference on (pp. 4612-4620). IEEE.

[3] Tawarmalani, M. and Sahinidis, N.V., 2005. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming, 103(2), pp.225-249.

[4] Maher, S.J., Fischer, T., Gally, T., Gamrath, G., Gleixner, A., Gottwald, R.L., Hendel, G., Koch, T., Lübbecke, M.E., Miltenberger, M. and Müller, B., 2017. The SCIP Optimization Suite 4.0.

[5] Li, Xiang, Asgeir Tomasgard, and Paul I. Barton. "Nonconvex generalized Benders decomposition for stochastic separable mixed-integer nonlinear programs." Journal of optimization theory and applications 151.3 (2011): 425.