Seminário de Otimização & Problemas Inversos
Título: First-order methods for the convex hull membership problem
Palestrante: Rafaela Filippozzi (UFSC)
Resumo: The convex hull membership problem (CHMP) consists in deciding whether a certain point belongs to the convex hull of a fnite 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 frst-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 develop suitable stopping criteria for CHMP to be integrated into Frank-Wolfe type and Projected Gradient methods, allowing a fair numerical comparison between those and the Triangle Algorithm. Interestingly, FrankWolfe integrated with such stopping criterion is nothing but a greedy Triangle Algorithm which is equivalent to an old algorithm due to von Neumann. Our numerical experiments on random instances of CHMP, across diﬀerent scenarios, indicate that an Away-Step version of Frank-Wolfe achieves the best performance in comparison to other frst-order methods mentioned above.
Data: Segunda-feira, 4 de abril, 14h
Local: Sala MTM202, no Departamento de Matemática
Maiores informações: http://mtm.ufsc.br/~maicon/seminar