Synthesis of optimization algorithms by concatenation

Based on the idea that classes of algorithms can be modeled with abstract schemas, a systematic approach to algorithm analysis has been developed over the past two decades [6, 7, 9, 12, 13, 14, 18, 19, 22]. The approach consists of identifying a given algorithm with the appropriate schema, and in using the convergence proof-pattern associated with that schema to structure and simplify the analysis of the properties of the given algorithm. It stands to reason that a similar approach may prove useful in simplifying and systematizing the synthesis of algorithms. Assuming that a collection of problem models, and the corresponding algorithm schemas is available, the synthesis approach will consist of identifying the given problem with the appropriate problem model, and then synthesizing the desired algorithm by incorporating the specific properties of the problem into the schema or schemas which correspond to the problem model. Some problem models and associated algorithm schemas already exist. The best known problem model is the fixed point formulation. In this model it is assumed that the solution set of the problem is described as the fixed point set of a point-to-point or point-to-set map. The associated schemas are the Picard iteration [17], and its variations through application of averaging processes [3, 4, 8, 10]. In this paper we examine a different problem model, namely the intersection model. This model assumes that the solution set of the problem is described as the intersection of a finite family of component sets, and the corresponding algorithm schema consists of the concatenation of a finite family of autonomous algorithm components, each of which is capable of finding points in one of the component sets. The intersection model is particularly well suited for the analysis and synthesis of relaxation methods. These methods, proposed originally by Jacobi and Seidel for solving linear systems of equations, were extended so that nonlinear systems could be so- ved [16], and then generalized to chaotic procedures [2, 15, 21, 21] . Relaxation methods have also been used on structured optimization problems. For example, in [1] and [11] the problem considered is that of minimizing a functional on a product space, in [9] various coordinate descent algorithms are analyzed using Zangwill´s idea of composition of point-to-set maps, and in [5], Fiorot and Huard present a theory for the analysis of algorithms for optimization which are obtained by cumposition of component algorithms.