Alternating minimization methods for strongly convex optimization
Authors
- Tupitsa, Nazarii
- Dvurechensky, Pavel
ORCID: 0000-0003-1201-2343 - Gasnikov, Alexander
- Guminov, Sergey
2010 Mathematics Subject Classification
- 90C30 90C25 68Q25
Keywords
- Convex optimization, alternating minimization, block-coordinate method, complexity analysis
DOI
Abstract
We consider alternating minimization procedures for convex optimization problems with variable divided in many block, each block being amenable for minimization with respect to its variable with freezed other variables blocks. In the case of two blocks, we prove a linear convergence rate for alternating minimization procedure under Polyak-Łojasiewicz condition, which can be seen as a relaxation of the strong convexity assumption. Under strong convexity assumption in many-blocks setting we provide an accelerated alternating minimization procedure with linear rate depending on the square root of the condition number as opposed to condition number for the non-accelerated method.
Appeared in
- J. Inverse Ill-Posed Probl., 29 (2021), pp. 721--739, DOI 10.1515/jiip-2020-0074 .
Download Documents