Polyhedral Boundary Projection

Abstract

We consider the problem of projecting a point in a polyhedral set onto the boundary of the set using an arbitrary norm for the projection. Two types of polyhedral sets, one defined by a convex combination of k points in R^n and the second by the intersection of m closed halfspaces in R^n, lead to disparate optimization problems for finding such a projection. The first case leads to a mathematical program with a linear objective function and constraints that are linear inequalities except for a single nonconvex cylindrical constraint. Interestingly, for the 1-norm, this nonconvex problem can be solved by solving 2n linear programs. The second polyhedral set leads to a much simpler problem of determining the minimum of m easily evaluated numbers. These disparate mathematical complexities parallel known ones for the related problem of finding the largest ball, with radius measured by an arbitrary norm, that can be inscribed in the polyhedral set. For a polyhedral set of the first type this problem is NP-hard for the 2-norm and the infinity-norm [4] and solvable by a single linear program for the 1-norm [7], while for the second type this problem leads to a single linear program even for a general norm [6].