Towards Global Solutions for Nonconvex Two-Stage Stochastic Programs: A Polynomial Lower Approximation Approach

Zhong, Suhan & Cui, Ying & Nie, Jiawang. (2024). Towards Global Solutions for Nonconvex Two-Stage Stochastic Programs: A Polynomial Lower Approximation Approach. SIAM Journal on Optimization. 34. 3477-3505. 10.1137/23M1615516.

This paper tackles the challenging problem of finding global optimal solutions for two-stage stochastic programs with continuous decision variables and nonconvex recourse functions. We introduce a two-phase approach. The first phase involves the construction of a polynomial lower bound for the recourse function through a linear optimization problem over a nonnegative polynomial cone. Given the complex structure of this cone, we employ semidefinite relaxations with quadratic modules to facilitate our computations. In the second phase, we solve a surrogate first-stage problem by substituting the original recourse function with the polynomial lower approximation obtained in the first phase. Our method is particularly advantageous for two reasons: it not only generates global lower bounds for the nonconvex stochastic program, aiding in the certificate of global optimality for prospective solutions like stationary …