论文标题
正规化的非平滑牛顿算法以获得最佳近似
Regularized Nonsmooth Newton Algorithms for Best Approximation
论文作者
论文摘要
我们考虑从多面体集合找到最佳近似点及其应用，特别是解决大规模线性程序的问题。经典投影问题有许多不同的应用和许多应用。我们研究了雅各布奇异的非平滑牛顿型解决方案方法。我们将计算性能与Halperin-Lions-Wittmann-Bauschke（HLWB）的经典投影方法进行了比较。 我们从经验上观察到，正规化方法明显优于HLWB方法。但是，HLWB具有收敛保证，而非平滑方法不是单调的，并且不能部分原因是由于普遍的Jacobian的奇异性。 我们用于求解大规模线性程序的应用程序使用参数化投影问题。这导致\ emph {踏板石外路跟随}算法。其他应用程序是从分支和结合方法中找到三角形，以及广义的约束线性最小二乘。我们包括提高效率和鲁棒性的缩放方法。
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 \emph{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.
