%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.