Recourse‐based stochastic nonlinear programming: properties and Benders‐SQP algorithms

In this paper, we study recourse‐based stochastic nonlinear programs and make two sets of contributions. The first set assumes general probability spaces and provides a deeper understanding of feasibility and recourse in stochastic nonlinear programs. A sufficient condition, for equality between the sets of feasible first‐stage decisions arising from two different interpretations of almost sure feasibility, is provided. This condition is an extension to nonlinear settings of the ‘W‐condition,’ first suggested by Walkup and Wets (1967). Notions of complete and relatively‐complete recourse for nonlinear stochastic programs are defined and simple sufficient conditions for these to hold are given. Implications of these results on the L‐shaped method are discussed. Our second set of contributions lies in the construction of a scalable, superlinearly convergent method for solving this class of problems, under the setting of a finite sample‐space. We present a novel hybrid algorithm that combines sequential quadratic programming (SQP) and Benders decomposition. In this framework, the resulting quadratic programming approximations while arbitrarily large, are observed to be two‐period stochastic quadratic programs (QPs) and are solved through two variants of Benders decomposition. The first is based on an inexact‐cut L‐shaped method for stochastic quadratic programming while the second is a quadratic extension to a trust‐region method suggested by Linderoth and Wright (2003). Obtaining Lagrange multiplier estimates in this framework poses a unique challenge and are shown to be cheaply obtainable through the solution of a single low‐dimensional QP. Globalization of the method is achieved through a parallelizable linesearch procedure. Finally, the efficiency and scalability of the algorithm are demonstrated on a set of stochastic nonlinear programming test problems.