Global convergence and acceleration of fixed point iterations of union upper semicontinuous operators: proximal algorithms, alternating and averaged nonconvex projections, and linear complementarity problems

We propose a unified framework to analyze fixed point iterations of a set-valued operator that is the union of a finite number of upper semicontinuous maps, each with a nonempty closed domain and compact values. We discuss global convergence, local linear convergence under a calmness condition, and component identification, and further propose acceleration strategies that drastically improve the convergence speed. Our framework is applied to analyze a class of proximal algorithms for minimizing the sum of a piecewise smooth function and the difference between pointwise minimum of finitely many weakly convex functions and a piecewise smooth convex function. When realized on two-set feasibility problems, this algorithm class recovers alternating projections and averaged projections as special cases, and our framework thus equips these classical methods with global convergence and possibilities for acceleration on a broad class of nonconvex feasibility problems. By specializing the framework to a nonconvex feasibility problem reformulation of the linear complementarity problem, we show global convergence to a solution from any initial point, with a local linear rate, of the alternating projection as well as the averaged projection methods, which is difficult to obtain on nonconvex problems. Numerical results further exemplify that the proposed acceleration algorithms significantly improve upon their non-accelerated counterparts in efficiency.

Article

Download

View Global convergence and acceleration of fixed point iterations of union upper semicontinuous operators: proximal algorithms, alternating and averaged nonconvex projections, and linear complementarity problems