GSoC 2017: Constrained Optimisation

[antonior92]

Hello, my name is Antonio and I am a Brazilian electrical engineer currently pursuing my master degree. I am interested in applying to Google Summer of Code 2017 with the proposal of implementing optimisation methods for problems with nonlinear constraints.

My proposal is to implement one or more state-of-the-art solvers (interior point and SQP methods) for constrained optimisation problems. I would like to get some feedback about this, discuss the relevance of it for Optim.jl package and get some suggestions of possible mentors.

[antonior92]

The existence of the branch constrained just come to my knowledge. What is the status of it? I have seem that there is a pending pull request from November, 2016.

[pkofod]

I think this would make for a great gsoc idea. Start by reading the latest pr and the pr it replaced to get an idea about the current status of constrained optimization in optim.

Edit: Let me add, I will be more than happy to comment on any and all work you do, but I don't think I would be the perfect mentor for you, as constrained optimization is by no means my speciality. Since @timholy produced #303 #50 he could be a suggestion, but I don't know if he is mentoring another gsoc project, or if he even has time at all. Ideally, you should find someone with a good knowledge of the theory/practice of constrained optimization, as I will, and I'm sure others will as well, be more than happy to comment on the API and Julia side of things.

[anriseth]

Adding nonlinear constraints support to Optim would be very welcome. My knowledge of these algorithms are only at the level of what's in Nocedal+Wright.

Here are some ideas on what I believe would be very valuable for Optim and such a project:

• Build on Constrained optimization episode 2: revenge of the slack variables #303 (which hopefully will have been pulled by the start of the project)
  • Implement interior point with Quasi-Newton (and/or GradientDescent if that is possible?)
• Implement a SQP method
• A MathProgBase interface (extend https://github.com/gragusa/OptimMPB.jl, or integrate with Optim)
  • This will make benchmarking/comparisons with other solvers easier
• Benchmarking suite (build on OptimTests.jl)
  • Would be great to show that we can compete with the state of the art (similar to Constrained optimization episode 2: revenge of the slack variables #303 (comment))

[antonior92]

I would like to thank you both for your comments. I've take a look at #303 and I think most ideas suggested by @anriseth are very good:

• Add support to quasi-Newton Hessian approximations should be very useful for the package users.
• Implement a SQP method would be nice. It does have it advantages over Interior Point methods for some cases.
• By what I have seem in Constrained optimization episode 2: revenge of the slack variables #303 most of the work for the interface have already been done by @timholy, so it should not be very hard to come up with a MathProgBase interface for the constrained method.

Another idea I could include in my proposal is to implement support for sparse matrices. I think this may require modifications in several places of the package and require a lot of work, however it could be very beneficial for the package as a whole: Other already implemented methods could benefit from it (e.g. Conjugate-gradient and L-BFGS) and, furthermore, Interior Point methods are powerful tools for dealing with large-scale optimisation (what cannot be fully explored right now).

[cortner]

Maybe not what you want, but a very Julia-specific idea that has come up on these issues somewhere is to refactor Optim.jl so that the state x need not be a Vector{Float64} anymore. This would be quite powerful for some applications and make Optim.jl quite unique amongst optimisation software I think.

[antonior92]

Sorry @cortner I didn't manage to understand your suggestion well enough. Can you point me out the issue you are talking about or try to explain in another way? Do you mean like to allow x to be an Vector{Int} (integer programming problems) or a combination (combinatorial optimisation)... Or did you mean something else?

[cortner]

In #326 , @ChrisRackauckas made this suggestion. As I write this, I am thinking this won't be enough for a GSOC project, but it would still be a good side-project.

[ChrisRackauckas]

@antonior92 some examples:

1. It would allow different numbers. Arbitrary precision is likely the most useful. BigFloat and ArbFloats are good libraries for this which would likely just work. DecFP has 128-bit decimal numbers which would likely just work. Odd numbers like Unums, etc. It's also the first step to allowing autodifferentiation through the optimization routine since it would allow Dual numbers.

2. Any AbstractArray would be able to work. SharedArray and DistributedArrays allow for easily parallelism. But you could also use things like RaggedArrays, MultiScaleArrays (essentially a type of graph with a linear index), CatViews, etc.

Julia's type-specialization design makes it so that way this abstraction actually has zero overhead, so using Vector{Float64} will still have the same performance, and all of these other setups will be "optimal" as well.

It definitely wouldn't be enough to be a GSoC project. For someone well-versed in Julia, this would likely be just a 1-day project. But if you're looking for some minor contributions which will get you familiar with Optim and Julia to be able to showcase in your application, this is something you could consider doing along the way.

[antonior92]

Thank you for the explanation! I will consider to implement it.

[antonior92]

I have just finished the first draft of my GSoC proposal:
https://www.dropbox.com/s/8f9loi3ue9k3923/GSoC2017.pdf?dl=0
what do you guys think? Any feedback would be much appreciated

[antonior92]

I based my proposal mostly on @anriseth suggestions. I decided to implement a trust-region SQP method, which I think is a method that work well for a large range of problems and will provide, together with the interior points method in ongoing integration, greater flexibility for the package. I intend to build my algorithm on the top of the branch for constrained optimisation @timholy already started to work on.

@ChrisRackauckas @cortner The idea in #326 didn't seem to fit well with the other tasks in my proposal so, unfortunately, I decided to left it of.

I included in my deliverables: i) to interface my method with the MathProgBase interface, what I think will make easier to compare the implemented method with other optimisation software; and, ii) to test it using CUTEst benchmarks (By what I have grasped the package OptimTest.jl being developed by @pkofod and @timholy already is going in that direction and could be useful).

