Email this article 
An Algorithm for Finding the Generalized Chebyshev Center of Sets Defined via Their Support Functions
- Authors: Arkhipov P.A1
-
Affiliations:
- Issue: No 6 (2024)
- Pages: 67-82
- Section: Topical issue
- URL: https://journal-vniispk.ru/0005-2310/article/view/261623
- DOI: https://doi.org/10.31857/S0005231024060059
- EDN: https://elibrary.ru/XXDBSM
- ID: 261623
Cite item
Open Access
Access granted
Subscription Access
Abstract
Статья посвящена задаче оптимизации. Пусть A,B ⊂ Rn - выпуклые компакты. Рассмотрим минимальное число t0 > 0 такое, что t0B накрывает A после сдвига на вектор x0 ∈ Rn. Цель - найти t0 и x0. В частном случае, когда B является единичным шаром с центром в нуле, x0 и t0 известны как чебышевский центр и чебышевский радиус A. В данной статье рассматривается случай, когда A и B определяются с помощью своих опорных функций. Предложен алгоритм в духе гардиентного спуска Б.Т. Поляка для эффективного решения таких задач. Алгоритм имеет сверхлинейную скорость сходимости и может решать стомерные тестовые задачи за разумное время, однако для гарантии наличия сходимости необходимы некоторые дополнительные условия на A и B. Дополнительно исследовано поведение алгоритма для простого частного случая, что приводит к ряду теоретических результатов. Изучаются также возмущения этого частного случая.
Keywords
References
- Балашов М.В. Покрытие множества выпуклым компактом: оценки погрешности и вычисление // Матем. заметки. 2022. Т. 112. № 13. С. 337–349.
- Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
- R. Tyrrell Rockafellar. Convex Analysis. Princeton University Press, 1997.
- Botkin N., Turova V. An algorithm for finding the Chebyshev center of a convex polyhedron // Appl. Mat. Optim. 1995. V. 29. P. 211–222.
- Xia Y., Yang M. Chebyshev center of the intersection of balls: complexity, relaxation and approximation // Mathematical Programming. 2021. V. 187. P. 287–315.
- Frankowska H., Olech C. R-convexity of the integral of set-valued functions // Contribut. Anal. Geometry. 1980. V. 117–129.
- Vial J.-Ph. Strong and Weak Convexity of Sets and Functions // Mathematics of Operations Research. 1983. V. 8. No. 2. P. 231–259.
- Boyd S., Vandenberghe L. Convex optimization. Cambridge University Press, 2004.
- Li X., Zhu Z., Man-Cho S., Lee J.D. Incremental Methods for Weakly Convex Optimization // arXiv, 2019. V. 1907.11687v1.
- Davis D., Drusvyatskiy D., MacPhee K.J., Paquette C. Subgradient Methods for Sharp Weakly Convex Functions // arXiv, 2018. V. 1803.02461v1.
- 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.
- 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.
- 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.
- Ioffe A.D. Metric regularity – a survey Part I // J. Austral. Math. Soc. 2016. V. 101. P. 1–56.
- Absil P.-A., Mahony R., Sepulchre R. Optimization Algorithms onMatrix Manifolds. Princeton University Press, 2008.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
Supplementary files
