Regularized Nonsmooth Newton Algorithms for Best Approximation
         with Applications


abstract:
We consider the problem of finding the best approximation point from a
polyhedral set, and its applications, in particular to solving large-scale
linear programs.
The classical best approximation problem has many various solution techniques
as well as applications. We study a regularized nonsmooth Newton type
solution method where the Jacobian is singular; and we compare the computational
performance to that of the classical projection method of
Halpern-Lions-Wittmann-Bauschke (HLWB).

We observe empirically that the regularized nonsmooth method significantly
outperforms the HLWB method. However, the HLWB method has a convergence
guarantee while the nonsmooth method is not monotonic
and does not guarantee convergence due in part to singularity of
the generalized Jacobian. We include special cases where convergence is
guaranteed.

Our application to
solving large-scale linear programs uses a parametrized 
best approximation problem. This leads to a finitely converging 
stepping stone external path following algorithm. Other
applications are finding triangles from branch and
bound methods, and generalized constrained linear least squares.
We include scaling methods and sensitivity analysis
to improve the efficiency.