A decomposition method based on SQP for a class of multistage nonlinear stochastic programs

Xinwei Liu and Gongyun Zhao

Multi-stage stochastic programming problems arise in many practical situations, such as production and manpower planning, portfolio selections and so on. Generally, the size of the deterministic equivalent of stochastic programs can be very large and not be solvable directly by optimization approaches. Sequential quadratic programming methods are iterative and very effective for solving medium-size nonlinear programming. Based on scenario analysis, a decomposition method based on SQP for solving a class of multistage nonlinear stochastic programs is proposed, which generates the search direction by solving parallelly a set of quadratic programming subproblems with size much less than the original problem at each iteration. Conjugate gradient methods can be introduced to derive the estimates of the dual multiplier associated with the nonanticipativity constraints. By selecting the step-size to reduce an exact penalty function sufficiently, the algorithm terminates finitely at an approximate optimal solution to the problem with any desirable accuracy.

Research report, Department of Mathematics, National University of Singapore, Singapore 119260

Contact: matliuxw@math.nus.edu.sg