Métodos para o problema de inclusão no envoltório convexo

Abstract

O problema de inclusão no envoltório convexo consiste em determinar se um ponto pode ser escrito como combinação convexa de um conjunto finito de pontos dados, isto é, se tal ponto pertence ao envoltório convexo dos dados pontos. Este é um problema de decisão com importantes aplicações em geometria computacional e em fundamentos de programação linear. Neste trabalho, propomos o uso de métodos de otimização de primeira ordem para resolver o problema. Mostramos que métodos do tipo Frank-Wolfe e gradiente projetado, quando equipados com novos critérios de parada, são eficazes para tal problema de decisão, e apresentam desempenho favorável em relação a um algoritmo recente específico ao problema, chamado Algoritmo do Triângulo. Discutimos as conexões entre este algoritmo e Frank-Wolfe, mostrando que o primeiro pode ser interpretado como um Frank-Wolfe inexato. Apesar dessa semelhança, o Algoritmo do Triângulo é fortemente baseado em um teorema de alternativas conhecido como dualidade de distâncias. Usando tal teorema, desenvolvemos novos critérios de parada para métodos do tipo Frank-Wolfe e gradiente projetado, especializando-os para o problema de inclusão. Reportamos experimentos numéricos executados em exemplares artificiais, cuidadosamente gerados para cobrir diferentes cenários, que indicam qual algoritmo é preferível de acordo com a geometria do envoltório convexo e a posição relativa do ponto a ser consultado. No que diz respeito a aplicações potenciais, apresentamos dois exemplos ilustrativos, um relacionado a problemas de viabilidade de programação linear e outro relacionado a problemas de classificação de imagem. Além disso, também consideramos uma reformulação do problema na qual o ponto a ser consultado é a origem e os pontos do conjunto dado têm norma um. Investigamos uma propriedade que, quando satisfeita a cada iteração, permite melhorar a complexidade de iteração do Algoritmo do Triângulo. Introduzimos uma heurística que busca favorecer a ocorrência de tal propriedade e resultados numéricos preliminares atestam sua efetividade.

Abstract: The convex hull membership problem consists in deciding whether a point can be written as a convex combination of a finite set of given points, that is, whether such a point belongs to the convex hull of the given points. This is a decision problem with important applications in computational geometry and in foundations of linear programming. In this work we propose the use of first-order optimization methods to solve this problem. We show that, Frank-Wolfe type methods and Projected Gradient methods, when equipped with new stopping criteria, are effective for such a decision problem and perform favorably against a recent problem-specific algorithm called Triangle Algorithm. We discuss the connections between this algorithm and Frank-Wolfe, showing that the former can be interpreted as an inexact Frank-Wolfe. Despite this similarity, the Triangle Algorithm is strongly based on a theorem of alternatives known as distance duality. By using this theorem, we devise new stopping criteria integrated for Frank-Wolfe type and Projected Gradient methods, specializing them to the membership decision problem. We report numerical experiments on artificial instances, 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. Furthermore, we also consider a reformulation of the problem in which the query point is the origin and the points of the given set have norm one. We investigated a property that, when satisfied at each iteration, allows us to improve the iteration complexity of the Triangle Algorithm. We introduce a heuristic that seeks to favor the occurrence of such a property and preliminary numerical results corroborates its effectiveness.