Adaptive selections of sample size and solver iterations in stochastic optimization with applicåation to nonlinear commodity flow problems
Loading...
Authors
Vondrak, David A.
Subjects
Advisors
Royset, Johannes O.
Date of Issue
2009-03
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
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%.
Type
Thesis
Description
Series/Report No
Department
Operations Research (OR)
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
xvi, 39 p. : ill. ;
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.