Back to search

University of British Columbia

Bregman generalized subgradient projected algorithms and applications

Abstract

dc:description

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.

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

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Mao, Xiaoyu. Bregman generalized subgradient projected algorithms and applications. master's thesis, University of British Columbia, 2023. http://hdl.handle.net/2429/85574