Advanced

Line Search for Averaged Operator Iteration

Giselsson, Pontus LU ; Fält, Mattias LU and Boyd, Stephen (2016)
Abstract
Many popular first order algorithms for convex optimization, such as forward-backward splitting, Douglas-Rachford splitting, and the alternating direction method of multipliers (ADMM), can be formulated as averaged iteration of a nonexpansive mapping. In this paper we propose a line search for averaged iteration that preserves the theoretical convergence guarantee, while often accelerating practical convergence. We discuss several general cases in which the additional computational cost of the line search is modest compared to the savings obtained.
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, ADMM, Douglas–Rachford splitting
pages
26 pages
publisher
arXiv.org
external identifiers
  • scopus:85010782415
language
English
LU publication?
yes
id
181e0b91-6353-45ad-90d6-7b8e7d6f042a
alternative location
http://arxiv.org/abs/1603.06772
date added to LUP
2016-05-13 13:50:25
date last changed
2017-08-20 04:58:46
@misc{181e0b91-6353-45ad-90d6-7b8e7d6f042a,
  abstract     = {Many popular first order algorithms for convex optimization, such as forward-backward splitting, Douglas-Rachford splitting, and the alternating direction method of multipliers (ADMM), can be formulated as averaged iteration of a nonexpansive mapping. In this paper we propose a line search for averaged iteration that preserves the theoretical convergence guarantee, while often accelerating practical convergence. We discuss several general cases in which the additional computational cost of the line search is modest compared to the savings obtained.},
  author       = {Giselsson, Pontus and Fält, Mattias and Boyd, Stephen},
  keyword      = {OPTIMIZATION,First order optimization algorithms,ADMM,Douglas–Rachford splitting},
  language     = {eng},
  month        = {03},
  note         = {Working Paper},
  pages        = {26},
  publisher    = {arXiv.org},
  title        = {Line Search for Averaged Operator Iteration},
  year         = {2016},
}