Distributed Convex Optimization with Many Convex Constraints

An optimization problem can be called large scale if it involves a large number of optimization variables, and/or a large number of input parameters, and/or a large number of constraints. The increasing availability of distributed hardware suggests to address large scale optimization problems by distributed algorithms. Here we design and analyze a distributed algorithm for general convex optimization problems that involve a large number of constraints. The algorithm is a variant of the alternating direction method of multipliers (ADMM) that was proposed by Glowinski and Marroco [7] and by Gabay and Mercier [4]. Recently, ADMM regained significant attention, especially in the machine learning community, because it allows to solve convex optimization problems that involve a large number of parameters in a distributed setting [2]. In a typical machine learning method, like the least squares method for regression problems, the parameters are just the data points. Hence, ADMM is often the method of choice for Big Data problems, where the data does not fit into the memory of a single compute node. The optimization problem behind a typical Big Data machine learning method usually aims at minimizing a so called loss-function that is the sum of the losses for each data point. Hence, the objective function f of such problems is separable, i.e., it holds that f(x)