Optimal and Long-Step Feasibility Algorithms
Abstract:
The method of alternating relaxed projections (MARP) was proposed in the 1950's and is a well known method for finding a point in the intersection of finitely many convex sets. For two sets, the algorithm has three parameters. In this talk, we present how to optimally select these parameters in the setting of two subspaces. We provide a sharp linear convergence rate estimate for the optimal parameters, and show that it depends on the Friedrichs angle between the subspaces. The obtained optimal rate is significantly better than previously known rates for, e.g., Douglas-Rachford splitting and (non-relaxed) alternating projections.
The MARP method performs worse with smaller Friedrichs angles. To avoid that, we present how it can be modified to take longer steps. In each step in MARP, three halfspaces are created that contain the fixed-point set. In the basic method, the next iterate is obtained by a relaxed projection onto one of them. We instead propose to do a relaxed projection onto the intersection of the generated halfspaces, which results in longer steps. We also propose some variations of the basic long-step method and show that all these methods converge to a point in the intersection. Numerical examples are presented that show very promising performance.
Biography:
Pontus Giselsson is an Associate Professor at the Department of Automatic Control at Lund University, Sweden. His current research interests include mathematical optimization and its applications in, e.g., control and signal processing. He received an M.Sc. degree from Lund University in 2006 and a Ph.D. degree from Lund University in 2012. During 2013 and 2014, he was a postdoc at Stanford University. In 2012, he received the Young Author Price at an IFAC Symposium, in 2013 he was a finalist for the Best Student Paper Award at the American Control Conference, in 2014, he received the Young Author Price at the IFAC World Congress, and in 2015 he received the Ingvar Carlsson Award from the Swedish Foundation for Strategic Research.