  In this paper we introduce and study a class of structured set-valued
operators which we call union averaged nonexpansive. At each point in their
domain, the value of such an operator can be expressed as a finite union of
single-valued averaged nonexpansive operators. We investigate various
structural properties of the class and show, in particular, that is closed
under taking unions, convex combinations, and compositions, and that their
fixed point iterations are locally convergent around strong fixed points. We
then systematically apply our results to analyze proximal algorithms in
situations where union averaged nonexpansive operators naturally arise. In
particular, we consider the problem of minimizing the sum two functions where
the first is convex and the second can be expressed as the minimum of finitely
many convex functions.
