University of British Columbia
Bregman generalized subgradient projected algorithms and applications
Abstract
dc:descriptionProjected subgradient methods were thought as ideal algorithms for constrained minimization problems. But they are often hampered by the computational complexity of the projection operator. The generalized Bregman distance has been identified as a potential solution to this issue. This thesis delves into an in-depth analysis and conducts numerical experiments on projected subgradient methods that utilize Bregman distances. Firstly, we discuss the existing mirror descent algorithm, which is designed for one-block constrained minimization problems. Previous research has revealed its equivalence with Bregman projected subgradient method. Subsequently, we expand this algorithm to accommodate two-block situations, thereby increasing its applicability. We also provide its convergence proof. Our algorithm has a strong correlation with another renowned method, the "proximal alternating linearized method," which can be considered a specific variant of our approach. In the numerical experiments, we choose a variety of examples from various fields, such as matrix analysis and statistics. The data we used are derived from both artificial and real-world sources. The results consistently indicate that Bregman generalized algorithms significantly reduce computation time, particularly when the variable is constrained to the unit simplex. This further corroborates our hypothesis that Bregman distances enhance the performance of projected subgradient methods.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Mathematics
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Mao, Xiaoyu
- Contributors dc:contributor
-
- Wang, Xianfu
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivatives 4.0 International
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/85574