Regularized Nonsmooth Newton Algorithms for Best Approximation
From MaRDI portal
Applications of functional analysis in optimization, convex analysis, mathematical programming, economics (46N10) Nonsmooth analysis (49J52) Iterative numerical methods for linear systems (65F10) Numerical optimization and variational techniques (65K10) Linear programming (90C05) Optimality conditions and duality in mathematical programming (90C46) Approximation methods and heuristics in mathematical programming (90C59)
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 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.
This page was built for publication: Regularized Nonsmooth Newton Algorithms for Best Approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6421751)