[timholy]

#303 is probably a good starting point, and you're welcome to bring it up to speed and merge it. I won't have a lot of time for helping to mentor, I think we have 2-3 applicants for JuliaImages.

[pkofod]

I wish you the very best of luck. I think we should start an issue on constrained Interface. It would be a good task for you to survey what we have and what Tim Holy suggested in his PR, and then we can have a discussion. Could be now, or you can wait until the community bonding period (if your application is chosen).

[antonior92]

Thank you both for the comments. I think it is a good idea to create an issue for discussing the constrained interface. I will create it after some more study in the interface Tim Holy suggested.
Furthermore I can start helping with #303 during my community bounding period.
It would be a good way to familiarise myself with the package internals.

Also, if my application is chosen we will have as a byproduct a quadratic programming solver that we will have to decide how to fit in.

[anriseth]

It looks good, I hope you are chosen. It would be really nice to get #303 up and running, and aligned with the changes from #337 and #388. (And maybe move the custom linesearch stuff in the PR to LineSearches).

Also, if my application is chosen we will have as a byproduct a quadratic programming solver that we will have to decide how to fit in.

Does this require special inputs different from what the other solvers would require? If not, the most important thing is that someone are happy to keep maintaining the solver.

[pkofod]

@antonior92 Sad to see you go to SciPy (https://summerofcode.withgoogle.com/projects/#5890418190319616 ) but congrats nonetheless!

[antonior92]

Hey guys,

I would like to thank you all for the suggestions and for the ideas. The other proposal I have submitted to GSoC (also about optimization) was the one that got selected so, unfortunately, I will not have the opportunity to follow on the project I have showed to you guys.

Nevertheless, I am very excited about Julia, which is, more and more, my language of choice for all things. I think that there is already a great environment for optimization implemented on it and I hope to have the opportunity to contribute to it in other ways.

[pkofod]

I think that there is already a great environment for optimization implemented on it and I hope to have the opportunity to contribute to it in other ways.

You're always welcome to contribute! As far as I'm concerned, your SciPy project is a great way for you to find out how you're going to implement your awesome Julia version of the constrained optimizer in Optim come next GSoC ;)

(oh, and by the way, I think SciPy is a great project, so really, congrats on landing the Python-project!)

[antonior92]

It make sense, I am getting experience to implement a more awesome solver next year :)

By the way, congratulations for also having your project accepted!