The 2017 SIAM Activity Group on Optimization Prize was awarded to Jérôme Bolte, Shoham Sabach, and Marc Teboulle for their paper, “Proximal Alternating Linearized Minimization for Nonconvex and Nonsmooth Problems,” published in Mathematical Programming, Series A, in 2014. The prize was awarded May 23, 2017, at the SIAM Conference on Optimization (OP17) in Vancouver, BC, Canada. Shoham Sabach presented the work of the paper in his talk, “Proximal Minimization Algorithms for Nonconvex and Nonsmooth Problems.”
The SIAM Activity Group on Optimization (SIAG/OPT) awards the SIAG/OPT Prize to the author or authors of the most outstanding paper, as determined by the prize committee, on a topic in optimization published in English in a peer-reviewed journal. The prize committee commended the authors for presenting a simple and versatile first-order algorithm for composite optimization, relevant to important applications, and a powerful semi-algebraic convergence analysis under mild assumptions.
Jérôme Bolte is a Professor in the Toulouse School of Economics at the University of Toulouse 1 Capitole, where he has been on the faculty since 2010. He earned his PhD at the University of Montpellier 2 in 2003. After postdoctoral fellowships at Simon Fraser University and the University of Chile, he joined the faculty of Pierre and Marie Curie University Paris 6 in 2004, before moving to Toulouse. His research interests center on continuous optimization, and algorithms and dynamical systems.
Shoham Sabach has been Assistant Professor in the Faculty of Industrial Engineering and Management at Technion-Israel Institute of Technology since 2014. He received his PhD in 2012 from the Technion. After graduation, he moved to Tel Aviv University for a postdoc position with Marc Teboulle, and then moved to the University of Göttingen as a Humboldt Research Fellow. Sabach’s research interests lie at the interface of core continuous optimization, algorithms, and applications.
Marc Teboulle is a Professor in the Department of Statistics and Operations Research in the School of Mathematical Sciences at Tel Aviv University. He received his DSc from Technion-Israel Institute of Technology in 1985. He has held a position of Applied Mathematician at Israel Aircraft Industries and academic appointments at Dalhousie University and the University of Maryland. Teboulle was elected a SIAM Fellow in 2017. He serves on the editorial board of
SIAM Journal on Optimization. His research interests are in the area of continuous optimization, including theory, algorithmic analysis and its applications.
All three authors collaborated on their answers to our questions.
Q: Why are you excited about winning the prize?
A: It is always a very pleasant and exciting adventure to work together on a new project. We enjoyed the mind blowing interactions, and learned a lot of new mathematics from each other. In this research, we invested an intensive effort to put forward a simple and versatile framework for the convergence analysis of algorithms for semi-algebraic optimization problems. We are grateful to those who kindly nominated us, and thankful to the prize committee for selecting our work. It is very gratifying to learn that our peers appreciate our research, and we hope this award will draw further attention to the methodology we have developed.
Q: Could you tell us a bit about the research that won you the prize?
A: Our main goal was to tackle the famous Nonnegative Matrix Factorization (NMF) problem, which is central to many problems in learning, imaging, and many other fields. We then realized that this problem could be seen as a special case of a broader class of problems involving composite structure and semi-algebraic data. Our friend and collaborator Jérôme Bolte, with his co-authors, pioneered the use of semi-algebraic geometry to study the convergence of descent iterative methods in optimization. In particular, nonsmooth Kurdyka-Lojasiewicz inequalities are the central tool to establishing the finite length property (and hence global convergence) of a sequence produced by descent schemes. We were then excited to discover that we can combine and use these powerful semi-algebraic tools well beyond the NMF problem. Our research resulted not only in a versatile and simple first-order algorithm (PALM) for a broad class of nonsmooth and nonconvex composite minimization with convergence guarantees, but also in a flexible general methodology for proving global convergence of descent methods. We are enthusiastic to learn that our work had an impact on numerous recent works on the convergence analysis of various novel iterative algorithms in nonconvex optimization which are using our approach.
Q: What does your research mean to the public?
A: Optimization plays a central role in applied mathematics and scientific applications with far reaching practical impact on our daily life. Nonconvex optimization problems are widespread in the modeling of real world and complex systems covering a very broad spectrum of disparate areas, such as image reconstruction in biology and astronomy, finance, learning features for facial recognition, communication systems, and optics to mention just a few. Thanks to the sustained increase in computational power, optimization algorithms based on simple iterative methods often perform surprisingly well, and improve the capability to tackle highly complex problems which are vital to advancing modern technologies. Our framework and the algorithm we developed are the very first step in understanding the mathematical tools underlying the good convergence properties of simple descent methods used in some of the applications mentioned above. We hope that further developments and enhancements of our approach will lead to the discovery of new performance methods in important applications.
Q: What does being a SIAM member mean to you?
A: SIAM is a first-class organization for applied mathematics, and it serves the community world-wide. Applied mathematics is central in all areas of science, and the role of SIAM in promoting applied mathematics through its journals and conferences is considered the gold standard. We are thus proud to be part of the vibrant environment that SIAM offers. We feel fortunate to have the opportunities it provides us and to add our contributions through our active participation.