First-order methods for the convex-hull membership problem and applications
Abstract
Let A := {v1 , v2 , . . . , vn } be a finite subset of Rm and consider a given point p ∈ Rm . The convex hull membership problem (CHMP) consists in deciding whether p ∈ conv(A), where conv(A) denotes the convex hull of A. This problem is related to fundamental concepts in linear programming and nds important applications in computational geometry [3, 4]. [...]
Downloads
References
P. Awasthi, B. Kalantari, and Y. Zhang. _Robust vertex enumeration for convex hulls in high dimensions_. In: International Conference on Arti_cial Intelligence and Statistics. PMLR. 2018, pp. 1387_1396.
A. Blum, S. Har-Peled, and B. Raichel. _Sparse approximation via generating point sets_. In: ACM Transactions on Algorithms 15.3 (2019), pp. 1_16.
E. J. Goodman and J. O'Rourke. Handbook of discrete and computational geometry. CRC, 1997.
B Kalantari. _A Characterization Theorem and an Algorithm for a Convex Hull Problem_. In: Annals of Operations Research 226.1 (2014), pp. 301_349.
P. Kumar and E. A. Yildirim. _Minimum-Volume Enclosing Ellipsoids and Core Sets_. In: Journal of Optimization Theory and Applications 126.1 (2005), pp. 1_21.
S. Lacoste-Julien and M. Jaggi. _On the global linear convergence of Frank-Wolfe optimization variants_. In: Proceedings of the 28th International Conference on Neural Informa- tion Processing Systems. Vol. 1. 2015, pp. 496_504.
