Key Takeaway: The paper presents a systematic approach for synthesis of iterative algorithms using thep-algorithm and transformations, enabling the transformation of well-known algorithms into ones satisfying a-priori specifications.

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.