An O(1/ε)-Iteration Triangle Algorithm for A Convex Hull Membership
share
A fundamental problem in linear programming, machine learning, and computational geometry is the Convex Hull Membership (CHM): Given a point p and a subset S of n points in R^m, is p ∈ conv(S)? The Triangle Algorithm (TA) computes p' ∈ conv(S) so that, either p'- p ≤ε R, R= { p -v : v∈ S}; or p' is a witness, i.e. the orthogonal bisector of pp' separates p from conv(S). By the Spherical-CHM we mean a CHM, where p=0, v =1, ∀ v ∈ S. First, we prove the equivalence of exact and approximate versions of CHM and Spherical-CHM. On the one hand, this makes it possible to state a simple O(1/ε^2) iteration TA, each taking O(n+m) time. On the other hand, using this iteration complexity we prove if for each p' ∈ conv(S) with p > ε that is not a witness there is v ∈ S with p' - v ≥√(1+ ε), the iteration complexity of TA reduces to O(1/ε). This matches complexity of Nesterov's fast-gradient method. The analysis also suggests a strategy for when the property does not hold at an iterate. Lastly, as an application of TA, we show how to solve strict LP feasibility as a dual of CHM. In summary, TA and the Spherical-CHM provide a convenient geometric setting for efficient solution to large-scale CHM and related problems, such as computing all vertices of conv(S).
READ FULL TEXT