Convergence theory for nonconvex stochastic programming
with an application to mixed logit
F. Bastin, C. Cirillo and Ph. L. Toint
Report 03/19
Monte-Carlo methods have been used extensively in the area of stochastic
programming. As with other methods that involve a level of uncertainty,
theoretical properties are required in order to give an indication of their
performance. Traditional convergence properties of Monte Carlo methods in
stochastic programming consider global minimizers of the sample average
approximation (SAA) problems as well as of the true problem. In this paper we
extend these results to the case where computed solutions are only local or
even first-order critical, in turn allowing for problems whose objective
function is nonconvex. As an application, we use the proposed framework in
the estimation of mixed logit models for discrete choice, guaranteeing almost
sure convergence of the solutions of the successive SAA problems. The result
is observed to hold both for constrained and unconstrained problems. Finally,
we produce estimates of the simulation bias and variance.