Preprint
An Away-Step Frank-Wolfe Method for Minimizing Logarithmically-Homogeneous Barriers
ArXiv.org
Cornell University
05/28/2023
DOI: 10.48550/arxiv.2305.17808
Abstract
We present and analyze a new away-step Frank-Wolfe method for the convex optimization problem minx∈Xf(Ax)+⟨c,x⟩, where f is a θ-logarithmically-homogeneous self-concordant barrier, A is a linear operator, ⟨c,⋅⟩ is a linear function and X is a nonempty polytope. We establish affine-invariant and norm-independent global linear convergence rate 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, Sun and Todd (2008). We also show that the iterates generated by our method will land on a face of X in a finite number of iterations, and this may lead to improved local linear convergence rates. We conduct numerical experiments on the problems of D-optimal design and inference of multivariate Hawkes processes, and the results not only showcase the efficiency and effectiveness of our method compared to other first-order methods, but also corroborate our theoretical results fairly well.
Details
- Title: Subtitle
- An Away-Step Frank-Wolfe Method for Minimizing Logarithmically-Homogeneous Barriers
- Creators
- Renbo Zhao
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- DOI
- 10.48550/arxiv.2305.17808
- ISSN
- 2331-8422
- Publisher
- Cornell University
- Language
- English
- Date posted
- 05/28/2023
- Academic Unit
- Business Analytics
- Record Identifier
- 9984447840302771
Metrics
31 Record Views