[WIP/RFC] GSoC: Improving the State of Optim.jl

[pkofod]

Thought I would open an umbrella issues for the things I plan to work in during GSoC 2016. You can find my introductory post over at julia-opt at the bottom, as well as the (by NumFOCUS) required blog.

• Break code Release v0.5.0 with the breaking changes fully implemented. We need this because I really want the keywords to be in sync with the rest of the API. It's good to have a clean slate to work off of. I will have to provide upper bounds to packages depending on Optim.jl over at METADATA.jl. See Tag Optim v0.5.0 JuliaLang/METADATA.jl#5330
• Documentation This will be sort of based off of README.md, but in a more structured manner, and using a proper docs solution, I am thinking mkdocs+ReadTheDocs. RTD seems pretty standard in the Julia ecosystem, and I must say I prefer markdown+mkdocs to Sphinx, based on my limited experience with both. Comments or objections are welcome. See http://pkofod.github.io/OptimDoc.jl/latest/. I ticked it off, but it will obviously see improvements over the summer.
• Optimization test suite I have to figure out what to do to interpret the CUTE(st) problems. It could be possible to hook into CuTest.jl, but it would be pretty neat to have a SIFDecoder.jl.
• Regression Performance tracking I propose we track iteration counts of different kinds, but also timings. A problem here is how to maintain a stable testing system (same setup everytime). I could use a server at work (University of Copenhagen), but that does seem a bit too fragile (tied to one person). Thoughts?
• Comparisons The results from above will be used to compare different algorithms for problems in the test suite. I would love a sortable list (sort by iterations, f_calls, g_calls, ...) so a user can pick an algorithm based on his or her knowledge of the expense of making an f_call, a g_call or whatever (javascript?), but a couple of static tables could work as well. Performance profiles and statistics on run times would also be included.
• Unit Tests
• Implement low-hanging improvements Implement the improved Simulated Annealing, and adaptive Nelder Mead.
• Presentation I was supposed to do a workshop at JuliaCon, but, unfortunately, I had to cancel. Instead, I will do a brief presentation at my university, and also at a PyData JuliaTalk meet-up.
• Misc To the extent possible, I would love to see an Optim.jl package by the end of GSoC, without any issues (besides discussions). This means that I would love to implement stuff like time limits and more, but this is only if the bullets above can be ticked off first.

julia-opt intro post : https://groups.google.com/forum/#!topic/julia-opt/9Ah5SQYYlgg
revived blog : http://pkofod.github.io/

[Evizero]

RTD seems pretty standard in the Julia ecosystem, and I must say I prefer markdown+mkdocs to Sphinx

ReadTheDocs has a markdown (in the form of CommonMark) option. As far as I know the reStructuredText option is more powerful though.

Regression tracking

Some regression could be measured with the returned metadata like g_calls, right? Other than that you could try normalizing results using the processor clockspeed or other relevant system infos. No idea how well that would work though

[pkofod]

Thanks for the comments!

ReadTheDocs has a markdown (in the form of CommonMark) option. As far as I know the reStructuredText option is more powerful though.

Yes, I know RTD supports markdown, it was meant as a "I want to use RTD and Markdown, not RTD and RST.". I think you may be right about RST being more powerful in some sense, but I'm not sure. I was kind of going with markdown being easier to use, together with the fact that docstrings are now markdown -> #14378 . If RST and Sphinx is preferred by the community, I'll figure out how to do it.

Some regression could be measured with the returned metadata like g_calls, right? Other than that you could try normalizing results using the processor clockspeed or other relevant system infos. No idea how well that would work though

(edited to be called performance tracking) Yes, I agree that a lot could be captured by f_calls and g_calls holding the optimized function fixed. It would be nice to track run time evolution with JuliaLang versions as well though, and f_calls and g_calls should not really be affected by these kinds of changes.

[KristofferC]

I would warmly recommend https://github.com/MichaelHatherly/Documenter.jl for generating documentation. It combines very nicely with mkdocs so that docs are automatically updated when a new master get merged. I've played with it a bit for some hobby projects like http://kristofferc.github.io/BlockArrays.jl/latest/.

[mlubin]

JuMP is trying to move away from RTD, so don't feel any need to use it.

CC @IainNZ

[pkofod]

Great with further comments. I will surely look at Documenter.jl. (I just looked, it seems pretty neat!). It does seem a lot simpler than an external service.

[IainNZ]

Yes, I'm investigating Documenter.jl now. I think, even if it isn't perfect, its something worth supporting through use if we take a longer view of the ecosystem.

[Evizero]

I just briefly looked it over. While the aspect of automatic documentation certainly has it's appeal, the results seem (at first glance) very different to handcrafted examples when it comes to types and functions.

automatic: http://kristofferc.github.io/BlockArrays.jl/latest/lib/public/
handcrafted: http://augmentorjl.readthedocs.io/en/latest/api/imagesource.html

Then again, I suppose with a bit of community adoption, maybe the results could be improved significantly

[pkofod]

While the aspect of automatic documentation certainly has it's appeal, the results seem (at first glance) very different to handcrafted examples when it comes to types and functions.

