A gradient method for unconstrained optimization in noisy environment. (English) Zbl 1283.65059
Summary: A gradient method for solving unconstrained minimization problems in noisy environment is proposed and analyzed. The method combines the line search technique with the stochastic approximation (SA) method. A line search along the negative gradient direction is applied while the iterates are far away from the solution and upon reaching some neighborhood of the solution the method switches to the SA rule. The main issue is to determine the switching point and that is resolved both theoretically and practically. The main result is the almost sure convergence of the proposed method due to a finite number of line search steps followed by infinitely many SA consecutive steps. The numerical results obtained on a set of standard test problems confirm theoretical expectations and demonstrate the efficiency of the method.
Keywords:
stochastic optimization; stochastic approximation; noisy function; gradient method; line search method; almost sure convergence; numerical resultsReferences:
| [1] | Andradóttir, S., A scaled stochastic approximation algorithm, Management Sci., 42, 4, 475-498 (1996) · Zbl 0885.93058 |
| [2] | Chen, H.-F., Stochastic Approximation and Its Application (2002), Kluwer Academic Publishers: Kluwer Academic Publishers New York · Zbl 1008.62071 |
| [3] | Delyon, B.; Juditsky, A., Accelerated stochastic approximation, SIAM J. Optim., 3, 4, 868-881 (1993) · Zbl 0801.62071 |
| [4] | Fang, H. T.; Chen, H. F., Almost surely convergent global optimization algorithm using noise-corrupted observations, J. Optim. Theory Appl., 104, 2, 343-376 (2000) · Zbl 0966.90061 |
| [5] | Kao, Ch.; Chen, Sh.-P., A stochastic quasi-Newton method for simulation response optimization, European J. Oper. Res., 173, 1, 30-46 (2006) · Zbl 1125.90394 |
| [6] | Kesten, H., Accelerated stochastic approximation, Ann. Math. Stat., 29, 1, 41-59 (1958) · Zbl 0087.13404 |
| [7] | Kiefer, J.; Wolfowitz, J., Stochastic estimation of the maximum of a regression function, Ann. Math. Stat., 23, 3, 462-466 (1952) · Zbl 0049.36601 |
| [8] | Kushner, H., Stochastic approximation: a survey, Wiley Interdisciplin. Rev.: Comput. Stat., 2, 1, 87-96 (2010) |
| [9] | Kushner, H. J.; Gavin, T., Extensions of Kestenʼs adaptive stochastic approximation method, Ann. Stat., 1, 5, 851-861 (1973) · Zbl 0285.62054 |
| [11] | Lucidi, S.; Sciandrone, M., A derivative-free algorithm for bound constrained optimization, Comput. Optim. Appl., 21, 2, 119-142 (2002) · Zbl 0988.90033 |
| [12] | Monnez, J.-M., Almost sure convergence of stochastic gradient processes with matrix step sizes, Statist. Probab. Lett., 76, 5, 531-536 (2006) · Zbl 1087.62092 |
| [13] | Moré, J. J.; Garbow, B. S.; Hillstrom, K. E., Testing unconstrained optimization software, ACM Trans. Math. Software, 7, 1, 17-41 (1981) · Zbl 0454.65049 |
| [14] | Nocedal, J.; Wright, S. J., Numerical Optimization (1999), Springer-Verlag: Springer-Verlag New York · Zbl 0930.65067 |
| [15] | Raydan, M., The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim., 7, 1, 26-33 (1997) · Zbl 0898.90119 |
| [16] | Robbins, H.; Monro, S., A stochastic approximation method, Ann. Math. Stat., 22, 3, 400-407 (1951) · Zbl 0054.05901 |
| [17] | Ruppert, D., A Newton-Raphson version of the multivariate Robbins-Monro procedure, Ann. Stat., 13, 1, 236-245 (1985) · Zbl 0571.62072 |
| [18] | Sirlantzis, K.; Lamb, J. D.; Liu, W. B., Novel algorithms for noisy minimization problems with applications to neural networks training, J. Optim. Theory Appl., 129, 2, 325-340 (2006) · Zbl 1139.90020 |
| [19] | Spall, J. C., Adaptive stochastic approximation by the simultaneous perturbation method, IEEE Trans. Automat. Contr., 45, 10, 1839-1853 (2000) · Zbl 0990.93125 |
| [20] | Spall, J. C., Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control (2003), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. Hoboken, NJ · Zbl 1088.90002 |
| [21] | Spall, J. C., Feedback and weighting mechanism for improving Jacobian estimates in the adaptive simultaneous perturbation algorithm, IEEE Trans. Automat. Contr., 54, 6, 1216-1229 (2009) · Zbl 1367.93734 |
| [22] | Wardi, Y., Stochastic algorithms with Armijo stepsizes for minimization of functions, J. Optim. Theory Appl., 64, 2, 399-417 (1990) · Zbl 0687.90086 |
| [23] | Wei, C. Z., Multivariate adaptive stochastic approximation, Ann. Stat., 15, 3, 1115-1130 (1987) · Zbl 0676.62064 |
| [24] | Xu, Zi; Dai, Yu-Hong, New stochastic approximation algorithms with adaptive step size, Optim. Lett., 6, 8, 1831-1846 (2012) · Zbl 1261.90057 |
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.
