Paper Info
Title
Recourse-based stochastic nonlinear programming: properties and Benders-SQP algorithms
Abstract
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 (SIAM J. Appl. Math. 15:1299---1314, 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 (Comput. Optim. Appl. 24:207---250, 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.
Year
DOI
Venue
2012
10.1007/s10589-010-9316-8
Comp. Opt. and Appl.
Keywords
Field
DocType
Stochastic programming,Nonlinear programming,Almost-sure feasibility,Recourse,W-condition,Sequential quadratic programming,Benders’ decomposition
Mathematical optimization,Hybrid algorithm,Nonlinear system,Lagrange multiplier,Nonlinear programming,Algorithm,Quadratic equation,Quadratic programming,Sequential quadratic programming,Stochastic programming,Mathematics
Journal
Volume
Issue
ISSN
51
1
0926-6003
Citations 
PageRank 
References 
6
0.53
33
Authors
2
Name
Order
Citations
PageRank
Ankur A. Kulkarni110620.95
Uday V. Shanbhag240335.53