Optimization Online


Line search methods with variable sample size for unconstrained optimization

Nataša Krejić (natasak***at***uns.ac.rs)
Nataša Krklec (natasa.krklec***at***dmi.uns.ac.rs)

Abstract: Minimization of unconstrained objective function in the form of mathematical expectation is considered. Sample Average Approximation - SAA method transforms the expectation objective function into a real-valued deterministic function using large sample and thus deals with deterministic function minimization. The main drawback of this approach is its cost. A large sample of the random variable that defines the expectation must be taken in order to get a reasonably good approximation and thus the sample average approximation method assumes very large number of function evaluations. We will present a line search strategy that uses variable sample size and thus makes the process significantly cheaper. Two measures of progress - lack of precision and decrease of function value are calculated at each iteration. Based on these two measures a new sample size is determined. The rule we will present allows us to increase or decrease the sample size in each iteration until we reach some neighborhood of the solution. An additional safeguard check is performed to avoid unproductive sample decrease. Eventually the maximal sample size is reached so the variable sample size strategy generates a solution of the same quality as SAA method but with significantly smaller number of function evaluations. The algorithm is tested on a couple of examples including the discrete choice problem.

Keywords: stochastic optimization, line search, simulations, sample average approximation, variable sample size

Category 1: Global Optimization

Citation: Journal of Computational and Applied Mathematics, Volume 245, June 2013, pages 213-231.


Entry Submitted: 07/07/2011
Entry Accepted: 07/07/2011
Entry Last Modified: 05/31/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society