Book on Acceleration in Optimization
This monograph covers some recent advances in a range of acceleration techniques frequently used in convex optimization. We first use quadratic optimization problems to introduce two key families of methods, namely momentum and nested optimization schemes. They coincide in the quadratic case to form the Chebyshev method.
We discuss momentum methods in detail, starting with the seminal work of Nesterov and structure convergence proofs using a few master templates, such as that for optimized gradient methods, which provide the key benefit of showing how momentum methods optimize convergence guarantees. We further cover proximal acceleration, at the heart of the Catalyst and Accelerated Hybrid Proximal Extragradient frameworks, using similar algorithmic patterns.
Common acceleration techniques rely directly on the knowledge of some of the regularity parameters in the problem at hand. We conclude by discussing restart schemes, a set of simple techniques for reaching nearly optimal convergence rates while adapting to unobserved regularity parameters.
Non-exhaustive list of methods we talk about:
- Chebyshev’s method and Polyak’s momentum (a.k.a. Heavy-ball method),
- (Regularized) Nonlinear Acceleration,
- Nesterov’s scheme and Optimized Gradient Descent,
- Catalyst scheme and Guller/Monteiro-Svaiter acceleration,
- Restart schemes.
[Website]
FAST Toolbox for Matlab
FAST (Finally An SDDP Toolbox) is an easy-to-use Stochastic Dynamic Dual Programming (SDDP) toolbox for Matlab. It helps you to model and solve your problem easily and quickly! The goal of SDDP is to solve large-scale stochastic problems with an algorithm based on the Cutting plane method.
Three typical applications of FAST,
- Energy production In the energy production domain, FAST allows for accurate solutions when dealing with uncertain energy supply or demand.
- Factory production line When the demand is unknown, FAST helps you plan your production to maximize your revenue.
- Financial products FAST allows you to deal with random portfolios in the stock exchange business.
[Website]
[Git repository]
JSR Toolbox for Matlab
I partially contributed to the JSR toolbox by implementing a few algorithms. The Joint Spectral Radius of a set of matrices characterizes the maximal asymptotic rate of growth of a product of matrices taken in this set when the length of the product increases. It is known to be very hard to compute. In recent years, many different methods have been proposed to approximate it.
These methods have different advantages, depending on the application, the type of matrices, the desired accuracy or running time, etc. This toolbox aims to provide the practitioner with the best available methods and propose an easy tool for the researcher to compare the different algorithms.
[Website]