Рандомизированные алгоритмы стохастической аппроксимации при неопределенностях с бесконечным вторым моментом
Диссертация
Работы написаны в соавторстве. Соискателю принадлежат формулировки и доказательства основных теорем, имитационное моделирование. В работах O.H. Грани-чину принадлежат общие постановки задач, в С. С. Сысоеву — формулировка алгоритма для квантовых вычисленийв Л. С. Гуревичу — формулировки условий на нестационарность и теорема об оптимальном выборе размера шага, в М.А. Пань-шенскову — анализ… Читать ещё >
Содержание
- 1. Рандомизированные алгоритмы стохастической аппроксимации
- 1. 1. Оптимизация дифференцируемых функций
- 1. 2. Оптимизация функционала среднего риска
- 1. 3. Методы на основе аппроксимации градиента
- 1. 4. Рандомизированные алгоритмы стохастической аппроксимации
- 1. 5. Модели со случайными величинами с бесконечной дисперсией и задачи оптимизации
- 1. 5. 1. Модель высокооптимизированной толерантности
- 1. 5. 2. Модель присоединения с предпочтением
- 2. 1. Условия состоятельности и стабилизации оценок
- 2. 2. Примеры задач.'
- 2. 3. Состоятельность оценок в стационарном случае
- 2. 4. Скорость сходимости
- 2. 5. Стабилизация оценок в нестационарном случае
- 2. 6. Доказательства теорем
- 3. 1. Задача з-агрузки узлов распределенной сети
- 3. 2. Управление с обратной связью
- 3. 3. Имитационное моделирование
- 3. 4. Доказательства теорем 7,
Список литературы
- Вазап М. Стохастическая аппроксимация. М: Мир. 1972. 295 с.
- Baxumoe А. Т. Методы балансировки загрузки для многопроцессорных систем // Стохастическая оптимизация в информатике. 2006. Вып. 2. С. 159−166.
- Baxumoe А. Т. Адаптивное слияние результатов поиска изображений по содержанию // Стохастическая оптимизация в информатике. 2007. Вып. 3. С. 97−107.
- Baxumoe А. Т. Балансировка Grid-вычислений методами стохастической оптимизации // Труды II школы-семинара молодых ученых «Управление большими системами». Воронеж, 2007. С. 115−120.i
- Baxumoe А. Т. Оптимизация балансировки загрузки процессоров при паралелльном выполнении цикла // Материалы шестого научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах». С.-Петербург. 2007. С. 88−90.
- Baxumoe А. Т. Адаптивное оценивание параметров в параллельных многопользовательских вычислительных системах // Стохастическая оптимизация в.информатике. 2008. Вып. 4. С. 139−150.
- Baxumoe А. Т. Нестационарная стохастическая оптимизация рандомизированными алгоритмами в случае бесконечной дисперсии неопределенностей // Стохастическая оптимизация в информатике. 2009. Вып. 5. С. 24−39.
- Вахитов А.Т., Вяххи Н. И., Петров А. Г. Грид-вычислсния в задаче Ant colony optimization: базовая архитектура приложения и адаптивное распределение заданий // Тр. конф. «Технологии Microsoft в теории и практике программирования». 2009. С. 62−65.
- Вахитов А. Т., Граничил О. Н. Рандомизированные алгоритмы оценивания при нерегулярных помехах // Стохастическая оптимизация в информатике. 2006. Вып. 2. С. 3−37.
- Вахитов А. Т., Граничина О. А. Алгоритмы классификации за минимальное число шагов // Стохастическая оптимизация в информатике. 2006. Вып. 2. С. 167−175.
- Вахитов А. Т., Граиичин О. Н., Гуревич Л. С. Алгоритм стохастической аппроксимации с пробным возмущением на входе в нестационарной задаче оптимизации // Автоматика и телемеханика. 2009. № 11. С. 70−79.
- Вахитов А.Т., Граиичин О. Н., Панъшенсков М. А. Методы оценивания пропускной способности в распределенных системах // Нейрокомпьютеры: разработка, применение. N2 11. 2009. С. 45−53.
- Вахитов А. Т., Граничии О. П., Сысоев С. С. Точность оценивания рандомизированного алгоритма стохастической оптимизации // Автоматика и телемеханика. № 4. 2006. С. 86−96.
- Вахитов А. Т., Гуревич Л. С. Псевдоградиентный метод с возмущением на входе для нестационарной задачи безусловной оптимизации // Стохастическая оптимизация в информатике. 2008. Вып. 4. С. 36−47.
- Вахитов А. Т., Гуревич Л. С., Павленко Д. В. Обзор алгоритмов сте-реозрения // Стохастическая оптимизация в информатике. 2008. Вып. 4. С. 151−169.
- Baxumoo A. TКраснощекое В. E. Оптимизация выполнения заданий в GRID на основе адаптации // Материалы шестого научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах». С.-Петербург. 2007. С. 79−88.
- Граничин О. Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения // Вестник Ленингр. ун-та. Сер. 1. 1989. № 1(4). С. 19−21.
- Граничин О.Н. Оптимальная скорость сходимости рандомизированных алгоритмов стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. 2003. № 2. С. 88−99.
- Граничин О.Н. Оценивание точки минимума неизвестной функции, наблюдаемой на фоне зависимых помех // Проблемы передачи информации. 1992. № 2. С. 16−20.
- Граничин О.Н. Рандомизированные алгоритмы стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. 2003. № 2. С. 44−55.
- Граничин О. Н.- Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. — М.: Наука. 2003. 291 с.
- Ермаков С.М., Жиглявский А. А. Математическая теория оптимального эксперимента. — М.: Наука. 1987. 320 с.
- Ермаков С. М., Жиглявский А. А. О случайном поиске глобального экстремума // Теория вероятностей и ее применения. 1983. Т. 28, № 1. С. 129−134.
- Ермольев Ю.М. О методе обобщенных стохастических градиентов и стохастических квазифейеровских последовательностях // Кибернетика. 1969. № 2. С. 73−83.
- Ермольев Ю.М. Методы стохастического программирования. — М.: Наука. 1976. 239 с.
- Жиглявский А.А., Жилиискас А. Г. Методы поиска глобального экстремума. — М.: Наука. 1991. 248 с.
- Зорин В.А. Математический анализ. Часть II. М: МЦНМО. 2002. 794 С.
- Карлип С. Математические методы в теории игр, программировании и экономике,— М.: Мир. 1964. 836 с.
- Карманов В.Г. Математическое программирование. — М.:ФИЗМАТЛИТ. 2004. 264 с.
- Катковник В. Я. Метод операторов усреднения в итерационных алгоритмах решения стохастических экстремальных задач // Кибернетика. 1972. № 4. С. 123−131.
- Катковник В.Я. Параметрические операторы усреднения в итерационных алгоритмах решения стохастических экстремальных задач. I. Операторы усреднения и статистические оценки // Автоматика и телемеханика. 1974. № 3. С. 67−75.
- Катковник В.Я. Параметрические операторы усреднения в итерационных алгоритмах решения стохастических экстремальных задач. II. Итеративные алгоритмы оптимизации // Автоматика и телемеханика. 1974. № 4. С. 613−620.
- Красулииа Т.П. О процессах стохастической аппроксимации с бесконечной дисперсией // Теория вероятностей и ее применения. 1969. Т. 14. № 3. С. 546−551.
- Красулина Т.П. Об односторонней сходимости модифицированного процесса Роббинса-Монро при малых шагах // Вестник С.-ПетербургСкого Университета. Сер. 1. № 4. С. 67−72.
- Красулина Т.П., Гапошкин Д. Ф. О законе повторного логарифма в процессе стохастической аппроксимации // Теория вероятностей и ее применения. 1974. Т. 19. № 4. С. 879−886.
- Коростелев А.П. Стохастические рекуррентные процедуры: локальные свойства. — М.: Наука. 1984. 208 с.
- Михалевич B.C., Гупал A.M., Норкин В. И. Методы невыпуклой оптимизации. — М.: Наука. 1987. 279 с.
- Невелъсон Ы.В., Хасьминский Р. З. Стохастическая аппроксимация и рекуррентное оценивание. — М.: Наука. 1972. 304 с.
- Нестеров Ю.Е. Метод решения задачи выпуклого программирования со скоростью сходимости О(р) // Докл. АН СССР. 1983. Т. 269, № 3. С. 543−547.
- Поляк Б.Т. Введение в оптимизацию. — М.:Наука. 1983. 384 с.
- Поляк Б. Т. Сходимость и скорость сходимости итеративных стохастических алгоритмов. I. Общий случай // Автоматика и телемеханика. 1976. № 12. С. 83−94.
- Поляк Б. Т., Цыбаков А. Б. Оптимальные порядки точности поисковых алгоритмов стохастической аппроксимации // Проблемы передачи информации. 1990. № 26. С. 126−133.
- Поляк Б.Т., Цыпкин Я. З. Псевдоградиентные алгоритмы адаптации и обучения // Автоматика и телемеханика. № 3. 1973. С. 45−68.
- Поляк Б. Т., Щербаков П. С. Робастная устойчивость и управление.1. М.: Наука. 2002. 303 с.
- Растригин Л.А. Статистические методы поиска. — М.: Наука. 1968. 369 с.
- Сухарев AT. Минимаксные алгоритмы в задачах численного анализа. M.:URSS. 2009. 304 с.
- Сысоев С. С. Рандомизированные алгоритмы стохастической оптимизации, квантовые компьютеры, искусственный интеллект // Стохастическая оптимизация в информатике. 2005. Вып. 1. С. 206 221.
- Фельдбаум А. А. О проблемах дуального управления //В кн.: Методы оптимизации автоматических систем. М.:Наука. 1972. с. 89 108.
- Фомин В.Н. Рекуррентное оценивание и адаптивная фильтрация— М.: Наука. 1984. 288 с. I
- Фомин В.П., Фрадков А. Л., Якубович В. А. Адаптивное управление динамическими объектами. — М.: Наука. 1981. 448 с.
- Харди Г. Г., Литлвуд Д. Е., Полиа Г. Неравенства. — М.:КомКнига, 2006. 456 с.
- Юдин Д.Б. Математические методы управления в условиях неполной информации. — М.: Советское радио, 1974. 400 с.
- Anderson D.P., Cobb J., Korpela E., Lebofsky M., Werthimer D. SETIhome: an experiment in public-resource computing // Communications of the ACM. 2002. Vol. 45. No. 11. P. 56−61.
- Astrom К. J., Wittenmark В. Adaptive control (2nd cd.) — Reading, MA: Addison-Wesley. 1995. 574 p.
- Auguin M., Jalby W., Maillard J. Use of SIMD-SPMD machine for simulation in particle physics // Proc. Conf. on Computing in high energy physics. 1986. P. 355 362.
- Babiker S., Asenov A., Barker J. R., Beaumont S. P. Finite element Monte Carlo simulation of recess gate compound FFTs // Solid-State Electronics. 1996. Vol. 39. No 5. P. 629−635.
- Barabasi A.-LAlbert R. Emergence of Scaling in Random Networks // Science. 1999. Vol. 286. P. 509−512.
- Benveniste A., Metiever M.} Priouret P. Adaptive algorithms and stochastic approximations. — Berlin-Heidelberg-New York: Springer-Verlag. 1990. 365 p.
- Berger N., Borgs p., Chayes J., and Saberi A. On the spread of viruses in the Internet// Proc. SODA, 2005. P. 301−310.
- Blum J.R. Multidimensional Stochastic Approximation // Ann. Math. Statist. 1954. Vol. 9. P. 417−425.
- Bonomi F., Kumar A. Adaptive Optimal Load Balancing in a Nonhomogeneous Multiserver System with a Central Job Scheduler //' IEEE Transactions on Computers. 1990. Vol. 30. No. 10. P. 1239−1250.
- Borkar V.S. Stochastic approximation: a dynamical systems viewpoint — New York: Cambridge University Press. 2008. 164 P.
- Bidlo F., Cortez J., Martinez S. Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms. USA: Princeton University Press. 2009. 336 p.
- Calafiore D., Campi M. Uncertain convex programs: randomized solutions and confidence levels // Mathematical Programming. 2005. Vol. 102. No. 1. P. 25−46.
- Chen H.-F., Duncan Т. E., Pasik-Duncan B. A Kiefer-Wolfowitz algorithm with randomized differences. // IEEE Trans. Automat. Contr. 1999. Vol. 44. No. 3. P. 442−453.
- Carlson J, Doyle J. Highly optimized tolerance: A mechanism for power laws in designed systems // Physical Review. 1999. Vol. 60, No. 2. P. 1412−1427.
- Carlson J.M., Doyle J. Complexity and robustness // Proc. Natl. Acad. Sci. U. S. A. 2002. Vol. 99 (Suppl. 1). P. 2538−2545.
- Dobson I., Carreras A., Lynch VNewman D. Complex systems analysis of series of blackouts: Cascading failure, critical points, and self-organization // CHAOS. 2007. Vol. 17, No. 2. P. 13.
- Drapper P. S., Li Y. T. Principles of optimalizing control systems and an application to the internal combustion engine // ASME Publication. 1951. P. 160−168.
- Dupac V. A dynamic stochastic approximation method // Ann. Math. Statist. 1965. Vol. 36, No. 6. P. 1695−1702.
- Durlauf S. N. Complexity and Empirical Economics // Economic Journal. 2005. Vol. 115. No 504. P. 225−243.
- Fabian V. Stochastic Appoximation // Optimizing Methods in Statistics. 1971. P. 439−470.
- Flaxman A. D., Kalai A. T, McMahan H. B. Online convex optimization in the bandit setting gradient //' In Proc. SODA, 2005. P. 385−394.
- Ferber J. Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence. Harlow: Addison Wesley Longman. 1999. 509 p.
- Flynn M. Some Computer Organizations and Their Effectiveness // IEEE Trans. Comput. 1972. Vol. C-21. P. 948.
- Foster I. The Anatomy of the Grid: Enabling Scalable Virtual Organizations // Euro-Par 2001 Parallel Processing. 2001. P. 1−4.
- Gabaix X., Gopikrishnan P., Plerou V., Stanley H.E. A theory of power-law distributions in financial market fluctuations // Nature.2003. Vol. 423. P. 267−270.
- Granichin 0. Linear regression and filtering under nonstandard assumptions (Arbitrary noise) // IEEE Trans, on Automatic Control.2004. Vol. 49. P. 1830−1835.
- Granichin O., Gurevich L., and Vakhitov A. SPSA with a fixed gain for intelligent control in tracking applications //In Proc. of 2009 IEEE Int. Symp. on Intelligent Control. P. 1415−1420.
- Granichin O.N., Vakhitov A.T. Architecture for artificial intelligence hybrid computing // Proc. of the 3rd Int. IEEE Scientific Conf. on Physics and Control. Potsdam, Germany. 2007. P. 181.
- Granichin 0. N., Vakhitov A. T. SPSA-Based Adaptive control: accuracy of estimates // Proc. 9-th IFAC Workshop «Adaptation and Learning in Control and Signal Processing» (ALCOSP). 2007. P. 51.
- Granichin O. N., Vakhitov A. T. Accuracy for the SPSA algorithm with two measurements // WSEAS Transactions on Systems. 2006. Vol. 5. No. 5. P. 953−957.
- Guo L., Ljung L. Performance analysis of general tracking algorithms // IEEE Trans. Automat. Contr. 1995. Vol. 40. No 8. P. 1388−1402.
- Gurevich L. S., Vakhitov A. T. SPSA algorithm for tracking //In Proc. of 12th Int. Student Olympiad on Automatic Control (Baltic Olympiad). P. 52−57.
- Harchol-Balter M., Downey A.B. Exploiting Process Lifetime Distributions for Dynamic Load Balancing. Report No. UCB/CSD-95−887 University of California Berkeley. 1995. 19 p.
- Jenkins S., Kirk S.R. Software architecture graphs as complex networks: A novel partitioning scheme to measure stability and evolution // Information Sciences. 2007. Vol. 177. No. 12. P. 25 872 601.
- Kiefer J., Wolfowitz J. Stochastic estimation of the maximum of a regression function, // Annals of Mathematical Statistics. Vol. 23. No. 3. 1952. P. 462−466.
- Killingback TDoebeli M. Self-organized criticality in Spatial Evolutionary Game Theory // Journal of Theoretical Biology. 1998. Vol. 191. No. 3. P. 335−340.
- Krasnotcshekov V., Vakhitov A. Adaptive Scheduling and resource asessment in GRID //In Proc. of 9th Int. Conf. Parallel Computing Technologies. P. 240−244.
- Krivulin N.K. Unbiased estimates for gradients of stochastic network performance measures // Acta Appl. Math. 1993. Vol. 33. P. 21−43.
- Krstic M., Wang H.H. Stability of extremum seeking feedback for general nonlinear dynamic systems // Automatica. 2000. Vol. 200. P. 595−601.
- Kushner H. J., Yin G. Stochastic approximation and recursive algorithms and applications. — Springer. 2003. 474 p.
- Lange K. Optimization. — Springer. 2004. 252 p.
- Maeda Y., Kanata Y. Learning rules for rcccurent neural networks using perturbation and their application to ncurocontrol / / Transactions of IEE of Japan. 1993. Vol. 113. P. 402−408.
- Matveev A., Savkin A. Estimation and Control Over Communication Networks. Springer, 2008. — 533 p.
- Mitzenmacher M. A Brief History of Generative Models for Power Law and Lognormal Distributions // Internet Mathematics. 2004. Vol. 1. No. 2. P. .226−251.
- Poznyak A. S., Tehickin D. O. Gradient procedures for stochastic approximation with dependent noise and their asymptotic behaviour // International Journal of Systems Science. 1985. Vol. 16. No. 8. P. 917 949.
- Robbins E., Monro S. A Stochastic Approximation Method // Annals of Mathematical Statistics. 1951. Vol. 22. No. 3. P. 400−407.
- Sadegh P., Spall J.C. Optimal Random Perturbations for Stochastic Approximation using a Simultaneous Perturbation Gradient Approximation / / IEEE Transactions on Automatic Control. 1998. Vol. 43. No. 10. P. 1480−1484.
- Schroeder В., Harchol-Balter M. Evaluation of Task Assignment Policies for Supercomputing Servers: The Case for Load Unbalancing and Fairness //In Proc. 9th IEEE Symposium on High Performance Distributed Computing (HPDC '00). 2000. P. 211−219.
- Simon H. A. On a Class of Skew Distribution Functions // Biometrika. 1955. Vol. 42. No. ¾. P. 425−440.
- Spall J. C. Multivariate Stochastic Aproximation Using a Simultaneous Perturbation Gradient Aproximation // IEEE Trans. Automat. Contr. 1992. Vol. 37. No. 3. P. 332−341.
- Spall J. C. A Stochastic aproximation technique for generating maximum likelihood parameter estimates, //' In Proc. of the American Control Conference. 1987. P. 1161−1167.
- Spall J.C. Developments in stochastic optimization algorithms with gradient aproximations based on function measurements // In Proceedings of the Winter Simulation Conference. 1994. P. 207−214.
- Spall J.C. A one-measurement form of simultaneous perturbation stochastic approximation // Automatica. Vol. 33. No. 1. 1997. P. 109 112.
- Spall J. C. Introduction to Stochastic Search and Optimization. — New York: Wiley. 2003. 620 p.
- Spall J.C., Cristion J.A. Model-Free Control of Nonlinear Stochastic Systems with Discrete-Time Measurements // IEEE Transactions on Automatic Control. 1998. Vol. 43. P. 1198−1210.
- Sternby J. Adaptive control of extremum systems // Methods and Aplications in Adaptive Control. 2006. P. 151−160.
- Vidyasagar M. Statistical learning theory and randomized algorithms for control // IEEE Control Systems. 1998. No. 12. P. 69−85.
- Vijay Srinivas A., Janakiram D., Venkateswar Reddy M. Avalanche Dynamics in Grids: Indications of SOC or HOT? // Frontiers in Artificial Intelligence and Applications. 2005. Vol. 135. P. 183−193.
- Weiss G. Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence. Cambridge: MIT Press. 1999. 619 p.
- Yi Y., Song H., Zheng R., Xiao L. Scale-Free Property in Large Scale Object-Oriented Software and Its Significance on Software Engineering //In Proc. Second International Conference on Information and Computing Science. 2009. Vol. 3. P. 401−404.
- Yule G. A Mathematical Theory of Evolution Based on the Conclusions of Dr. J.C. .Willis // F.R.S. Philosophical Transactions of the Royal Society of London (Series B). 1925. No. 213. P. 21−87.