Successive Projection for Solving Systems of Nonlinear Equations/Inequalities
share
Solving large-scale systems of nonlinear equations/inequalities is a fundamental problem in computing and optimization. In this paper, we propose a generic successive projection (SP) framework for this problem. The SP sequentially projects the current iterate onto the constraint set corresponding to each nonlinear (in)equality. It extends von Neumann's alternating projection for finding a point in the intersection of two linear subspaces, Bregman's method for finding a common point of convex sets and the Kaczmarz method for solving systems of linear equations to the more general case of multiple nonlinear and nonconvex sets. The existing convergence analyses on randomized Kaczmarz are merely applicable to linear case. There are no theoretical convergence results of the SP for solving nonlinear equations. This paper presents the first proof that the SP locally converges to a solution of nonlinear equations/inequalities at a linear rate. Our work establishes the convergence theory of the SP for the case of multiple nonlinear and nonconvex sets. Besides cyclic and randomized projections, we devise two new greedy projection approaches that significantly accelerate the convergence. Furthermore, the theoretical bounds of the convergence rates are derived. We reveal that the convergence rates are related to the Hoffman constants of the Jacobian matrix of the nonlinear functions at the solution. Applying the SP to solve the graph realization problem, which attracts much attention in theoretical computer science, is discussed.
READ FULL TEXT