Open Collections

Mao, Xiaoyu

University of British Columbia

Projected 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.

Text

2023-08-22

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/85574

Mathematics

University of British Columbia

UBCO

http://creativecommons.org/licenses/by-nc-nd/4.0/