First-order methods for the convex-hull membership problem and applications

Rafaela Filippozzi, Douglas S. Gonçalves, Luiz Rafael Santos

Resumo


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]. [...]


Texto completo:

PDF (English)

Referências


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.


Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato