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

Authors

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

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

Download data is not yet available.

Author Biographies

Rafaela Filippozzi

Department of Mathematics, Federal University of Santa Catarina, Florianópolis, SC

Douglas S. Gonçalves

Department of Mathematics, Federal University of Santa Catarina, Florianópolis, SC

Luiz Rafael Santos

Department of Mathematics, Federal University of Santa Catarina, Blumenau, SC

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.

Downloads

Published

2022-12-08

Issue

Section

Resumos