Polyhedral boundary projection

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 o f polyhedral sets, one defined by a convex combination of k points in R-n a nd the second by the intersection of m closed half-spaces in R-n, lead to d isparate optimization problems for finding such a projection. The first cas e leads to a mathematical program with a linear objective function and cons traints that are linear inequalities except for a single nonconvex cylindri cal constraint. Interestingly, for the 1-norm, this nonconvex problem can b e solved by solving 2n linear programs. The second polyhedral set leads to a much simpler problem of determining the minimum of m easily evaluated num bers. These disparate mathematical complexities parallel known ones for the related problem of finding the largest ball, with radius measured by an ar bitrary 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 infin ity-norm [R. M. Freund and J. B. Orlin, Math. Programming, 33 (1985), pp. 1 39-145] and solvable by a single linear program for the 1-norm [P. Gritzman n and V. Klee, Math. Programming, 59 (1993), pp. 163-213], while for the se cond type this problem leads to a single linear program even for a general norm [P. Gritzmann and V. Klee, Discrete Comput. Geom., 7 (1992), pp. 255-2 80].