Regularized Nonsmooth Newton Algorithms for Best Approximation

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 projection problem has many various and many 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 Halperin-Lions-Wittmann-Bauschke (HLWB).

We observe empirically that the regularized nonsmooth method significantly outperforms the HLWB method. However, the HLWB 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.

Our application to solving large-scale linear programs uses a parametrized projection problem. This leads to a 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 that improve the efficiency and robustness.

Regularized Nonsmooth Newton Algorithms for Best Approximation

Citation

Article