Logo image
Back
New Analysis of an Away-Step Frank–Wolfe Method for Minimizing Log-Homogeneous Barriers
Journal article   Peer reviewed

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

Renbo Zhao
Mathematics of operations research, Vol.51(1), pp.35-59
01/2026
DOI: 10.1287/moor.2023.0281

View Online

Abstract

We present and analyze an away-step Frank–Wolfe method for the convex optimization problem min𝑥∈𝒳 𝑓⁡(𝖠⁢𝑥)+〈𝑐,𝑥〉, where f is a θ-logarithmically homogeneous self-concordant barrier, 𝖠 is a linear operator that may be noninvertible, 〈𝑐,·〉 is a linear function, and 𝒳 is a nonempty polytope. The applications of primary interest include D-optimal design, inference of multivariate Hawkes processes, and total variation-regularized 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 𝒳 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.
 away-step Frank-Wolfe logarithmically homogeneous self-concordant barrier facial distance

Details

Metrics

6 Record Views
1 Times Cited - Web of Science
Logo image