Optimization Online


Computational acceleration of projection algorithms for the linear best approximation problem

Yair Censor (yair***at***math.haifa.ac.il)

Abstract: This is an experimental computational account of projection algorithms for the linear best approximation problem. We focus on the sequential and simultaneous versions of Dykstra's algorithm and the Halpern-Lions-Wittmann-Bauschke algorithm for the best approximation problem from a point to the intersection of closed convex sets in the Euclidean space. These algorithms employ different iterative approaches to reach the same goal but no mathematical connection has yet been found between their algorithmic schemes. We compare these algorithms on linear best approximation test problems that we generate so that the solution will be known a priori and enable us to assess the relative computational merits of these algorithms. For the simultaneous versions we present a new component-averaging variant that substantially accelerates their initial behavior for sparse systems.

Keywords: Projection algorithms; linear best approximation; component-averaging; acceleration.

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Linear Algebra and Its Applications, Vol. 416 (2006), pp. 111-123.


Entry Submitted: 10/06/2005
Entry Accepted: 10/06/2005
Entry Last Modified: 06/12/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society