ON SOME PROBLEMS WITH MULTIVALUED MAPPINGS

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

Рассматриваются некоторые задачи о многозначных отображениях, которые могут быть сведены к минимизации положительно однородной липшицевой функции на единичной сфере. Последняя задача может быть в некоторых случаях решена алгоритмом первого порядка – методом проекции градиента. Вкачестве одного из примеров рассмотрен случай, когда многозначное отображение есть множество достижимости автономной линейной управляемой системы. Для ряда постановок доказана линейная сходимость метода проекции градиента в рассматриваемой ситуации. Мы используем схему доказательства сходимости градиентного метода, предложенную Б.Т. Поляком, в случае выполнения неравенства Лежанского– Поляка–Лоясевича. Вотличие от други х способов решения, например при помощи аппроксимации множества достижимости, приведенные алгоритмы гораздо слабее зависят от размерности фазового пространства и других параметров задачи. Также возможна эффективная оценка ошибок. Численные эксперименты подтверждают эффективность рассматриваемого подхода. Помимо множества достижимости, рассмотренные алгоритмы могут быть применены к различным теоретико-множественным задачам с многозначными отображениями достаточно общего вида.

About the authors

M. V Balashov

Институт проблем управления им. В.А. Трапезникова РАН

Email: balashov73@mail.ru
д-р физ.-мат. наук Москва

K. Z Biglov

Институт проблем управления им. В.А. Трапезникова РАН

Email: biglov.kz@phystech.edu
Москва

A. A Tremba

Институт проблем управления им. В.А. Трапезникова РАН; Московский физико-технический институт

Email: atremba@ipu.ru
канд. физ.-мат. наук Москва; Долгопрудный

References

  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

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 The Russian Academy of Sciences