First-order methods for the convex hull membership problem

作     者：Filippozzi, Rafaela Goncalves, Douglas S. Santos, Luiz-Rafael 

作者机构：Univ Fed Santa Catarina Dept Math BR-88040900 Florianopolis SC Brazil Univ Fed Santa Catarina Dept Math BR-89065300 Blumenau SC Brazil 

出 版 物：《EUROPEAN JOURNAL OF OPERATIONAL RESEARCH》 (欧洲运筹学杂志)

年 卷 期：2023年第306卷第1期

页      面：17-33页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Brazilian agency CAPES (Coordenacao para Aperfeicoamento Pessoal do Ensino Superior) CAPES Brazilian agency CNPq (Conselho Nacional de Desenvolvimento Cientifico e Tecnologico) [305213/2021-0] CNPq [113190/2022-0] 

主　　题：Convex programming Convex hull membership problem Triangle algorithm Frank-Wolfe algorithms 

摘      要：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 theo-rem, 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 in-tegrated 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 ran-dom 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. Con-cerning potential applications, we present two illustrative examples, one related to linear programming feasibility problems and another related to image classification problems.(c) 2022 Elsevier B.V. All rights reserved.