Algorithms and Theory

• J. R. Birge, Xiaojun Chen, Liqun Qi, and Zengxin Wei, " A Stochastic Newton Method for Stochastic Quadratic Programs with Recourse," Technical Report, Deparment of Industrial and Operations Engineering, University of Michigan, 1994 (postscript file).

  Abstract

  In this paper, we combine the inexact Newton method with the stochastic decomposition method and present a stochastic Newton method for solving the two-stage stochastic program. We prove that the new method is superlinearly convergent with probability one and a probabilistic error bound $h(N_k)$. The error bound $h(N_k)$ at least has the same order as $||y^k- y^*||$ when $k \to \infty$. In the algorithm, we can control the error bound $h(N_k)$ such that $h(N_k) =o(||y^k-y^*||)$.