О НЕКОТОРЫХ ЗАДАЧАХ С МНОГОЗНАЧНЫМИ ОТОБРАЖЕНИЯМИ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

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

Об авторах

М. В БАЛАШОВ

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

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

К. З БИГЛОВ

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

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

А. А ТРЕМБА

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

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

Список литературы

  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

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2024

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».