Bregman method

Bregman's method is an iterative algorithm to solve certain convex optimization problems. The algorithm is a row-action method accessing constraint functions one by one and the method is particularly suited for large optimization problems where constraints can be efficiently enumerated. The original version is due to Lev M. Bregman.[1]

The algorithm starts with a pair of primal and dual variables. Then, for each constraint a generalized projection onto its feasible set is performed, updating both the constraint's dual variable and all primal variables for which there are non-zero coefficients in the constraint functions gradient. In case the objective is strictly convex and all constraint functions are convex, the limit of this iterative projection converges to the optimal primal dual pair.

The method has links to the method of multipliers and dual ascent method and multiple generalizations exist.

One drawback of the method is that it is only provably convergent if the objective function is strictly convex. In case this can not be ensured, as for linear programs or non-strictly convex quadratic programs, additional methods such as proximal gradient methods have been developed.

References
  1. Bregman L. "A Relaxation Method of Finding a Common Point of Convex Sets and its Application to Problems of Optimization". Dokl. Akad. Nauk SSSR, v. 171, No. 5, 1966, p.p. 1019-1022. (English translation: Soviet Math. Dokl., v. 7, 1966, p.p. 1578-1581)


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.