(522g) Guaranteed Global Optimization of Expected-Value Minimization Problems with Continuous Ranom Variables

Stochastic programming is a powerful framework for determining optimal design and operational decisions under uncertainty, and is extensively used in manufacturing, chemical processing, power distribution, and wireless communication, to name only a few. In this talk, we propose a new algorithm for globally solving a specific class of stochastic programs with (i) nonconvex models, which arise in chemical processes, water and gas networks, AC power systems, etc.; (ii) continuously distributed random variables (RVs), which characterize uncertainty in, e.g., product demands, returns on investments, and renewable energy resources; (iii) expected-value objective functions; and (iv) no recourse decisions.

In the existing literature, such problems are most commonly addressed using sample-average approximation (SAA), which solves a deterministic approximation using a finite number of sampled scenarios. However, this often provides an unworkable compromise between accuracy and efficiency. Specifically, using too few scenarios can result in approximate solutions that are highly suboptimal or even infeasible. On the other hand, increasing the number of scenarios leads to high computational costs when computing sample-average approximations of the objective and constraints. Moreover, verifying the accuracy of a solution generally requires solving many repeats of the deterministic problem with independent samples, leading to an unmanageable computational burden for many problems of practical interest. Another common approach is the so-called stochastic branch-and-bound (B&B) algorithm. However, unlike standard B&B algorithms, the upper and lower bounds obtained in stochastic B&B are sample-based and are only valid in a probabilistic sense. Thus, stochastic B&B has a nonzero probability of fathoming optimal solutions.

To address these challenges, this talk presents a new Branch-and-Bound (B&B) algorithm that is guaranteed to converge finitely to epsilon-global solutions of nonconvex stochastic programs with continuous RVs, and does so with significantly higher efficiency than existing approaches. This is achieved using discrete approximations based on exhaustive partitions of the uncertainty space rather than on sampled scenarios. A key insight in our approach is that such approximations enable the construction of convergent convex relaxations that rigorously account for discretization error. In turn, this enables the computation of rigorous, deterministic upper and lower bounds that can be exploited within B&B to obtain global solutions with provable accuracy. To our knowledge, no existing approach can provide such deterministic bounds for nonconvex programs with continuous RVs. Moreover, by deterministically bounding the discretization error, it becomes possible to prove infeasibility or suboptimality of regions of the decision space using only coarse partitions of the uncertainty space. Using this insight, we achieve high efficiency by adaptively refining the uncertainty partition as the B&B search proceeds.

Compared to stochastic B&B, our B&B approach is advantageous because it uses deterministic rather than probabilistic upper and lower bounds. Thus, it is impossible to fathom a global solution. Compared to SAA, our approach is more rigorous because it provides epsilon-global solutions finitely, whereas SAA converges to the true solution with probability 1 only as the number of scenarios goes to infinity. Moreover, our approach can be significantly more efficient than SAA because we use a partition of the uncertainty space that is adaptively refined during B&B. In contrast, SAA must use a fixed number of scenarios during optimization, and must begin from scratch if additional scenarios are deemed necessary.

The advantages of our proposed B&B approach will be demonstrated through case studies in chemical reactor design and renewable energy systems.