First-order methods for the convex hull membership problem

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

European Journal of Operational Research, 2023, vol. 306, issue 1, 17-33

Abstract: The convex hull membership problem (CHMP) consists in deciding whether a certain point belongs to the convex hull of a finite set of points, a decision problem with important applications in computational geometry and in foundations of linear programming. In this study, we review, compare and analyze first-order methods for CHMP, namely, Frank-Wolfe type methods, Projected Gradient methods and a recently introduced geometric algorithm, called Triangle Algorithm (TA). We discuss the connections between this algorithm and Frank-Wolfe, showing that TA can be interpreted as an inexact Frank-Wolfe. Despite this similarity, TA is strongly based on a theorem of alternatives known as distance duality. By using this theorem, we propose suitable stopping criteria for CHMP to be integrated into Frank-Wolfe type and Projected Gradient, specializing these methods to the membership decision problem. Interestingly, Frank-Wolfe integrated with such stopping criteria coincides with a greedy version of the Triangle Algorithm which is, in its turn, equivalent to an algorithm due to von Neumann. We report numerical experiments on random instances of CHMP, carefully designed to cover different scenarios, that indicate which algorithm is preferable according to the geometry of the convex hull and the relative position of the query point. Concerning potential applications, we present two illustrative examples, one related to linear programming feasibility problems and another related to image classification problems.

Keywords: Convex programming; Convex hull membership problem; Triangle algorithm; Frank-Wolfe algorithms (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172200683X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:306:y:2023:i:1:p:17-33

DOI: 10.1016/j.ejor.2022.08.040

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().