- Код статьи
- 10.31857/S0005231024060059-1
- DOI
- 10.31857/S0005231024060059
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 6
- Страницы
- 67-82
- Аннотация
- Статья посвящена задаче оптимизации. Пусть A,B ⊂ Rn - выпуклые компакты. Рассмотрим минимальное число t0 > 0 такое, что t0B накрывает A после сдвига на вектор x0 ∈ Rn. Цель - найти t0 и x0. В частном случае, когда B является единичным шаром с центром в нуле, x0 и t0 известны как чебышевский центр и чебышевский радиус A. В данной статье рассматривается случай, когда A и B определяются с помощью своих опорных функций. Предложен алгоритм в духе гардиентного спуска Б.Т. Поляка для эффективного решения таких задач. Алгоритм имеет сверхлинейную скорость сходимости и может решать стомерные тестовые задачи за разумное время, однако для гарантии наличия сходимости необходимы некоторые дополнительные условия на A и B. Дополнительно исследовано поведение алгоритма для простого частного случая, что приводит к ряду теоретических результатов. Изучаются также возмущения этого частного случая.
- Ключевые слова
- оптимизация чебышевский центр градиентный спуск
- Дата публикации
- 15.06.2024
- Год выхода
- 2024
- Всего подписок
- 0
- Всего просмотров
- 10
Библиография
- 1. Балашов М.В. Покрытие множества выпуклым компактом: оценки погрешности и вычисление // Матем. заметки. 2022. Т. 112. № 13. С. 337–349.
- 2. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
- 3. R. Tyrrell Rockafellar. Convex Analysis. Princeton University Press, 1997.
- 4. Botkin N., Turova V. An algorithm for finding the Chebyshev center of a convex polyhedron // Appl. Mat. Optim. 1995. V. 29. P. 211–222.
- 5. Xia Y., Yang M. Chebyshev center of the intersection of balls: complexity, relaxation and approximation // Mathematical Programming. 2021. V. 187. P. 287–315.
- 6. Frankowska H., Olech C. R-convexity of the integral of set-valued functions // Contribut. Anal. Geometry. 1980. V. 117–129.
- 7. Vial J.-Ph. Strong and Weak Convexity of Sets and Functions // Mathematics of Operations Research. 1983. V. 8. No. 2. P. 231–259.
- 8. Boyd S., Vandenberghe L. Convex optimization. Cambridge University Press, 2004.
- 9. Li X., Zhu Z., Man-Cho S., Lee J.D. Incremental Methods for Weakly Convex Optimization // arXiv, 2019. V. 1907.11687v1.
- 10. Davis D., Drusvyatskiy D., MacPhee K.J., Paquette C. Subgradient Methods for Sharp Weakly Convex Functions // arXiv, 2018. V. 1803.02461v1.
- 11. Schneider R., Uschmajew A. Convergence results for projected line search methods on varieties of low-rank matricies via Lojasiewicz inequality // SIAM J. Optim. 2015. V. 25. No. 1. P. 622–646.
- 12. Balashov M.V. About the Gradient Projection Algorithm for a Strongly Convex Function and a Proximally Smooth Set // J. Convex Anal. 2017. V. 24. No. 2. P. 493–500.
- 13. Bello-Cruz Y., Li G., Nghia T.T.A. On the Linear Convergence of ForwardBackward Splitting Method: Part I – Convergence Analysis // J. Optim. Theory Appl. 2021. V. 188. P. 378–401.
- 14. Ioffe A.D. Metric regularity – a survey Part I // J. Austral. Math. Soc. 2016. V. 101. P. 1–56.
- 15. Absil P.-A., Mahony R., Sepulchre R. Optimization Algorithms onMatrix Manifolds. Princeton University Press, 2008.
- 16. Cen X., Xia Y., Gao R., Yang T. On Chebyshev Center of the Intersection of Two Ellipsoids // Optimization of Complex Systems: Theory, Models, Algorithms and Applications. Springer International Publishing, 2020. P. 135–144.
- 17. Beltran F., Finardi E.C., Fredo G.M., Oliveira W. Improving the performance of the stochastic dual dynamic programming algorithm using Chebyshev centers // Optim. Engineer. 2022. V. 23. P. 147–168.
- 18. Beck A., Eldar Y.C. Regularization in Regression with Bounded Noise: A Chebyshev Center Approach // SIAM J. Matrix Anal. Appl. 2007. V. 29. No. 2. P. 606–625.
- 19. Cerone V., Piga D., Regruto D. Set-Membership Error-in-Variables Identification Through Convex Relaxation Techniques // IEEE Transact. Autom. Control. 2012. V. 57. No. 2. P. 517–522.
- 20. Hou J., Teng F., Yin W., Song Y., Hou Y. A Cost-Effective Cyber-Defense Strategy: Attack-Induced Region Minimization and Cybersecurity Margin Maximization // arXiv. 2023. V. 2302.07597.
- 21. Samadi S., Roux J., Tanguy A., Caron S., Kheddar A. Some journal publication in English // IEEE Robot. Autom. Lett. 2021. V. 6. No. 2. P. 4032–4039.
- 22. Ren X., Mo Y., Chen J., Johansson K.H. Secure state estimation with byzantine sensors: A probabilistic approach // IEEE Transact. Autom. Control. 2020. V. 65. No. 9. P. 3742–3757.
