Adaptive selections of sample size and solver iterations in stochastic optimization with applicåation to nonlinear commodity flow problems
Vondrak, David A.
Royset, Johannes O.
Wood, R. Kevin
MetadataShow full item record
We present an algorithm to approximately solve certain stochastic nonlinear programs through sample average approximations. The sample sizes in these approximations are selected by approximately solving optimal control problems defined on a discrete-time dynamic system. The optimal-control problem seeks to minimize the computational effort required to reach a near-optimal objective value of the stochastic nonlinear program. Unknown control-problem parameters such as rate of convergence, computational effort per solver iteration, and optimal value of the program are estimated within a receding horizon framework as the algorithm progresses. The algorithm is illustrated with single-commodity and multi-commodity network flow models. Measured against the best alternative heuristic policy we consider for selecting sample sizes, the algorithm finds a near-optimal objective value on average up to 17% faster. Further, the optimal-control problem also leads to a 40% reduction in standard deviation of computing times over a set of independent runs of the algorithm on identical problem instances. When we modify the algorithm by selecting a policy heuristically in the first stage (only), we improve computing time, on average, by nearly 47% against the best heuristic policy considered, while reducing the standard deviation across the independent runs by 55%.
Showing items related by title, author, creator and subject.
Royset, Johannes O.; Phelps, Chris; Gong, Qi (IEEE, 2013-12);This paper focuses on an optimal control problem in which the objective is to minimize the expectation of a cost functional with stochastic parameters. The inclusion of the stochastic parameters in the objective raises ...
Royset, Johannes O.; Szechtman, Roberto (2012-12);The sample average approximation approach to solving stochastic programs induces a sampling error, caused by replacing an expectation by a sample average, as well as an optimization error due to approximating the solution ...
Phelps, Chris; Royset, Johannes O.; Gong, Qi (Society for Industrial and Applied Mathematics, 2016);In this paper, we introduce the uncertain optimal control problem of determining a control that minimizes the expectation of an objective functional for a system with parameter uncertainty in both dynamics and objective. ...