- Код статьи
- 10.31857/S0005231024050024-1
- DOI
- 10.31857/S0005231024050024
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 5
- Страницы
- 58-85
- Аннотация
- Рассматриваются некоторые задачи о многозначных отображениях, которые могут быть сведены к минимизации положительно однородной липшицевой функции на единичной сфере. Последняя задача может быть в некоторых случаях решена алгоритмом первого порядка – методом проекции градиента. Вкачестве одного из примеров рассмотрен случай, когда многозначное отображение есть множество достижимости автономной линейной управляемой системы. Для ряда постановок доказана линейная сходимость метода проекции градиента в рассматриваемой ситуации. Мы используем схему доказательства сходимости градиентного метода, предложенную Б.Т. Поляком, в случае выполнения неравенства Лежанского– Поляка–Лоясевича. Вотличие от други х способов решения, например при помощи аппроксимации множества достижимости, приведенные алгоритмы гораздо слабее зависят от размерности фазового пространства и других параметров задачи. Также возможна эффективная оценка ошибок. Численные эксперименты подтверждают эффективность рассматриваемого подхода. Помимо множества достижимости, рассмотренные алгоритмы могут быть применены к различным теоретико-множественным задачам с многозначными отображениями достаточно общего вида.
- Ключевые слова
- метод проекции градиента многозначный интеграл сильная выпуклость опорное множество условие Липшица негладкий анализ
- Дата публикации
- 15.05.2024
- Год выхода
- 2024
- Всего подписок
- 0
- Всего просмотров
- 10
Библиография
- 1. Ioffe A.D. Metric regularity - a survey Part I and II // J. Aust. Math. Soc. 2016. V. 101. P. 188-243; P. 376-417.
- 2. Luke D.R. Finding best approximation pairs relative to a convex and prox-regular set in a Hilbert space // SIAM J. Optim. 2008. V. 19. No. 2. P. 714-739.
- 3. Grunewalder S. Compact convex projections //J. Mach. Learn. Res. 2018. V. 18. No. 2019. P. 1-43.
- 4. Sosa W., Raupp F.M.P An algorithm for projecting a point onto a level set of a quadratic function // Optimization. 2022. V. 71. No. 1. P. 71-89.
- 5. Bregman L.M., Censor Y., Reich S., Zepkowitz-Malachi Y. Finding the projection of a point onto the intersection of convex sets via pro jections onto half-spaces // J. Approx. Theory. 2003. V. 124. No. 2. P. 194-218.
- 6. Aumann R. Integrals of set-valued functions //J. Math. Anal. Appl. 1965. V. 12. No. 1. P. 1-12.
- 7. Ляпунов А.А. О вполне аддитивных вектор-функциях // Изв. АН СССР. Сер. матем. 1940. Т. 4. № 6. С. 465-478.
- 8. Frankowska H, Olech C. R-convexity of the integral of the set-valued functions. Contributions to analysis and geometry (Baltimore, Md., 1980) / Johns Hopkins Univ. Press, Baltimore, Md., 1981. P. 117-129.
- 9. Vial J.-Ph. Strong and Weak Convexity of Sets and Functions // Math. Oper. Res. 1983. V. 8. No. 2. P. 231-259.
- 10. Balashov M. V., Repovs D. Uniformly convex subsets of the Hilbert space with modulus of convexity of the second order //J. Math. Anal. Appl. 2011. V. 377. No. 2. P. 754-761.
- 11. Veliov V.M. On the convexity of integrals of multivalued mappings: application in control theory //J. Optim. Theor. Appl. 1987. V. 54. No. 3. P. 541-563.
- 12. Veliov V.M. Second order discrete approximations to strongly convex differential inclusions // Syst. Control Lett. 1989. V. 13. No. 3. P. 263-269.
- 13. Althoff M, Frehse G, Girard A. Set propagation techniques for reachability analysis // Annu. Rev. Control Robot. Auton. Syst. 2021. V. 4. P. 369-395.
- 14. Le Guernic C., Girard A. Reachability analysis of linear systems using support functions // Nonlinear Anal. Hybrid Syst. 2010. V. 4. P. 250-262.
- 15. Gruber P.M. Approximation of convex bodies / Convexity and Its Applications. Basel Birkhauser, 1983. P. 131-162.
- 16. Serry M., Reissig G. Over-approximating reachable tubes of linear time-varying systems // IEEE Trans. Automat. Control. V. 67. No. 1. P. 443-450.
- 17. Kurzhanski A.B., Varaiya P. Dynamics and control of trajectory tubes, theory and computation // Ser. Systems and Control: Foundations and Applications. Birkhauser/Springer, 2014.
- 18. Левитин Е.С., Поляк Б.Т. Методы минимизации при наличии ограничений // Журн. вычисл. матем. и матем. физ. 1966. Т. 6. № 5. С. 1-50.
- 19. Балашов М.В., Половинкин Е.С. M-сильно выпуклые множества и их порождающие подмножества // Матем. сб. 2000. Т. 191. № 1. C. 25-60.
- 20. Cannarsa P., Frankowska H. Interior sphere property of attainable sets and time optimal control problems // ESAIM Control Optim. Calc. Var. 2006. V. 12. No. 2. P. 350-370.
- 21. Balashov M.V., Polyak B.T., Tremba A.A. Gradient projection and conditional gradient methods for constrained nonconvex minimization // Numer. Funct. Anal. Optim. 2020. V. 41. No. 7. P. 822-849.
- 22. Балашов М.В. Сильная выпуклость множеств достижимости линейных систем // Матем. сб. 2022. Т. 213. № 5. C. 30-49.
- 23. Болтянский В.Г. Математические методы оптимального управления. Наука, 1969.
- 24. Тремба А.А. Вычисление множества достижимости линейных стационарных систем с помощью опорной функции и опорных элементов // Материалы XVI Международной научной конференции Устойчивость и колебания нелинейных систем управления (конференция Пятницкого). ИПУ РАН, Москва, 2022. С. 437-441.
- 25. Половинкин Е.С. Сильно выпуклый анализ // Матем. сб. 1996. Т. 187. № 2. C. 259-286.
- 26. Bolte J., Sabach Sh., Teboulle M. Proximal alternating linearized minimization for nonconvex and nonsmooth problems // Math. Program. 2014. V. 146. P. 459-494.
- 27. Balashov M.V., Tremba A.A. Error bound conditions and convergence of optimization methods on smooth and proximally smooth manifolds // Optimization. 2022. V. 71. No. 3. P. 711-735.
- 28. Ivanov G.E., Goncharov V. V. Strong and weak convexity of closed sets in a Hilbert space / Operations Research, Engineering, and Cyber Security. Springer Optimization and Its Applications. Springer, 2017. Vol. 113. P. 259-297.
- 29. Балашов М.В., Камалов Р.А. Метод проекции градиента с шагом Армихо на многообразиях // Журн. вычисл. матем. и матем. физ. 2021. Т. 61. № 11. С. 1776-1786.
- 30. Tremba A. Computing reachability set with support function and support points: Python code repository. https://github.com/atremba/lti-reachability-set
