|
Аннотация.
В работе рассматривается следующая существенно комбинаторная задача: даны N точек в пространстве R^n, построить эллипсоид минимального объема, содержащий ровно N – k точек, где k много меньше N. Предлагаются шесть алгоритмов приближенного решения этой задачи, основанные на тех или иных эвристических соображениях. Приводятся численные результаты сравнительной эффективности алгоритмов при различных предположениях о механизме генерирования точек и их количестве.
Ключевые слова:
точечное множество, отбраковка, выпуклая оптимизация, эллипсоид минимального объема, эвристика.
DOI 10.14357/20718632240411
EDN JCIBCK
Стр. 112-122.
Литература
1. Becker S., Bobin J., Candes E. NESTA: A fast and accuratefirst-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://stanford.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.
|
