Google Summer of Code 2016: Optim.jl
In the spring, my proposal to work on Optim.jl was accepted by the NumFOCUS organization and GSoC 2016. It has been a great opportunity for me to improve my programming skills in general, and work on a Julia package that I care about. Some things have worked out, and some things haven’t.
The package I have worked on is basically a collection of solvers with a coherent interface, mainly for unconstrained mathematical programming. Standard algorithms such as gradient descent (and variants), conjugate gradient, (L-)BFGS, and variations on Newton’s Method.
At the beginning of GSoC’16, the package was actually in okay shape. Lots of the functionality was in there, and the package generally worked. However, there were some long standing issues, some frozen pull requests, and more to be done. Benchmarking was done on a few select problems, and some solvers lacked testing.
My Life as Groundskeeper Willie
The biggest surprise is how much janitorial work I have done over the summer. Optim is, and was, by no means idle or inactive. However, there is always a specific danger related to an open source project’s life: the volunteering developers. No one is getting paid (unless they’re GSoC’ers), so the project only receives the resources (time) that people can throw at it without jepardizing their family lifes, work lifes, or studies. Optim saw an initial sprint with a lot of activities, but lately the work has been more sporadic. Given my activity under the GSoC banner, I have to a large extent worn one of the “maintaner” caps. This means responding to issues, reviewing pull requests (including reading the academic work underlying them), tagging releases, handling deprecations and iteroperability with other packages, and more.
It might seem as if the experience has taken time and effort away from the things in my original proposal, and obviously it has. However, I really think it has given me a great insight into the way open source communities work, and what it takes to successfully develop and maintain open source software. While it is only a hypothesis, I dare to suggest that the increased activity coming from the GSoC-project has increased general interest of contributing to the package. New contributors have made successful pull requests or important things such as: improved support for preconditioning, a Newton solver using a trust region approach to ensure convergence, a particle swarm solver, and more.
Pushing a polytope downhill
A major re-write of the Simulated Annealing solver was also carried out as part of this project. The old solver was essentially a direct implementation of the original Nelder and Mead (1965) paper. As shown in Gao and Han (2010)), it is possible to improve on the performance for high-dimensional problems, by letting the parameters vary with the dimension of the input to the objective function.
The pull request (merged) can be found here, and documentation of the new functionality is here. Besides improving the ability of finding the minimizer, the new code is also significantly faster, and has a much smaller memory use. In an application mentioned in the pull request it is a hundred times faster, and requires on 1/20th of allocated memory as the old version.
The state of benchmarking in Optim was lacking. Over the summer I have experimented with testing the solvers on the well-known CUTEst test set. I leveraged the existing package CUTEst.jl to easily compile and call the objective functions and gradients for each problem. The package has been a bit of a moving target, as it has seen some changes over the summer, but the development branch is now in a state where it is much easier to use from Optim’s side.
Some pictures showing the results can be seen below.
The work is not entirely done, mostly because it is not yet clear what the best hosting solution is. The benchmarks creates two csv files and a few images per commit that is benchmarked, and it might be optimal to move this machinery to an OptimExtras.jl package. The (currently) active pull request can be found here.
What, why, and how?
Prior to the summer, Optim’s documentation system was basically the README.md file in the Github repository. The new documentation is based on Documenter.jl. Documenter.jl is a Julia package that generates documentation based on files provided, and doc strings from the actual code. It is quite need, and we need to take advantage of more features in the future, for example the automatic testing if the examples provided actually run, or break due to changes in the code.
The new documentation contains the old information from the README, but also additional information on particular solvers, how to use automatic differentiation, and more. While the pull request is merged, more information is still waiting to be added, and hopefully the documentation can be supplemented with example notebooks in the future.
This part of the proposal could have gone further. Testing a solver is not necessarily straight forward. One thing you can do, as we do, is to take a test problem with a known solution, and see if the solver succeeds. Testing all the components is a bit more tricky, although of course possible. More work needs to be done, but so far what was done was simply to make sure that solvers are tested on the small sample we already have in Optim, as well as running the benchmarks to see if some solvers seem to have significant, and surprising, performance issues. The AcceleratedGradientDescent solver might be such a case identified during this GSoC.
Besides the things mentioned in the project description other smaller additions made it into the package over the summer. A NEWS.md file was added so it is easier to remember and communicate changes since last version tag. I also changed the automatic differentiation to use ForwardDiff instead of the DualNumbers we used to use. The most important improvement here is the ability to use automatic differentiation for the second order methods, that is we now provide AD Hessians.
That’s All Folks!
I would like to thank Miles Lubin who encouraged me to apply, and has been my mentor, NumFOCUS which is the organization my project is carried out for, Google for creating Google Summer of Code, and the Danish weather for providing lots of computer time by raining all summer.
List of Commits
To fulfill the requirements, I list all commits below. My commits to Optim.jl can be found here, but they also include older and will include future commits done outside of GSoC.
- 24ad090 - getting the docs up and running (introduce Documenter.jl to Optim.jl)
- 013d264 - clean README.md of information moved to docs, and improve docs
- 21bd318 - fix encryption for Documenter.jl
- 025c8cc - small Documenter.jl fix due to Julia slightly changing to v0.6-dev
- d80282c allow for more optimizers in combination with box constrains
- 98e50c8 - improve Nelder-Mead trace, and parameterize OptimizationTrace to allow for solver based dispatch
- 4e16fb8 - implement Adaptive Parameters Nelder-Mead and document it
- 88f8e48 - switch to the ForwardDiff automatic differentiation functionality
- fffb8ca - allow for automatic differentiation in NewtonTrustRegion
- b1c7de4 - trace tests for BFGS and NelderMead
- b2188d7 - trace tests and cleaning of some files
- c6a5efc - improve tests for BFGS, GradientDescent, MomentumGradientDescent, Newton, NewtonTrustRegion, and add tests for bounded, univariate optimization
Misc. changes including general bug fixes
- b013257 - preparing transition from Optim v0.4 to v0.5
- 2b586e9 - add a NEWS.md to keep track of progress in Optim.jl
- 244d032 - small indentation adjustment
- 5a8e2a1 - use vecnorm instead of norm
- 276c98d - Deprecate old NelderMead API
- 32d6b37 - NEWS.md coverage improvement
- 3351bb6 - make use of syntax for lower and upper bounds constraints consistent
- bb81e1e - cleaning of NewtonTrustRegion and ParticleSwarm constructors and NEWS.md
- e8e75a8 - fix direction reset branch in ConjugateGradient -2e7d238 - fix small NelderMead printing error
- d25efee - get package ready for v0.6.1