<p>In this paper, we propose Riemannian conditional gradient methods for minimizing composite functions, i.e., those that can be expressed as the sum of a smooth function and a retraction-based convex function. We analyze the convergence of the proposed algorithms, utilizing three types of step-size strategies: adaptive, diminishing, and those based on the Armijo condition. We establish the convergence rate of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {O}(1/k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for the adaptive and diminishing step sizes, where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$k$</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation> denotes the number of iterations. Additionally, we derive an iteration complexity of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal {O}(1/\epsilon ^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <msup> <mi>ϵ</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for the Armijo step-size strategy to achieve <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>-optimality, where <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation> is the optimality tolerance. Finally, the effectiveness of our algorithms is validated through some numerical experiments performed on the sphere and Stiefel manifolds.</p>

Riemannian conditional gradient methods for composite optimization problems

期刊论文
发表日期：

2025年12月18日

查看全文

Kangming Chen,
Ellen H. Fukuda

摘要

In this paper, we propose Riemannian conditional gradient methods for minimizing composite functions, i.e., those that can be expressed as the sum of a smooth function and a retraction-based convex function. We analyze the convergence of the proposed algorithms, utilizing three types of step-size strategies: adaptive, diminishing, and those based on the Armijo condition. We establish the convergence rate of $\mathcal {O}(1/k)$ $O (1 / k)$ for the adaptive and diminishing step sizes, where $k$ $k$ denotes the number of iterations. Additionally, we derive an iteration complexity of $\mathcal {O}(1/\epsilon ^2)$ $O (1 / ϵ^{2})$ for the Armijo step-size strategy to achieve $\epsilon $ $ϵ$ -optimality, where $\epsilon $ $ϵ$ is the optimality tolerance. Finally, the effectiveness of our algorithms is validated through some numerical experiments performed on the sphere and Stiefel manifolds.