Parallel Cost Approximation Algorithms for Differentiable Optimization

Michael Patriksson
Department of Mathematics
Linköping Institute of Technology
Linköping
Sweden

ABSTRACT:

This paper presents a unified analysis of decomposition algorithms for
continuously differentiable optimization problems defined on Cartesian
products of convex feasible sets.  The decomposition algorithms are
analyzed using the framework of cost approximation algorithms.  A
convergence analysis is made for three decomposition algorithms: a
sequential algorithm which encompasses the classical Gauss--Seidel
scheme, a synchronized parallel algorithm which encompasses the Jacobi
method, and a partially asynchronous parallel algorithm.  The analysis
validates inexact computations in both the subproblem and line search
phases.  The range of feasible step lengths within each algorithm is
shown to have a direct correspondence to the increasing degree of
parallelism and asynchronism, and the resulting usage of more outdated
information in the algorithms.

KEY WORDS: Cartesian Product Sets, Convex Optimization, Decomposition,
Cost Approximation, Sequential Algorithm, Parallel Processing,
Partially Asynchronous Algorithms