Adaptive system optimization using random directions stochastic approximation
This work addresses optimization problems in simulation-based systems, offering incremental improvements in algorithm efficiency for researchers and practitioners in stochastic optimization.
The paper tackles simulation optimization by introducing novel random directions stochastic approximation algorithms, including first-order and second-order schemes with continuous and discrete perturbations, and shows that their Newton method with asymmetric Bernoulli perturbations outperforms an existing method (2SPSA) in terms of efficiency, requiring fewer perturbations and loss measurements per iteration.
We present novel algorithms for simulation optimization using random directions stochastic approximation (RDSA). These include first-order (gradient) as well as second-order (Newton) schemes. We incorporate both continuous-valued as well as discrete-valued perturbations into both our algorithms. The former are chosen to be independent and identically distributed (i.i.d.) symmetric, uniformly distributed random variables (r.v.), while the latter are i.i.d., asymmetric, Bernoulli r.v.s. Our Newton algorithm, with a novel Hessian estimation scheme, requires N-dimensional perturbations and three loss measurements per iteration, whereas the simultaneous perturbation Newton search algorithm of [1] requires 2N-dimensional perturbations and four loss measurements per iteration. We prove the unbiasedness of both gradient and Hessian estimates and asymptotic (strong) convergence for both first-order and second-order schemes. We also provide asymptotic normality results, which in particular establish that the asymmetric Bernoulli variant of Newton RDSA method is better than 2SPSA of [1]. Numerical experiments are used to validate the theoretical results.