PESTO swMATH ID: 20864 Software Authors: Taylor, Adrien B.; Hendrickx, Julien M.; Glineur, F. Description: Code of the Performance Estimation Toolbox (PESTO) whose aim is to ease the access to the PEP methodology. The numerical worst-case analyses from PEP can be performed just by writting the algorithms just as you would implement them: Exact worst-case performance of first-order methods for composite convex optimization. We provide a framework for computing the exact worst-case performance of any algorithm belonging to a broad class of oracle-based first-order methods for composite convex optimization, including those performing explicit, projected, proximal, conditional and inexact (sub)gradient steps. We simultaneously obtain tight worst-case guarantees and explicit instances of optimization problems on which the algorithm reaches this worst-case. We achieve this by reducing the computation of the worst-case to solving a convex semidefinite program, generalizing previous works on performance estimation by Drori and Teboulle [13] and the authors [43]. We use these developments to obtain a tighter analysis of the proximal point algorithm and of several variants of fast proximal gradient, conditional gradient, subgradient and alternating projection methods. In particular, we present a new analytical worst-case guarantee for the proximal point algorithm that is twice better than previously known, and improve the standard worst-case guarantee for the conditional gradient method by more than a factor of two. We also show how the optimized gradient method proposed by Kim and Fessler in [22] can be extended by incorporating a projection or a proximal operator, which leads to an algorithm that converges in the worst-case twice as fast as the standard accelerated proximal gradient method [2] Homepage: https://github.com/AdrienTaylor/Performance-Estimation-Toolbox Source Code: https://github.com/AdrienTaylor/Performance-Estimation-Toolbox Keywords: convex optimization; composite convex optimization; first-order methods; worst-case analysis; performance estimation; semidefinite programming; convex interpolation Related Software: YALMIP; CVX; SeDuMi; UNLocBoX; Mosek; Saga; Wasserstein GAN; GitHub; TensorFlow; Finito; DFO; Wirtinger Flow; Eigtool; SDPT3; Mathematica; AlexNet; IQC-Game; SBEED; ImageNet; CVXPY Cited in: 40 Publications all top 5 Cited by 70 Authors 9 Taylor, Adrien B. 5 Fessler, Jeffrey A. 5 Glineur, François 5 Kim, Donghwan 4 Drori, Yoel 3 de Klerk, Etienne 3 Hendrickx, Julien M. 3 Ryu, Ernest K. 2 Gasnikov, Alexander V. 2 Lessard, Laurent 2 Öktem, Ozan 1 Abbaszadehpeivasti, Hadi 1 Adler, Jonas 1 Alkousa, Mohammad S. 1 Arridge, Simon R. 1 Asl, Azam 1 Bachir, Mohammed 1 Banert, Sebastian 1 Bao, Xuchan 1 Becker, Stephen R. 1 Bergeling, Carolina 1 Bolte, Jérôme 1 Dall’Anese, Emiliano 1 d’Aspremont, Alexandre 1 Ding, Zhengtao 1 Dong, Zhen 1 Dragomir, Radu-Alexandru 1 Dvinskikh, D. M. 1 Fazlyab, Mahyar 1 Gannot, Oran 1 Giselsson, Pontus 1 Grosse, Roger 1 Gu, GuoYong 1 Hannah, Robert 1 Hildebrand, Roland 1 Hu, Bin 1 Iutzeler, Franck 1 Jordan, Michael Irwin 1 Karlsson, Johan 1 Kovalev, D. A. 1 Li, Zhongguo 1 Liang, Zhongchao 1 Lieder, Felix 1 Maass, Peter 1 Madden, Liam 1 Morari, Manfred 1 Overton, Michael L. 1 Preciado, Victor M. 1 Recht, Ben 1 Ribeiro, Alejandro R. 1 Rieger, Janosch 1 Ringh, Axel 1 Salzo, Saverio 1 Schönlieb, Carola-Bibiane 1 Seiler, Peter J. 1 Stonyakin, Fedor Sergeevich 1 Tam, Matthew K. 1 Tan, Sandra S. Y. 1 Tan, Vincent Yan Fu 1 Tapia-García, Sebastián 1 Tyurin, A. I. 1 Varvitsiotis, Antonios E. 1 Villa, Silvia 1 Vũ, Bằng Công 1 Wilson, Ashia C. 1 Yang, Junfeng 1 Yin, Wotao 1 Zamani, Moslem 1 Zhang, Guodong 1 Zhang, Hui all top 5 Cited in 14 Serials 9 Mathematical Programming. Series A. Series B 8 SIAM Journal on Optimization 6 Journal of Optimization Theory and Applications 3 Optimization Letters 2 Journal of Complexity 2 Computational Mathematics and Mathematical Physics 2 Optimization Methods & Software 2 Journal of Machine Learning Research (JMLR) 1 Applied Mathematics and Computation 1 Automatica 1 Journal of Convex Analysis 1 Mathematical Methods of Operations Research 1 Acta Numerica 1 Advances in Operator Theory all top 5 Cited in 13 Fields 35 Operations research, mathematical programming (90-XX) 17 Computer science (68-XX) 9 Calculus of variations and optimal control; optimization (49-XX) 8 Numerical analysis (65-XX) 7 Operator theory (47-XX) 3 Systems theory; control (93-XX) 1 Real functions (26-XX) 1 Functional analysis (46-XX) 1 Geometry (51-XX) 1 Convex and discrete geometry (52-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Statistics (62-XX) 1 Information and communication theory, circuits (94-XX) Citations by Year