Алгоритмические модели поведения человека и стохастическая оптимизация
DOI:
https://doi.org/10.26577/jmmcs-2017-3-473Ключевые слова:
стохастический зеркальный спуск, безградиентные методы, поиск равновесия в транспортных сетяхАннотация
В статье исследуется параллелизация вычислений при решении задач стохастической опти-
мизации; рассматривается приложение полученных здесь результатов к поиску равновесного
распределения потоков по путям; исследуется зависимость скорости сходимости оптималь-
ных алгоритмов в задачах стохастической безградиентной оптимизации, в зависимости от
числа обращений к оракулу за реализацией функции на каждой итерации. Отличительная
особенность данной статьи – демонстрация полученных результатов наглядными примерами.
Библиографические ссылки
[1] Agarwal A., Dekel O. and Xiao L., "Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit
Feedback."Proceedings of 23 Annual Conference on Learning Theory (2010): 528.
[2] Andersen S.P., de Palma A. and Thisse J.F., Discrete Choice Theory of Product Differentiation. (Cambridge: MIT Press,
1992), 423.
[3] Beckmann M., McGuire C.B. and Winsten C. Studies in the Economics of Transportation. (Santa Monica: RAND
Corporation, 1955), 323.
[4] Bubeck S. and Cesa-Bianchi N., "Regret Analysis of Stochastic and Nonstochastic Multi-Armed Bandit
Problems"Foundation and Trends in Machine Learning 5(2012): 122.
[5] Bubeck S. and Eldan R., "Multi-Scale Exploration of Convex Functions and Bandit Convex Optimization"e-print, 2015,
http://research.microsoft.com/en-us/um/people/sebubeck/ConvexBandits.pdf
[6] Duchi J.C., Jordan M.I., Wainwright M.J. and Wibisono A., "Optimal Rates for Zero-Order Convex Optimization: the
Power of Two Function Evaluations"IEEE Transaction of Information 61(2015): 2952.
[7] Gasnikov A.V., Gasnikova Ye.V., Matsiyevskiy S.V. and Usik I.V., "O Svyazi Modeley Diskretnogo Vybora s
Raznomasshtabnymi po Vremeni Populyatsionnymi Igrami Zagruzok"Trudy MFTI. 7(2015): 204.
[8] Gasnikov A.V., Krymova Ye.A., Lagunovskaya A.A., Usmanova I.N. and Fedorenko F.A., "Stokhasticheskaya Onlain
Optimizatsiya. Odnotochechnyye i Dvukhtochechnyye Nelineynyye Mnogorukiye Bandity. Vypuklyy i Sil’no Vypuklyy
Sluchai."Avtomatika i Telemekhanika 2(2017): 144.
[9] Gasnikov A.V., Lagunovskaya A.A. and Morozova L.E., "O Svyazi Imitatsionnoy Logit Dinamiki v Populyatsionnoy Teorii
Igr i Metoda Zerkal’nogo Spuska v Onlayn Optimizatsii na Primere Zadachi Vybora Kratchayshego Marshruta."Trudy
MFTI 7(2015): 204.
[10] Gasnikov A.V., Lagunovskaya A.A., Usmanova I.N. and Fedorenko F.A., "Bezgradiyentnyye Proks-Metody s Netochnym
Orakulom Dlya Negladkikh Zadach Vypukloy Stokhasticheskoy Optimizatsii na Simplekse"Avtomatika i telemekhanika
10(2016): 166.
[11] Gasnikova Ye.V., "Modelirovaniye Dinamiki Makrosistem na Osnove Kontseptsii Ravnovesiya"(Associate prof. diss.,
MFTI, 2012).
[12] Hazan E., "Introduction to Online Convex Optimization."Foundations and Trends in Optimization 2(2016): 325.
[13] Hazan E. and Kale S., "Beyond the Regret Minimization Barrier: Optimal Algorithms for Stochastic Strongly-Convex
Optimization."JMLR 15(2014): 2512.
[14] Juditsky A., Lan G., Nemirovski A. and Shapiro A., "Stochastic Approximation Approach to Stochastic
Programming."SIAM Journal on Optimization 19 (2009): 2014.
[15] Juditsky A. and Nemirovski A., "First Order Methods for Nonsmooth Convex Large-Scale Optimization, I,
II."Optimization for Machine Learning (2012): 63.
[16] Ledoux M., Concentration of Measure Phenomenon (Amer Mathematical Society, 2001), 192.
[17] Lugosi G. and Cesa-Bianchi N., Prediction, Learning and Games. (New York: Cambridge University Press, 2006), 403.
[18] Nemirovski A., "Lectures on Modern Convex Optimization Analysis, Algorithms,
and Engineering Applications."Philadelphia: SIAM, 2016, accessed August 12, 2017,
http://www2.isye.gatech.edu/nemirovs/LectModConvOpt.pdf.
[19] Nemirovski А.С. and Judin D.B., Lozhnost’ Zadach i Effektivnost’ Metodov Optimizatsii (Moscow: Nauka, 1979), 384.
[20] Nesterov Yu., "Primal-Dual Subgradient Methods for Convex Problems."Math. Program. Ser. B. 120(2009): 287.
[21] Nesterov Y. and Vial J.-Ph., "Confidence Level Solution for Stochastic Programming."Automatica 44(2008): 1652.
[22] Polyak B.T., Vvedeniye v Optimizatsiyu (Moscow: Nauka, 1983), 384.
[23] Sandholm W., Population Games and Evolutionary Dynamics. Economic Learning and Social Evolution. (Cambridge:
MIT Press, 2010), 616.
[24] Sheffi Y., Urban Transportation Networks: Equilibrium Analysis With Mathematical Programming Methods. (N.J.:
Prentice-Hall Inc, 1985), 416.
[25] Razzhevaykin V.N., Analiz Modeley Dinamiki Populyatsiy. Uchebnoye posobiye. (Moscow: MFTI, 2010), 174.
Feedback."Proceedings of 23 Annual Conference on Learning Theory (2010): 528.
[2] Andersen S.P., de Palma A. and Thisse J.F., Discrete Choice Theory of Product Differentiation. (Cambridge: MIT Press,
1992), 423.
[3] Beckmann M., McGuire C.B. and Winsten C. Studies in the Economics of Transportation. (Santa Monica: RAND
Corporation, 1955), 323.
[4] Bubeck S. and Cesa-Bianchi N., "Regret Analysis of Stochastic and Nonstochastic Multi-Armed Bandit
Problems"Foundation and Trends in Machine Learning 5(2012): 122.
[5] Bubeck S. and Eldan R., "Multi-Scale Exploration of Convex Functions and Bandit Convex Optimization"e-print, 2015,
http://research.microsoft.com/en-us/um/people/sebubeck/ConvexBandits.pdf
[6] Duchi J.C., Jordan M.I., Wainwright M.J. and Wibisono A., "Optimal Rates for Zero-Order Convex Optimization: the
Power of Two Function Evaluations"IEEE Transaction of Information 61(2015): 2952.
[7] Gasnikov A.V., Gasnikova Ye.V., Matsiyevskiy S.V. and Usik I.V., "O Svyazi Modeley Diskretnogo Vybora s
Raznomasshtabnymi po Vremeni Populyatsionnymi Igrami Zagruzok"Trudy MFTI. 7(2015): 204.
[8] Gasnikov A.V., Krymova Ye.A., Lagunovskaya A.A., Usmanova I.N. and Fedorenko F.A., "Stokhasticheskaya Onlain
Optimizatsiya. Odnotochechnyye i Dvukhtochechnyye Nelineynyye Mnogorukiye Bandity. Vypuklyy i Sil’no Vypuklyy
Sluchai."Avtomatika i Telemekhanika 2(2017): 144.
[9] Gasnikov A.V., Lagunovskaya A.A. and Morozova L.E., "O Svyazi Imitatsionnoy Logit Dinamiki v Populyatsionnoy Teorii
Igr i Metoda Zerkal’nogo Spuska v Onlayn Optimizatsii na Primere Zadachi Vybora Kratchayshego Marshruta."Trudy
MFTI 7(2015): 204.
[10] Gasnikov A.V., Lagunovskaya A.A., Usmanova I.N. and Fedorenko F.A., "Bezgradiyentnyye Proks-Metody s Netochnym
Orakulom Dlya Negladkikh Zadach Vypukloy Stokhasticheskoy Optimizatsii na Simplekse"Avtomatika i telemekhanika
10(2016): 166.
[11] Gasnikova Ye.V., "Modelirovaniye Dinamiki Makrosistem na Osnove Kontseptsii Ravnovesiya"(Associate prof. diss.,
MFTI, 2012).
[12] Hazan E., "Introduction to Online Convex Optimization."Foundations and Trends in Optimization 2(2016): 325.
[13] Hazan E. and Kale S., "Beyond the Regret Minimization Barrier: Optimal Algorithms for Stochastic Strongly-Convex
Optimization."JMLR 15(2014): 2512.
[14] Juditsky A., Lan G., Nemirovski A. and Shapiro A., "Stochastic Approximation Approach to Stochastic
Programming."SIAM Journal on Optimization 19 (2009): 2014.
[15] Juditsky A. and Nemirovski A., "First Order Methods for Nonsmooth Convex Large-Scale Optimization, I,
II."Optimization for Machine Learning (2012): 63.
[16] Ledoux M., Concentration of Measure Phenomenon (Amer Mathematical Society, 2001), 192.
[17] Lugosi G. and Cesa-Bianchi N., Prediction, Learning and Games. (New York: Cambridge University Press, 2006), 403.
[18] Nemirovski A., "Lectures on Modern Convex Optimization Analysis, Algorithms,
and Engineering Applications."Philadelphia: SIAM, 2016, accessed August 12, 2017,
http://www2.isye.gatech.edu/nemirovs/LectModConvOpt.pdf.
[19] Nemirovski А.С. and Judin D.B., Lozhnost’ Zadach i Effektivnost’ Metodov Optimizatsii (Moscow: Nauka, 1979), 384.
[20] Nesterov Yu., "Primal-Dual Subgradient Methods for Convex Problems."Math. Program. Ser. B. 120(2009): 287.
[21] Nesterov Y. and Vial J.-Ph., "Confidence Level Solution for Stochastic Programming."Automatica 44(2008): 1652.
[22] Polyak B.T., Vvedeniye v Optimizatsiyu (Moscow: Nauka, 1983), 384.
[23] Sandholm W., Population Games and Evolutionary Dynamics. Economic Learning and Social Evolution. (Cambridge:
MIT Press, 2010), 616.
[24] Sheffi Y., Urban Transportation Networks: Equilibrium Analysis With Mathematical Programming Methods. (N.J.:
Prentice-Hall Inc, 1985), 416.
[25] Razzhevaykin V.N., Analiz Modeley Dinamiki Populyatsiy. Uchebnoye posobiye. (Moscow: MFTI, 2010), 174.
Загрузки
Как цитировать
Bektemessov, M. A., Gasnikov, A. V., Lagunskaya А А. А., & Ordabayeva, Z. M. (2018). Алгоритмические модели поведения человека и стохастическая оптимизация. Вестник КазНУ. Серия математика, механика, информатика, 95(3), 50–68. https://doi.org/10.26577/jmmcs-2017-3-473
Выпуск
Раздел
Прикладная математика
