Line Search for Generalized Alternating Projections

Research output: Working paper

Abstract

This paper is about line search for the generalized alternating projections (GAP) method. This method is a generalization of the von Neumann alternating projections method, where instead of performing alternating projections, relaxed projections are alternated. The method can be interpreted as an averaged iteration of a nonexpansive mapping. Therefore, a recently proposed line search method for such algorithms is applicable to GAP. We evaluate this line search and show situations when the line search can be performed with little additional cost. We also present a variation of the basic line search for GAP - the projected line search. We prove its convergence and show that the line search condition is convex in the step length parameter. We show that almost all convex optimization problems can be solved using this approach and numerical results show superior performance with both the standard and the projected line search, sometimes by several orders of magnitude, compared to the nominal method.

Details

Authors
Organisations
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computational Mathematics

Keywords

  • Optimization, First order optimization algorithms
Original languageEnglish
PublisherarXiv.org
Number of pages14
StatePublished - 2016 Sep 19

Related projects

Mattias Fält & Pontus Giselsson

Swedish Research Council, Stiftelsen för Strategisk Forskning, SSF

Project: Research

View all (1)