Journal article
Convergence rate analysis of the multiplicative gradient method for PET-type problems
Operations research letters, Vol.51(1), pp.26-32
01/2023
DOI: 10.1016/j.orl.2022.11.010
Abstract
We analyze the convergence rate of the multiplicative gradient (MG) method for PET-type problems with m component functions and an n-dimensional optimization variable. We show that the MG method has an O(ln(n)/t) convergence rate, in both the ergodic and the non-ergodic senses. Furthermore, we show that the distances from the iterates to the set of optimal solutions converge (to zero) at rate O(1/t). Our results show that, in the regime n=O(exp(m)), to find an ε-optimal solution of the PET-type problems, the MG method has a lower computational complexity compared with the relatively-smooth gradient method and the Frank-Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier.
Details
- Title: Subtitle
- Convergence rate analysis of the multiplicative gradient method for PET-type problems
- Creators
- Renbo Zhao - MIT Operations Research Center, Muckley Bldg, 1 Amherst St, Cambridge, 02142, MA, USA
- Resource Type
- Journal article
- Publication Details
- Operations research letters, Vol.51(1), pp.26-32
- Publisher
- Elsevier B.V
- DOI
- 10.1016/j.orl.2022.11.010
- ISSN
- 0167-6377
- eISSN
- 1872-7468
- Grant note
- DOI: 10.13039/100000181, name: Air Force Office of Scientific Research, award: FA9550-19-1-0240
- Language
- English
- Date published
- 01/2023
- Academic Unit
- Business Analytics
- Record Identifier
- 9984446535902771
Metrics
1 Record Views