Blog

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. This is a joint
work with Ching-pei Lee.