Advanced

Line Search for Generalized Alternating Projections

Fält, Mattias LU and Giselsson, Pontus LU (2016)
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Working Paper
publication status
published
subject
keywords
Optimization, First order optimization algorithms
pages
14 pages
publisher
arXiv.org
language
English
LU publication?
yes
id
e2d5b7d2-ca14-4ddc-a580-0e2fefc1c960
alternative location
https://arxiv.org/abs/1609.05920
date added to LUP
2016-10-03 16:06:37
date last changed
2016-10-05 12:10:08
@misc{e2d5b7d2-ca14-4ddc-a580-0e2fefc1c960,
  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. },
  author       = {Fält, Mattias and Giselsson, Pontus},
  keyword      = {Optimization,First order optimization algorithms},
  language     = {eng},
  month        = {09},
  pages        = {14},
  publisher    = {ARRAY(0xa459850)},
  title        = {Line Search for Generalized Alternating Projections},
  year         = {2016},
}