Эвристические подходы к построению эллипсоида минимального объема вокруг подмножества точек

Обложка

Цитировать

Полный текст

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

Аннотация

В работе рассматривается следующая существенно комбинаторная задача: даны N точек в пространстве ℝn, построить эллипсоид минимального объема, содержащий ровно N – k точек, где k много меньше N. Предлагаются шесть алгоритмов приближенного решения этой задачи, основанные на тех или иных эвристических соображениях. Приводятся численные результаты сравнительной эффективности алгоритмов при различных предположениях о механизме генерирования точек и их количестве.

Об авторах

Павел Сергеевич Щербаков

Институт проблем управления им. В. А. Трапезникова Российской академии наук; Московский Физико-технический институт; Федеральный исследовательский центр «Информатика и управление» Российской академии наук

Автор, ответственный за переписку.
Email: cavour118@mail.ru

главный научный сотрудник, доктор физико-математических наук; ведущий научный сотрудник; ведущий научный сотрудник

Россия, Москва; Долгопрудный; Москва

Яна Игоревна Квинто

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

Email: yanakvinto@mail.ru

старший научный сотрудник, кандидат технических наук

Россия, Москва

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

  1. Becker S., Bobin J., Candes E. NESTA: A fast and accurate first-order method for sparse recovery. SIAM J. on Imaging Sciences. 2009;4(1):1–39.
  2. Burke E.K., Kendall G. (eds.) Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. New York: Springer Science+Business Media, 2014.
  3. Donoho D.L. For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics. 2006;56(6):797–829.
  4. Ruan D., Chen G., Kerre E.E., Wets G. (eds.) Intelligent Data Mining: Techniques and Applications. Studies in Computational Intelligence. Vol. 5. New York: Springer, 2005.
  5. Ahipaşaoğlu S.D. Fast algorithms for the minimum volume estimator. Journal of Global Optimization. 2015;62(2):351–370.
  6. Boyd S., El Ghaoui L., Feron E., Balakrishnan V. Linear Matrix Inequalities in System and Control Theory. Philadelphia: SIAM, 1994.
  7. Boyd S., Vandenberge L. Convex Optimization. Cambridge, MA: Cambridge University Press, 2004.
  8. Grant M., Boyd S. CVX: Matlab software for disciplined convex programming, ver. 2.2. Available from: http://stan- ford.edu/~boyd/cvx, 2020.
  9. Ahipaşaoğlu S.D., Sun P., Todd M.J. Linear convergence of a modified frank-wolfe algorithm for computing minimum-volume enclosing ellipsoids. Optimization Methods and Software. 2008;23:5–19.
  10. Sun P., Freund R.M. Computation of minimum-volume covering ellipsoids. Operations Research. 2004;52(5):690–706.
  11. Agullo J. Exact iterative computation of the multivariate minimum volume ellipsoid estimator with a branch and bound algorithm. In: Pratt A. (ed.) Proceedings in Computational Statistics. Heidelberg; Physica-Verlag, 1996. p. 175–180.
  12. Bai E.-W., Chi H., Tempo R., Ye Y. Optimization with few violated constraints for linear bounded error parameter estimation. IEEE Trans. Autom. Control. 2002;47(7):1067–1077.
  13. Dabbene F., Shcherbakov P. Minimum volume ellipsoid comprising a subset of points. In: Proceedings of the 6th Int. Conf. Control, Decision Inform. Technologies (CoDiT 2019), Paris, Apr 23–26, 2019, paper WiP 20
  14. Gärtner B.. Sampling with removal in LP-type problems. Journal of Computational Geometry. 2015;6(2):93–112.
  15. Tempo R., Calafiore G., Dabbene F. Randomized Algorithms for Analysis and Control of Uncertain Systems: With Applications. 2nd ed. Springer, 2013.
  16. Van Aelst S., Rousseeuw P. Minimum volume ellipsoid. WIREs Computational Statistics. 2009;1:71–82.
  17. Campi M.C., Garatti S. A sampling-and-discarding approach to chance-constrained optimization: Feasibility and optimality. Journal of Optimization Theory and Applications.2011;148:257–280.
  18. Dabbene F., Henrion D., Lagoa C., Shcherbakov P. Randomized approximations of the image set of nonlinear discrete-time systems with applications to filtering. In: Proceedings of the 8th IFAC Symposium on Robust Control Design (ROCOND 2015), Bratislava, Slovak Republic, Jul 8–11, 2015.
  19. Raynaud H. Sur l’enveloppe convexe des nuages de points aleatoires dans IRn. I. Journal of Applied Probability. 1970;7(1):35–48.
  20. Hueter I. Limit theorems for the convex hull of random points in higher dimensions. Trans. Amer. Math. Soc. 1999;351(11):4337–4363.
  21. Jolliffe I.T. Principal Component Analysis. Springer Series in Statistics. New York: Springer, 2002.
  22. Pearson K. On lines and planes of closest fit to systems of points in space. Philosophical Magazine. 1901;2:559–572.
  23. Lee J. Relationships between Properties of Pulp-Fibre and Paper. PhD Diss, University of Toronto, 1992.

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

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


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

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») на элемент с текстом «Принять и продолжить».