Abstract
A new stochastic subgradient algorithm for solving convex stochastic programming problems is described. It uses an auxiliary filter to average stochastic subgradients observed and is provided with on-line rules for determining stepsizes and filter gains in the course of computation. Convergence with probability one is proved and numerical examples are described.
Preview
Unable to display preview. Download preview PDF.
References
Yu.M. Ermol’ev, “On a method of generalized stochastic gradients and stochastic quasi-Fejer sequences”, Kibernetika 2 (1969) 73–83 [in Russian]. Cybernetics 5 (1969) 208–220.
Yu.M. Ermol’ev, Stochastic programming methods (Nauka, Moscow, 1976, [in Russian].
Yu.M. Ermol’ev and N.Z. Shor, “Method of random walk for the two-stage problem of stochastic programming and its generalization”, Kibernetika 1 (1968) 90–92 [in Russian]. Cybernetics 4 (1968) 59–60.
A.M. Gupal, Stochastic methods for solving nonsmooth extremal problems (Naukova Dumka, Kiev, 1979) [in Russian].
A.M. Gupal and L.T. Bazhenov, “A stochastic analog of the conjugate gradient method”, Kibernetika 1 (1972) 124–126 [in Russian]. Cybernetics 8 (1972) 138–140.
J.B. Hiriart-Urruty, “Conditions nécessaires d’optimalité pour un programme stochastique avec recours”, SIAM Journal on Control and Optimization 16 (1978) 317–319.
A.P. Korostelev, “On multi-step procedures of stochastic optimization”, Avtomatika i Telemekhanika 5 (1981) 82–90 [in Russian]. Automation and Remote Control 42 (1981) 621–628.
K. Kiwiel, “An aggregate subgradient method for nonsmooth convex minimization”, Mathematical Programming 27 (1983) 320–341.
H.J. Kushner and D.S. Clark, Stochastic approximation methods for constrained and unconstrained systems (Springer-Verlag, Berlin, New York, 1978).
H.J. Kushner and Hai-Huang, “Asymptotic properties of stochastic approximations with constant coefficients”, SIAM Journal on Control and Optimization 19 (1981) 87–105.
F. Mirzoakhmedov and S.P. Uryas’ev, “Adaptive stepsize regulation for a stochastic optimization algorithm”, Žurnal Vičislitelnoi Matematiki i Matematičeskoi Fiziki 23 (1983) 1314–1325 [in Russian].
M.B. Nevelson and B.Z. Khasminski, Stochastic approximation and recursive estimation (Nauka, Moscow, 1972) [in Russian].
E.A. Nurminski, Numerical methods for solving deterministic and stochastic minimax problems (Naukova Dumka, Kiev, 1979) [in Russian].
R.T. Rockafellar and R.J.B. Wets, “Stochastic convex programming: Relatively complete recourse and induced feasibility”, SIAM Journal on Control and Optimization 14 (1976) 574–589.
A. Ruszczyński and W. Syski, “Stochastic approximation method with gradient averaging for unconstrained problems”, IEEE Transactions on Automatic Control AC-28 (1983) 1097–1105.
A. Ruszczyński and W. Syski, “Stochastic approximation algorithm with gradient averaging and on-line stepsize rules”, contributed paper, Eighth World Congress of the IFAC, Budapest, 1984.
A. Ruszczyński and W. Syski, “On convergence of the stochastic subgradient method with on-line stepsize rules”, Technical Report R.I.21/84, Instytut Automatyki, Politechnika Warszawska, Warszawa, 1984, to appear in Journal on Mathematical Analysis and Applications.
S.P. Uryas’ev, “Step control for direct stochastic programming methods”, Kibernetika 6 (1980) 85–87 [in Russian]. Cybernetics 16 (1980) 886–890.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1986 The Mathematical Programming Society, Inc.
About this chapter
Cite this chapter
Ruszczyński, A., Syski, W. (1986). A method of aggregate stochastic subgradients with on-line stepsize rules for convex stochastic programming problems. In: Prékopa, A., Wets, R.J.B. (eds) Stochastic Programming 84 Part II. Mathematical Programming Studies, vol 28. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0121128
Download citation
DOI: https://doi.org/10.1007/BFb0121128
Received:
Revised:
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00926-6
Online ISBN: 978-3-642-00927-3
eBook Packages: Springer Book Archive