Projection on the intersection of convex sets

Abstract

In this paper, we give a solution of the problem of projecting a point onto the intersection of several closed convex sets, when a projection on each individual convex set is known. The existing solution methods for this problem are sequential in nature. Here, we propose a highly parallelizable method. The key idea in our approach is the reformulation of the original problem as a system of semi-smooth equations. The benefits of the proposed reformulation are twofold: (a) a fast semi-smooth Newton iterative technique based on Clarke's generalized gradients becomes applicable and (b) the mechanics of the iterative technique is such that an almost decentralized solution method emerges. We proved that the corresponding semi-smooth Newton algorithm converges near the optimal point (quadratically). These features make the overall method attractive for distributed computing platforms, e.g. sensor networks.