New Analysis of an Away-Step Frank-Wolfe Method for Minimizing Log-Homogeneous Barriers

• 成果类型: Article; Early Access
• 署名作者: Zhao, Renbo
• 署名单位: University of Iowa
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.0281
• 发表日期: 2025
• 关键词: CONVERGENCE-RATES; 1st-order methods; optimal designs; algorithm; MODEL

摘要

We present and analyze an away-step Frank-Wolfe method for the convex optimization problem minx is an element of Xf(Ax) + < c , x > , where f is a theta-logarithmically homogeneous self-concordant barrier, A is a linear operator that may be noninvertible, < c , > is a linear function, and X is a nonempty polytope. The applications of primary interest include D-optimal design, inference of multivariate Hawkes processes, and total variationregularized Poisson image deblurring. We establish affine-invariant and norm-independent global linear convergence rates of our method in terms of both the objective gap and the Frank-Wolfe gap. When specialized to the D-optimal design problem, our results settle a question left open since Ahipasaoglu et al. [Ahipasaoglu SD, Sun P, Todd MJ (2008) Linear convergence of a modified Frank-Wolfe algorithm for computing minimum-volume enclosing ellipsoids. Optim. Methods Software 23(1):5-19]. We also show that the iterates generated by our method will land on and remain in a face of X within a bounded number of iterations, which can lead to improved local linear convergence rates (for both the objective gap and the Frank-Wolfe gap). We conduct numerical experiments on D-optimal design and inference of multivariate Hawkes processes, and our results not only demonstrate the efficiency and effectiveness of our method compared with other principled first-order methods but also, corroborate our theoretical results quite well.