Error Forgetting of Bregman Iteration

Date
2012-01
Journal Title
Journal ISSN
Volume Title
Publisher
Description
Abstract

This short article analyzes an interesting property of the Bregman iterative procedure for minimizing a convex piece-wise linear function J(x) subject to linear constraints Ax=b. The procedure obtains its solution by solving a sequence of unconstrained subproblems, each minimizing J(x) + (1/2) ||Ax-bk||2, and iteratively updating bk. In practice, the subproblems are solved with finite accuracy. Let wk denote the numerical error at iteration k. If all wk are sufficiently small, Bregman iteration identifies the optimal face in finitely many iterations, and afterward, it enjoys an interesting error-forgetting property: the distance between the current point and the optimal solution set is bounded by ||wk+1-wk||, independent of the numerical errors at previous iterations. This property partially explains why the Bregman iterative procedure works well for sparse optimization and ||x||1 minimization. The error-forgetting property is unique to piece-wise linear functions (i.e., polyhedral functions) J(x), and it is new to the literature of the augmented Lagrangian method.

Description
Advisor
Degree
Type
Technical report
Keywords
Citation

Yin, Wotao and Osher, Stanley. "Error Forgetting of Bregman Iteration." (2012) https://hdl.handle.net/1911/102193.

Has part(s)
Forms part of
Published Version
Rights
Link to license
Citable link to this page