%A O. L. Mangasarian %T Polyhedral Boundary Projection %D October 1997 %R 97-10 %I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN %C MADISON, WI %X 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. The second polyhedral set leads to a much simpler problem of determining the minimum of $m$ easily evaluated numbers. Similarly disparate mathematical programs ensue from the problem of finding the largest ball relative to the affine hull of a polyhedral set, 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 leads to a maxmin of a bilinear function over linear inequality constraints and a single nonconvex cylindrical constraint, while for the second type this problem leads to a single linear program. Interestingly, for the one norm, the nonconvex mathematical program associated with the boundary projection problem for the first polyhedral set can be solved by solving $2n$ linear programs.