Optimization-Solvers

Numerical optimization solvers for unconstrained and simple bound-constrained convex optimization problems. The solvers are implemented in Rust and are based on the ACM Collected Algorithms. The solvers are designed to be easy to use and to be easily integrated into existing codebases.

Note: Currently the unique non-rust solver is L-BFGS-B, which uses code bindings to the original Fortran implementation.

Modules and submodules of this crate follow the bipartition presented in [Nocedal, J., & Wright, S. J. (2006). Numerical optimization] regarding optimization algorithms:

• Line search methods:
  • Steepest descent methods
  • Newton methods
  • Quasi-Newton methods
  • Conjugate gradient methods
• Trust region methods:

In the figure above: minimization of quadratic function using gradient descent solver

Todo

• Consider implementing solutions for line search in constrained optimization
• Consider adding preconditioning techniques

Links

• ACM digital library: https://dl.acm.org/
• ACM Collected Algorithms: https://calgo.acm.org/
• IEEE Xplore: https://ieeexplore.ieee.org/Xplore/home.jsp

Books and articles on convex optimization:

• GLL non-monotone line search algorithm: L. Grippo, F. Lampariello and S. Lucidi, “A Nonmonotone Line Search Technique for Newton’s Methods,” SIAM Journal on Numerical Analysis, Vol. 23, No. 4, 1986, pp. 707-716.
• Hessian ill-conditioning hobbles first order methods (section 3.1): Nicholas Vieau Alger (2019), "Data-Scalable Hessian Preconditioning for Distributed Parameter PDE-Constrained Inverse Problems", PhD Thesis, University of Texas at Austin
• Misc. on numerical optimization: Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge university press. (Chapter 9)
• Misc. on numerical optimization: Nocedal, J., & Wright, S. J. (2006). Numerical optimization. Springer Science & Business Media.
• Misc. on numerical optimization:Neculai Andrei, 2022. "Modern Numerical Nonlinear Optimization," Springer Optimization and Its Applications, Springer, number 978-3-031-08720-2, December
• Misc. on numerical optimization + cubic and quadratic interpolation: Sun, Wenyu & Yuan, Ya-xiang. (2006). Optimization theory and methods. Nonlinear programming
• Moré-Thuente line search algorithm: Jorge J. Moré and David J. Thuente. 1994. Line search algorithms with guaranteed sufficient decrease. ACM Trans. Math. Softw. 20, 3 (Sept. 1994), 286–307.
• NEOS Guide: NEOS Guide
• Online scaling gradient methods (OSGM): Gao, W., Chu, Y. C., Ye, Y., & Udell, M. (2024). Gradient Methods with Online Scaling. arXiv preprint arXiv:2411.01803
• Survey of existing solvers for bound-constrained optimization: Tröltzsch, A. (2007). Benchmarking of bound-constrained optimization software
• Survey of existing solvers for bound-constrained optimization: Birgin, E.G., Gentil, J.M. Evaluating bound-constrained minimization software. Comput Optim Appl 53, 347–373 (2012)
• Spectral Projected Gradient Method (ACM Algo 813): Birgin, Ernesto & Martínez, José Mario & Raydan, Marcos. (2014). Spectral Projected Gradient Methods: Review and Perspectives. Journal of Statistical Software. 60. 1-21. 10.18637/jss.v060.i03.

Nice community questions

• Preconditioning gradient descent: https://stats.stackexchange.com/questions/91862/preconditioning-gradient-descent
• Basic preconditioned gradient descent example: https://stats.stackexchange.com/questions/486594/basic-preconditioned-gradient-descent-example
• Relating condition number of hessian to the rate of convergence: https://math.stackexchange.com/questions/2285282/relating-condition-number-of-hessian-to-the-rate-of-convergence
• What is ill conditioning for a system of linear equations: https://www.quora.com/What-is-ill-conditioning-for-systems-of-linear-equations
• What is a ill conditioned matrix: https://www.quora.com/What-is-an-ill-conditioned-matrix
• What methods can be used for preconditioning of ill conditioned matrix: https://www.quora.com/What-methods-can-be-used-for-preconditioning-of-ill-conditioned-matrix
• Subtractive cancellation errors during computation: https://tobydriscoll.net/fnc-julia/intro/conditioning.html
• Painless conjugate gradient: https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf
• A note on preconditioning: https://www.math.iit.edu/~fass/477577_Chapter_16.pdf