A systematic approach to the synthesis of algorithms

This paper presents a theory which allows the systematic synthesis of a class of iterative algorithms by using a specially structured model called thep-algorithm and a set of transformations so that the new algorithm obtained by repeated application of these transformations still solves the problem.

Abstract

This paper presents a theory which allows the systematic synthesis of a class of iterative algorithms. The basic idea consists of using a specially structured model called thep-algorithm and a set of transformations. These transformations are chosen so that if thep-algorithm solves a given problem, then the new algorithm obtained by repeated application of these transformations still solves the problem. One of the applications of the approach is the synthesis of algorithms which satisfy a-priori given specifications. Given a set of primitives, one may transform an algorithm which uses primitives not in the allowable set into an algorithm which uses only allowable primitives. The theory is illustrated by the systematic transformation of a well known algorithm for optimization, the Frank-Wolfe algorithm.