A randomized distributed ellipsoid algorithm for uncertain feasibility problems

In this paper, we consider a network of processors aiming at cooperatively solving a convex feasibility problem in which the constraint set is the intersection of local uncertain sets, each one known only by one processor. We propose a randomized, distributed method-using concepts borrowed from a centralized ellipsoid algorithm-having finite-time convergence and working under asynchronous, time-varying and directed communication topologies. At every communication round, each processor maintains a 'candidate' ellipsoid for the global problem and performs two tasks. First, it verifies-in a probabilistic sense-if the center of the candidate ellipsoid is robustly feasible for its local set and, if not, constructs a new ellipsoid with smaller volume. Second, it exchanges its ellipsoid with neighbors, and then selects the one with smallest volume among the collected ones. We show that in a finite number of communication rounds, the processors reach consensus on a common ellipsoid whose center is-with high confidence-feasible for the entire set of uncertainty except a subset having an arbitrary small probability measure. We corroborate the theoretical results with numerical computations in which the algorithm is tested on a multi-core platform of processors communicating asynchronously.