Scholarlink

<p>We study the convergence properties of the “greedy” Frank-Wolfe (GFW) algorithm with a unit step size, for a concave minimization problem (or equivalently, convex maximization) over a compact set. We assume that the function satisfies smoothness and strong concavity. These assumptions, together with the Kurdyka-Łojasiewicz (KL) property, allow us to derive global asymptotic convergence for the sequence generated by the algorithm. Furthermore, we also derive a convergence rate that depends on the geometric properties of the problem. To illustrate the implications of the convergence result obtained, we prove a new convergence result for a sparse principal component analysis algorithm, propose a convergent reweighted <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\ell _1\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ℓ</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> minimization algorithm for compressed sensing, and design a new algorithm for the semidefinite relaxation of the Max-Cut problem, which is very efficient numerically, solving dense instances with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\textrm{n}=\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>n</mtext> <mo>=</mo> </mrow> </math></EquationSource> </InlineEquation> 30,000 in under two seconds.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Strongly convex maximization via the Frank-Wolfe algorithm with the Kurdyka-Łojasiewicz inequality

  • 期刊论文

  • 发表日期：

    2026年7月8日

查看全文
  • Fatih S. Aktaş,
  • Christian Kroer

摘要

We study the convergence properties of the “greedy” Frank-Wolfe (GFW) algorithm with a unit step size, for a concave minimization problem (or equivalently, convex maximization) over a compact set. We assume that the function satisfies smoothness and strong concavity. These assumptions, together with the Kurdyka-Łojasiewicz (KL) property, allow us to derive global asymptotic convergence for the sequence generated by the algorithm. Furthermore, we also derive a convergence rate that depends on the geometric properties of the problem. To illustrate the implications of the convergence result obtained, we prove a new convergence result for a sparse principal component analysis algorithm, propose a convergent reweighted \(\ell _1\) ℓ 1 minimization algorithm for compressed sensing, and design a new algorithm for the semidefinite relaxation of the Max-Cut problem, which is very efficient numerically, solving dense instances with \(\textrm{n}=\) n = 30,000 in under two seconds.