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

• 成果类型: Article; Early Access
• 署名作者: Aktas, Fatih S.; Kroer, Christian
• 署名单位: Columbia University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02381-x
• 发表日期: 2026-07-08
• 关键词: frank-wolfe algorithm; Conditional gradient algorithm; Convex Maximization; concave minimization; Kurdyka-& Lstrok; ojasiewicz inequality; Max-Cut algorithm; LIPSCHITZ GRADIENT CONTINUITY; 1st-order methods; semidefinite; CONVERGENCE; minimization; sparsity; optimization; optimality; nonconvex

摘要

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-& Lstrok;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 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 n= 30,000 in under two seconds.