×

Simultaneous perturbation stochastic approximation of nonsmooth functions. (English) Zbl 1123.90056

Summary: A simultaneous perturbation stochastic approximation (SPSA) method is developed in this paper, using the operators of perturbation with Lipschitz density function. This model enables us to use the approximation of the objective function by twice differentiable functions and to present their gradients by volume integrals. The calculus of the stochastic gradient by means of this presentation and likelihood ratios method is proposed, that can be applied to create SPSA algorithms for a wide class of perturbation densities. The convergence of the SPSA algorithms is proved for Lipschitz objective functions under quite general conditions. The rate of convergence O\((\frac{1}{k^{\gamma}}), 1 < \gamma < 2\) of the developed algorithms is established for functions with a sharp minimum. The dependence of the rate of convergence is explored theoretically as well as by computer simulation. The applicability of the presented algorithm is demonstrated by applying it to the minimization of the mean absolute pricing error for the calibration of the Heston stochastic volatility model.

MSC:

90C15 Stochastic programming
65C05 Monte Carlo methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blum, J., Multidimensional stochastic approximation procedures, Annals of Mathematical Statistics, 25, 4 (1954)
[2] Clarke, F. H., Optimization and Nonsmooth Analysis (1983), John Wiley: John Wiley New York · Zbl 0727.90045
[3] Dieudonné, J., Foundations of Modern Analysis (1960), Academic Press: Academic Press NY, London · Zbl 0100.04201
[4] Donoghue, W. F., Distributions and Fourier Transforms (1969), Academic Press: Academic Press NY, London · Zbl 0188.18102
[5] Dupac, V., Stochastic approximation, (Krishnaiah, P. R.; Sen, P. K., Handbook of Statistics. Nonparametric Methods (1988), Nord Holand: Nord Holand NY) · Zbl 0137.36504
[6] Dvoretzky, A., On stochastic approximation, (Neumann, J., Proceedings of the 3rd Berkeley Symposium of Mathematical Statistics and Probability, vol. I (1956), University of California Press: University of California Press Berkeley), 39-55
[7] Ermoliev, Yu. M., Methods of Stochastic Programming (1976), Nauka: Nauka Moscow, (in Russian)
[8] Ermoliev, Yu. M.; Norkin, V. I.; Wets, R. J.-B., The minimization of semicontinuous functions: Mollifier subgradients, Control and optimization, 3, 1, 149-167 (1995) · Zbl 0822.49016
[9] Granichin, O. N.; Poliak, B. T., Randomized Algorithms for Estimation and Optimization with Almost Arbitrary Errors (2003), Nauka: Nauka Moskow, (in Russian)
[10] Gupal, A. M.; Norkin, V. I., An algorithm for minimization of discontinuous functions, Kibernetika, 73-75 (1977) · Zbl 0349.90109
[11] Heston, S. L., A closed-form solution for options with stochastic volatility with applications to bond and currency options, The Review of Financial Studies, 6, 2, 327-343 (1993) · Zbl 1384.35131
[12] Kiefer, J.; Wolfowitz, J., A stochastic estimation of the maximum of a regression function, Annals of Mathematical Statistics, 23, 3, 462-466 (1952) · Zbl 0049.36601
[13] Kushner, H. J.; Yin, G. G., Stochastic Approximation and Recursive Algorithms and Applications (2003), Springer: Springer NY, Heidelberg, Berlin · Zbl 1026.62084
[14] Kuratowski, K., Topology, vol. II (2003), Academic Press: Academic Press NY
[15] Michalevitch, V. S.; Gupal, A. M.; Norkin, V. I., Methods of Nonconvex Optimization (1987), Nauka: Nauka Moscow, (in Russian) · Zbl 0635.90054
[16] Nurminski, E. A., Numerical Methods for Solving Deterministic and Stochastic Minimax Problems (1979), Naukova Dumka: Naukova Dumka Kiev, (in Russian) · Zbl 0441.90085
[17] Poliak, B. T., Introduction to Optimization, Translations Series in Mathematics and Engineering (1987), Optimization Software, Inc., Publications Division: Optimization Software, Inc., Publications Division New York
[18] Robins, H.; Monro, S., A stochastic approximation method, Annals of Mathematical Statistics, 22, 3, 400-407 (1951) · Zbl 0054.05901
[19] Rockafellar, R. T., Directionally Lipschitzian functions and subdifferential calculus, Proceedings of the London Mathematical Society, 39, 331-355 (1979) · Zbl 0413.49015
[20] Rubinstein, R.; Shapiro, A., Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method (1993), Wiley: Wiley New York, NY · Zbl 0805.93002
[21] Sakalauskas, L., Nonlinear stochastic programming by Monte-Carlo estimators, Informatica, 137, 558-573 (2002) · Zbl 1029.90050
[22] Spall, J. C., Multivariate stochastic approximation using a simultaneous perturbation gradient approximation, IEEE Transactions on Automatic Control, 37, 332-341 (1992) · Zbl 0745.60110
[23] Wasan, M. T., Stochastic approximation. Stochastic approximation, Transactions in Mathematics and Mathematical Physics (1969), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0293.62026
[24] Yudin, D.B., 1965. Qualitative methods for analysis of complex systems. Izv. AN SSSR, Ser. “Technicheskaya. Kibernetika”, No. 1, pp. 3-13 (in Russian).; Yudin, D.B., 1965. Qualitative methods for analysis of complex systems. Izv. AN SSSR, Ser. “Technicheskaya. Kibernetika”, No. 1, pp. 3-13 (in Russian).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.