Are you referring to the formatting? Maybe I've misunderstood something, but why wouldn't Documenter.jl-powered docs be "handcrafted" ? It's still just a bunch of markup-files getting parsed by something, possibly including "automatic" elements such as fetching docstrings.

edit I see what you mean. The automatically fetched docstrings do not look very nicely formatted. That could obviously change!

edit what about this example instead? http://michaelhatherly.github.io/NumericSuffixes.jl/latest/ it does not use the RTD theme.

Some regression could be measured with the returned metadata like g_calls, right? Other than that you could try normalizing results using the processor clockspeed or other relevant system infos. No idea how well that would work though

I know this won't be perfect either, but maybe simply running against the PR, and current HEAD of the target branch is enough.

[cortner]

How about

• implement a steihaug method?

[pkofod]

I spent too much time trying to setup a dummy repo for the docs to test things out. I had forgotten to add the public key to my settings, oops. It's over at http://pkofod.github.io/OptimDoc.jl/latest/, but very sparsely filled out, and somewhat hurried. Most of the things were put in to test a specific feature. Will add more asap.

[pkofod]

It requires a bit of fiddling, but...

julia> using CUTEst

julia> nlp = CUTEstModel("ALLINITU")
Minimization problem ALLINITU
nvar = 4, ncon = 0 (0 linear)

julia> using Optim

julia> obj(nlp, nlp.meta.x0)
13.0

julia> f(x) = obj(nlp, x)
f (generic function with 1 method)

julia> g!(x, stor) = grad!(nlp, x, stor)
g! (generic function with 1 method)

julia> optimize(f, nlp.meta.x0)
Results of Optimization Algorithm
 * Algorithm: Nelder-Mead
 * Starting Point: [0.0,0.0,0.0,0.0]
 * Minimizer: [1.4598776154349462,-5.382256469615769e-6, ...]
 * Minimum: 5.744385e+00
 * Iterations: 96
 * Convergence: true
   *  √(Σ(yᵢ-ȳ)²)/n < 1.0e-08: true
   * Reached Maximum Number of Iterations: false
 * Objective Function Calls: 176


julia> optimize(f, g!, nlp.meta.x0)
Results of Optimization Algorithm
 * Algorithm: BFGS
 * Starting Point: [0.0,0.0,0.0,0.0]
 * Minimizer: [1.4598615643816433,0.0, ...]
 * Minimum: 5.744385e+00
 * Iterations: 13
 * Convergence: true
   * |x - x'| < 1.0e-32: false
   * |f(x) - f(x')| / |f(x)| < 1.0e-32: true
   * |g(x)| < 1.0e-08: true
   * Reached Maximum Number of Iterations: false
 * Objective Function Calls: 55
 * Gradient Calls: 55

or a 5000 dimensional seperable extension of Rosenbrock

julia> optimize(f, nlp.meta.x0)
Results of Optimization Algorithm
 * Algorithm: Nelder-Mead
 * Starting Point: [1.2,1.0, ...]
 * Minimizer: [1.1997439297424661,1.0002982814213657, ...]
 * Minimum: 4.848823e+04
 * Iterations: 1000
 * Convergence: false
   *  √(Σ(yᵢ-ȳ)²)/n < 1.0e-08: false
   * Reached Maximum Number of Iterations: true
 * Objective Function Calls: 6002

julia> optimize(f, g!, nlp.meta.x0)
Results of Optimization Algorithm
 * Algorithm: BFGS
 * Starting Point: [1.2,1.0, ...]
 * Minimizer: [0.9999999999634346,0.9999999999223543, ...]
 * Minimum: 6.140105e-19
 * Iterations: 53
 * Convergence: true
   * |x - x'| < 1.0e-32: false
   * |f(x) - f(x')| / |f(x)| < 1.0e-32: false
   * |g(x)| < 1.0e-08: true
   * Reached Maximum Number of Iterations: false
 * Objective Function Calls: 265
 * Gradient Calls: 265

Ouch Nelder Mead!

I've compiled a list of unconstrained problems in CUTEst (some 200 I think). Let's see how good we are at minimizing :)

[pkofod]

Did the presentation today. I think it went well. Unfortunately, a lot of people in the audience didn't really use optimization for their work, or were not familiar with optimization at all. Anyway, it was fun, and I hope some people got something out of it :)

[GiggleLiu]

Hi, I am from http://julianlsolvers.github.io/Optim.jl/v0.9.3/algo/simulated_annealing/

The current implementation of Simulated Annealing is very rough. It lacks quite a few features which are normally part of a proper SA implementation. A better implementation is under way, see this issue.

Wondering if simulated annealing is still in progress?

[marcobonici]

Any news on this PR?

[pkofod]

This is not a PR but my very old proposal for a GSoC. What are you referring to exactly? :)

[marcobonici]

Sorry, my bad. The documentation points to here, saying that the simulated annealing implementation is a bit rough. Is it true?

[pkofod]

Wow, interesting. I do not remember writing that. 2016 is a long time ago.

I don't really know what it would mean. There are so many simulated annealing versions out there. I think we could point to Optim.SAMIN instead that should be a better implementation. This was added many years ago.

edit: see #1116