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

We present and analyze an away-step Frank–Wolfe method for the convex optimization problem ${\min }_{x\in \mathcal{X}}\hspace{0.17em}f(\mathsf{A}x)+〈c,x〉$, where f is a θ-logarithmically homogeneous self-concordant barrier, $\mathsf{A}$ is a linear operator that may be noninvertible, $〈c,·〉$ is a linear function, and $\mathcal{X}$ 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 $\mathcal{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.

Funding: This work was supported by the Air Force Office of Scientific Research [Grant FA9550-22-1-0356].