Convergence analysis of the transformed gradient projection algorithms on compact matrix manifolds
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909914609221632 |
|---|---|
| author | Ding, Wentao Li, Jianze Zhang, Shuzhong |
| author_facet | Ding, Wentao Li, Jianze Zhang, Shuzhong |
| contents | In this paper, we study the optimization problem on a compact matrix manifold. While existing feasible algorithms can be broadly categorized into retraction-based and projection-based methods, compared to the more comprehensive and in-depth algorithmic and convergence research framework for retraction-based line-search (RetrLS) algorithms using only tangent vectors, the theoretical understanding and algorithmic design of projection-based line-search (ProjLS) algorithms remain limited, especially when general search directions and stepsizes are involved. To bridge this gap, we propose a unified algorithmic framework called the Transformed Gradient Projection (TGP) algorithm. The key idea is to construct the search direction as a transformed Riemannian (or Euclidean) gradient augmented by an additional normal component, allowing the framework to encompass and generalize numerous existing algorithms. Then, we conduct a thorough exploration of the convergence properties of the TGP algorithms under various stepsizes, including the Armijo, Zhang-Hager type nonmonotone Armijo, and fixed stepsizes. To achieve this, we extensively analyze the geometric properties of the projection onto compact matrix manifolds, which may be of independent interest. Building upon these insights, we establish the weak convergence, iteration complexity, and global convergence of TGP algorithms under three distinct stepsizes. In cases where the compact matrix manifold is the Stiefel or Grassmann manifold, our convergence results either encompass or surpass those found in the literature. Finally, through a series of numerical experiments and theoretical analysis, we observe that different choices of scaling matrices and normal components in the search direction of TGP algorithms can lead to significantly different performance in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_19392 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Convergence analysis of the transformed gradient projection algorithms on compact matrix manifolds Ding, Wentao Li, Jianze Zhang, Shuzhong Optimization and Control Numerical Analysis 15A23, 49M37, 65K05, 90C26, 90C30 In this paper, we study the optimization problem on a compact matrix manifold. While existing feasible algorithms can be broadly categorized into retraction-based and projection-based methods, compared to the more comprehensive and in-depth algorithmic and convergence research framework for retraction-based line-search (RetrLS) algorithms using only tangent vectors, the theoretical understanding and algorithmic design of projection-based line-search (ProjLS) algorithms remain limited, especially when general search directions and stepsizes are involved. To bridge this gap, we propose a unified algorithmic framework called the Transformed Gradient Projection (TGP) algorithm. The key idea is to construct the search direction as a transformed Riemannian (or Euclidean) gradient augmented by an additional normal component, allowing the framework to encompass and generalize numerous existing algorithms. Then, we conduct a thorough exploration of the convergence properties of the TGP algorithms under various stepsizes, including the Armijo, Zhang-Hager type nonmonotone Armijo, and fixed stepsizes. To achieve this, we extensively analyze the geometric properties of the projection onto compact matrix manifolds, which may be of independent interest. Building upon these insights, we establish the weak convergence, iteration complexity, and global convergence of TGP algorithms under three distinct stepsizes. In cases where the compact matrix manifold is the Stiefel or Grassmann manifold, our convergence results either encompass or surpass those found in the literature. Finally, through a series of numerical experiments and theoretical analysis, we observe that different choices of scaling matrices and normal components in the search direction of TGP algorithms can lead to significantly different performance in practice. |
| title | Convergence analysis of the transformed gradient projection algorithms on compact matrix manifolds |
| topic | Optimization and Control Numerical Analysis 15A23, 49M37, 65K05, 90C26, 90C30 |
| url | https://arxiv.org/abs/2404.19392 |