Advanced

Line search for generalized alternating projections

Fält, Mattias LU and Giselsson, Pontus LU (2017) 2017 American Control Conference, ACC 2017 In 2017 American Control Conference, ACC 2017 p.4637-4642
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 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... (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 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
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
2017 American Control Conference, ACC 2017
pages
6 pages
publisher
Institute of Electrical and Electronics Engineers Inc.
conference name
2017 American Control Conference, ACC 2017
external identifiers
  • scopus:85027048836
DOI
10.23919/ACC.2017.7963671
language
English
LU publication?
yes
id
84b5e053-9b35-4fb8-a8ee-a73a0f09decd
date added to LUP
2017-09-01 13:07:00
date last changed
2017-09-12 13:00:39
@inproceedings{84b5e053-9b35-4fb8-a8ee-a73a0f09decd,
  abstract     = {<p>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 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.</p>},
  author       = {Fält, Mattias and Giselsson, Pontus},
  booktitle    = {2017 American Control Conference, ACC 2017},
  language     = {eng},
  month        = {06},
  pages        = {4637--4642},
  publisher    = {Institute of Electrical and Electronics Engineers Inc.},
  title        = {Line search for generalized alternating projections},
  url          = {http://dx.doi.org/10.23919/ACC.2017.7963671},
  year         = {2017},
}