Derivative-free nonlinear optimization for .NET and Java

Optimization of non-linear objective functions and potentially also non-linear constraints is a common problem in for example radiation therapy.

More often than not, the objective and constraint functions are not easily differentiable, which limits the possibility of applying the more efficient derivative-based optimization algorithms (of which IPOPT is a prominent open-source example).

There are several more or less time-efficient ways of solving (constrained) non-linear optimization problems, including simulated annealing, genetic algorithms and direct search methods such as the Nelder-Mead method (a good overview of mathematical optimization with several links is provided here.)

One rather popular code for solving non-linear optimization problems involving (potentially nonlinear) constraints is the COBYLA2 method. Originally formulated and implemented in Fortran 77 by Michael Powell, this method has been ported to both Fortran 90 and C (through f2c conversion), and it has also been integrated into the Python scientific calculations library scipy. COBYLA2 is simple to use, but it exhibits a rather slow convergence rate; the number of function and constraint evaluations required to locate an optimum that meets the constraints is often very large. As a first-attempt solver when objective and constraint function gradients are complex or time-consuming to derive, COBYLA2 is however often a good choice.

Being primarily a .NET developer, it has until recently not been straightforward to incorporate COBYLA2 though. It has of course been possible to build a native DLL and call COBYLA2 via P/Invoke. This works relatively well in a full .NET Framework environment, but it is only barely applicable in Silverlight applications and completely inapplicable in Windows Phone applications. On the other hand, the Fortran code is relatively well structured and well documented, so I recently decided to port COBYLA2 to C#.

I based the porting on the Fortran 90 code, since this implementation already utilizes more C/C++/C# like constructs. The porting has been successful and I have released the end result as an open-source project cscobyla on Github. Included in this project are unit tests demonstrating the use of COBYLA2 in C# applications. The C# code is very straightforward and does not make use of any advanced functions, so it should be possible to incorporate the code in Silverlight and Windows Phone applications just as easy as it can be incorporated in regular .NET applications. When built into a C# class library, it should be straightforward to reference the COBYLA2 optimization from any other .NET language as well.

Encouraged by the successful porting to C#, I then embarked on a Java porting experience! I have not been able to find a pure Java implementation of COBYLA2, so I considered this a good Java development exercise. Java does not provide delegates, multidimensional arrays can only be represented as jagged arrays, and Java does not support the goto statement, so I was forced to make some design changes. Nevertheless, the Java porting effort also succeeded, and I have also made this result available as open source on Github, the jcobyla project.

And this is not all there is! As mentioned, COBYLA2 converges slowly. Michael Powell has made several efforts to overcome this issue for specialized cases by making use of a local quadratic approximation rather than a linear approximation that is being used in COBYLA2. These improvements have been made available in the NEWUOA code for unconstrained optimization of nonlinear objective functions, and more recently for bound constrained optimization of nonlinear objective functions in the BOBYQA (Bound Optimization BY Quadratic Approximation) code. These codes exhibits substantially improved convergence properties compared to COBYLA2, albeit for unconstrained or bound constrained problems only.

In particular, I consider the BOBYQA being a very interesting development, as many problems encountered in for example radiation therapy can be formulated as bound constrained problems. BOBYQA has not been available for the .NET platform other than through P/Invoke, so again I decided to port Fortran code to C#. This time I had to rely on the Fortran 77 implementation, since I have not been able to identify any Fortran 90 port of BOBYQA. It took some additional effort, but even BOBYQA is now available as open source in C#. I have denoted this project csbobyqa and made it available on Github. Also written using standard C# constructs, the code should be easily incorporated in any .NET, Silverlight or Windows Phone application.

In the case of BOBYQA, there actually already is an open-source Java implementation available as part of the Apache Commons Math project. The API for this Java class can be found here. 

To confirm that my C# implementation is sufficiently efficient, I have also identified the longest-running unit test (bound-constrained Rosen with varying number of interpolation points) in the Java implementation and implemented the corresponding unit test in the C# unit test library. On my laptop, the C# unit test takes around 15 seconds in each consecutive run, whereas the corresponding unit test on the Java implementation ranges from 15 to 40 seconds. I am not sure why the Java timing varies this much, but it is however encouraging that the C# implementation consistently performs equal to or better than the Java implementation in this case.

To re-iterate, here are the links to my most recent open-source optimization projects:

.NET COBYLA2: https://github.com/cureos/cscobyla

.NET BOBYQA: https://github.com/cureos/csbobyqa

Java COBYLA2: https://github.com/cureos/jcobyla

Good luck with the derivative-free optimization!