Thursday, May 3, 2012

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:


Good luck with the derivative-free optimization!

Monday, December 19, 2011

Ipopt + Silverlight = True!

Today I have released a new version 0.9.5 of csipopt, the .NET interface to the Ipopt large-scale non-linear constrained optimization algorithm.

Compiled libraries can be downloaded here: http://code.google.com/p/csipopt/downloads/list
The source code is available here: https://github.com/cureos/csipopt/tags

A detailed description of the improvements and usage is provided here: https://github.com/cureos/csipopt/wiki/Substantially-extended-API

Highlights include:

  • Unsafe directive requirement removed
  • IpoptProblem sub-classable, yielding cleaner instantiation of the optimization problems
  • Native Ipopt methods publicly available
  • Silverlight 5 supported in elevated-trust, out-of-browser applications
Do not hesitate to discuss or report experiences and problems in the csipopt forum!

Sunday, October 30, 2011

Silverlight mdcm merged into Colby Dillion's main fork!


Yesterday, I was excited to see that my Silverlight and WPF fork of mdcm was merged, in its entirety, into Colby Dillion's main mdcm fork.

Since my efforts have now become more "official", I think it could be worth recalling some of the specific issues that are currently applicable in particular to the Silverlight library of mdcm:

  • The Silverlight class library is currently using Silverlight version 5 Release Candidate. It should be fairly straightforward to revert to Silverlight 4, but there may be some incompatibilities especially with respect to network access.
  • I have tried to implement managed support for JPEG codecs in the Silverlight project, but I have so far stumbled on 12 (and 16) bit support. The available open source JPEG codec libraries (FluxJpeg.Core and LibJpeg.Net) only support 8 bit images, and I have not yet been able to extend either of the libraries to 12 bit support. Furthermore, these libraries only support lossy compression.
  • Silverlight 5 will open up new possibilities for the mdcm Silverlight library, since P/Invoke is now supported when running in so called "elevated trust" mode. In particular, it should be possible to implement network server and full image codec support through calls to native libraries. So far, I have not implemented any of these ideas.
  • I have not made any extensive efforts with the MonoTouch project yet; in particular, no image support is implemented. Basic functionality is there though, DICOM file parsing and network client for example works out-of-the-box.



Wednesday, October 12, 2011

LINQ and Dictionaries

LINQ is a very powerful technique for operating on collections of objects in .NET. If you for example have a collection of integers, it is a simple task to pick the even numbers from the collection using LINQ:

int[] ints = new[] { 1, 3, 6, 8, 9, 10 };
IEnumerable<int> evens = ints.Where(i => i % 2 == 0);


Similarly for dictionaries:

Dictionary<int, int> intDict = new Dictionary<int, int> 
    { { 2, 3 }, { 3, 5 }, { 6, 7}};
Dictionary<int, int> evenKeys = intMap.Where(kv => kv.Key % 2 == 0);


What? Compilation error?!?

In fact, the intDict.Where() statement is not entirely correct. From the LINQ point of view, Dictionary<,> and other classes implementing the IDictionary<TKey, TValue> interface are actually regarded as implementations of the IEnumerable<KeyValuePair<TKey, TValue>> interface. Thus (ignoring for a moment that we could also have used the var keyword), the correct evenKeys assignment should read:

IEnumerable<KeyValuePair<int, int>> evenKeys = 
    intMap.Where(kv => kv.Key % 2 == 0);

Now, my guess is that in the normal case one would rather have the above assignment to return a Dictionary. Fortunately, LINQ also provides a number of ToDictionary method overloads. So for the evenKeys assignment to return a Dictionary we simply type:

Dictionary<int, int> evenKeys = intMap.Where(
    kv => kv.Key % 2 == 0).ToDictionary();

What?! Compilation error again?

Yes, because the ToDictionary method also operates on IEnumerable<T> objects. You need to tell the compiler how you want to design your Dictionary based on this arbitrary type T. For correctness, our evenKeys assignment has to be expressed as follows:

Dictionary<int, int> evenKeys = intMap.Where(kv => kv.Key % 2 == 0).
    ToDictionary(kv => kv.Key, kv => kv.Value);


For dictionaries, this explicitness may appear quite counter-intuitive, and there are several forum questions on the Internet indicating that this API design indeed has caused confusion (here, here and here for example).

After giving this issue some thought, I believe I have come up with an approach to bypass this hurdle of confusion. I have implemented the following extension method in a static utility class:

public static Dictionary<TKey, TValue> ToDictionary<TKey, TValue>(

    this IEnumerable<KeyValuePair<TKey, TValue>> source)

{

    return source.ToDictionary(kv => kv.Key, kv => kv.Value);

}

This overload of ToDictionary takes any object that implements the IEnumerable<KeyValuePair<TKey, TValue>> interface, which is a common return type when invoking LINQ operations on dictionaries, and returns a Dictionary<TKey, TValue> object using the same keys and values as the dictionary in the argument list. With this extension method defined, I now actually can enter:

Dictionary<int, int> evenKeys = intMap.Where(
    kv => kv.Key % 2 == 0).ToDictionary();

without getting the annoying compilation error.

Now this is all good and well, but I then decided to take the issue even one step further. Wouldn't it be good if for example the Where() extension method when operating on a Dictionary by default returned a Dictionary with the same keys and values?

Well, it can of course be done! And here is the solution:

public static Dictionary<TKey, TValue> Where<TKey, TValue>(

    this IDictionary<TKey, TValue> source, 

    Func<KeyValuePair<TKey, TValue>, bool> predicate)
{
    return Enumerable.Where(source, predicate).
        ToDictionary(kv => kv.Key, kv => kv.Value);

}

When this method is defined, it effectively hides the general Where(IEnumerable<T>, Func<>) extension method when the IEnumerable<T> object also implements the IDictionary<TKey, TValue> interface. Having the above Where() extension method defined now even makes it possible for us to apply our first dictionary LINQ attempt without compilation error:

Dictionary<int, int> evenKeys = intMap.Where(kv => kv.Key % 2 == 0);

Unfortunately, this method will always return a Dictionary object, regardless of whether intDict is a SortedDictionary or SortedList or another object implementing the IDictionary<TKey, TValue> interface. At this point, I have no viable solution for returning the same dictionary type that was used as input to the specialized Where method. The quest for a solution will continue nonetheless.

I have also collected a few more similar LINQ extension method overloads in a Github project that I have chosen to call ... dictionarylinq

In this project you may find dictionary overloads for the Except, Intersect and Union extension methods. Due to their signatures, for these methods it has actually been possible to implement a specialized overload that returns the true input dictionary type, together with a designated overload with better performance for the Dictionary<TKey, TValue> class.

Included are also method overloads for the Select method when the return type of the Func<TSource, TResult> object is a KeyValuePair<TKey, TValue>. It would be relatively easy to add more method overloads to dictionarylinq, but for now this is what there is.

When the extension methods from the dictionarylinq utility class are included in your application, these methods will effectively hide the general extension methods in the System.Linq.Enumerable class. If you do want to fall back on the general methods in a certain scenario, either make an explicit cast to the IEnumerable<> interface:

IEnumerable<KeyValuePair<int, int>> output = 

    ((IEnumerable<KeyValuePair<int, int>>)input).Where(kv => kv.Key > 3);

or invoke the static method explicitly:

IEnumerable<KeyValuePair<int, int>> output = 
    Enumerable.Where(input, kv => kv.Key > 3);

Please also note that the dictionarylinq class library in the Visual Studio solution is a Portable Class Library. This means that the library uses the "least common denominator" of .NET Framework 4, Silverlight and Windows Phone 7 base class libraries. The library can be built once and consumed by all three .NET technologies without rebuilding. If you have not installed the Portable Library Tools, simply create a new designated class library project and include the source code from the dictionarylinq class library, or include the source code directly in your own class library or application.

I hope that this effort can be useful also to others than myself. For questions and comments on this work, please do not hesitate to contact me for example via a blog comment. If you are a Github user, please feel free to report code issues via the project's Issues tab.

Good luck with Dictionary and LINQ!

Friday, October 7, 2011

Getting the grip on your version control

I have recently been working with several different open-source projects that are available on Google Code, Github, CodePlex etc. The projects tend to use different software for managing version control, which in turn requires multiple SCM clients to be installed on the development system.

Version control software commonly used in open-source projects today include Subversion, Git and Mercurial. By default, the version control software is accessed through command-line interfaces. However, there are several different GUI wrappers available to facilitate the version control management. On Windows, different flavors of Tortoise are predominantly used. These tools are primarily shell extensions, enabling version control management inside Windows Explorer. TortoiseCVS for CVS version control was first in line, and it has inspired or formed the basis to followers like TortoiseSVN, TortoiseGit and TortoiseHg.

The various Tortoise tools makes version control management much easier and more efficient, and there is normally no problem having several of these tools installed at once on the same computer.

There is one annoying issue though: all the above tools use the same icons and icon overlays in Windows Explorer. It is therefore not immediately possible in Windows Explorer to determine which version control software that is being used to manage a specific folder.


Of course, if you enter the folder the version control administration sub-folders (.svn, .git, .hg, etc.) will be listed if you have configured Windows Explorer to display hidden folders. But this is a sub-optimal behavior; ideally the version control software should be detectable through some indication in the Windows Explorer list, or when hovering the mouse over the folder in question.

In case someone had experienced the same annoyance as I and found a workaround for it, I posted a question on the subject at StackOverflow. I got a few answers primarily explaining why the same icon overlays are used, but then I also got an eye-opening answer from Stefan Küng, lead developer of TortoiseSVN. Stefan suggested me to customize the version controlled top folder using the approach described here. This was exactly what I had looked for: a method for customizing the folder layout and provide explanatory text in the tool-tip when hovering over the folder with the mouse pointer!

My only remaining concern now was that I would have to do this customization manually for each version controlled folder, which would be quite tedious and error-prone when a large number of projects are involved.

But then, what do developers do, if not implementing solutions to repetitive problems?

Thus, I took the bull by the horns and came up with a simple yet efficient console application for managing the folder customization. The application identifies the version control software used in the specified folder, adds a tool-tip and sets the folder icon to indicate which software that is being used to version control the folder. Currently, the application identifies Subversion, Git and Mercurial, but if the conditions are right (version control administration files in a sub-folder with a fix name) it is a straightforward task to extend this list of software. The application source code is available under an open-source license (Eclipse Public License version 1.0) and can be obtained from here.

After running the application on the version-controlled folders in the image above, Windows Explorer will (after a few refreshes) provide the following display:


Hovering with the mouse pointer over a version control decorated folder will clearly indicate the version control software being used:


It is even possible to run the folder decorator application without changing the folder icons. If the icons are not available in the same directory as the folder decorator application, the classic folder icon will be maintained but the tool-tip will still be updated.

The icons have been obtained from the Open Icon Library. The Subversion icon is "Sub-optimal"; I was not able to find a better redistributable Subversion icon. For personal, non-redistributable use, a more identifiable Subversion icon is available here. If you so wish, download this Subversion icon file instead, rename it to svn.ico and replace the existing Subversion icon in the Visual Studio project with the downloaded one.

Happy version-controlling!

Friday, September 16, 2011

P/Invoke: Bundling native DLL:s in Silverlight 5 RC applications

One of the many interesting new features in Silverlight 5 RC is the ability for elevated trust applications (in-browser as well as out-of-browser) to access native DLL:s via P/Invoke.

Some interesting application examples are given here and here. These examples show how easy it is to access system DLL:s such as user32.dll, kernel32.dll and psapi.dll. However, the issue appears to be more complex when it comes to native DLL:s that are not automatically available on the system.

Ideally (I think), you would like to bundle the native third party DLL:s as Content in the XAP file, and the XAP file would be artificially included in the P/Invoke search path. Unfortunately, this is not the way it works today. When I bundle my third-party native DLL as Content in my Silverlight 5 RC application, and try to access one of its methods via the following declaration,

[DllImport("NativeDll")]
public static extern int add(int a, int b);


I get a discouraging DllNotFoundException. It does not help if I add the .dll extension to the file name, and I have also not been able to find the DLL by applying any of the pack URI approaches to the DLL file name.

Several people, including myself, have brought up this issue in various forums, but so far I have not seen any published solution to the problem.

Well, as we say in Sweden, "själv är bäste dräng" (which is similar to "if you want something done, do it yourself"), so here is my attempt to solve the problem. Granted, it might not be the most Elegant Solution, but at least it is A Solution.

It is important to note that this solution is applicable primarily to Silverlight 5 RC. In the best of worlds, Microsoft will fix the native DLL path issue in the RTM release of Silverlight 5, and then this solution would be superfluous. We'll see what happens in the end.

Note also that since P/Invoke is a feature requiring elevated trust, this solution is only relevant to applications running in elevated trust (in- or out-of-browser).


In short, the solution is to bundle the native third party DLL:s as resource files in the Silverlight 5 RC application, and when the application is started copy these DLL:s to a local directory and add the directory to the system path during the execution of the Silverlight application.

In more details, here is how it can be done:

Add each native third party DLL as an existing item to the root folder or, even more preferably, to an assets sub-folder in the Silverlight 5 RC application project.


In the File Properties window, set Build Action to Resource and Copy to Output Directory to Copy if newer.


The DLL copying and PATH environment variable setting of course requires some additional code. Fortunately :-) I have created a static utility class for this purpose. The class is named NativeDllHelper and can be found it is entirety here. Download and add this file to your Silverlight 5 RC application project.

Next, go to the App.xaml.cs or equivalent file. Add the following using statement.

using Cureos.Utility;

In the Application_Startup (or equivalent) event handler, add the following method call to the first line of the event handler.

NativeDllHelper.SetupNativeDllFolder("relpath/dllname.dll", ...);

where relpath is the path relative to the project root folder where the native DLL:s are located, and dllname is the file name of the DLL. Specify all DLL:s to be copied in one argument list; the SetupNativeDllFolder method should only be called once at start-up to avoid adding duplicate entries of the local DLL directory to the system path.

The native DLL files are copied to a My Documents sub-folder Silverlight\Native. If you prefer a different folder for the DLL:s, edit the static constructor of the NativeDllHelper class.

Here is an example call of SetupNativeDllFolder, copying one file NativeDll.dll located in the Assets sub-folder of the Silverlight 5 RC application project.

NativeDllHelper.SetupNativeDllFolder("Assets/NativeDll.dll");

Having performed these steps, no user intervention is required when running the application, the native methods in the third party DLL:s can simply be invoked using only the file name of the DLL:

[DllImport("NativeDll")]
public static extern int add(int a, int b);


A complete example SL 5 RC application utilizing this functionality can be downloaded from here. Note that it contains a C(++) project for creating the example native DLL.
If you try out the application and get build errors due to copy prevention the first time, building a second time should do the trick. You might also need to manually set the start page of the Web project to the .aspx file.


The application itself is very simple; there is this button

with the following click event handler associated to it:

private void Button_Click(object sender, RoutedEventArgs e)
{
  button.Content = add(5, 7);
}

The add method is a native method, as declared above. Clicking the button leaves us with the following satisfying button update:

And that is basically all that there is to it. The utility method for copying DLL:s from the application resources can most certainly be further improved, for example by more efficiently handling DLL:s already existing locally. With the current implementation, any existing DLL:s are automatically overwritten. All improvement suggestions as well as reports of successes or failures are highly appreciated.

Monday, September 5, 2011

csipopt on Silverlight: almost there!

As mentioned in a recent post, it is possible to enable unsafe code support in the release candidate of Silverlight 5 for out-of-browser (OOB) applications in elevated-trust mode. Together with the introduction of P/Invoke support in Silverlight 5, it would thereby in principle be possible to also use my csipopt .NET interface to the IPOPT optimizer in Silverlight.

I have now tested to build and run csipopt on Silverlight 5 RC, and it almost works:
  • The code successfully builds, provided the <AllowUnsafeBlocks> tag is manually set to true in the .csproj file.
  • If I bundle the native IPOPT DLL:s as content or resources in the XAP file, I get a DllNotFoundException. At this point I do not know if this is a bug or by design. For now, it works to place the native IPOPT DLL:s in a directory that is included in the system path.
  • When I run my csipopt calling application in OOB elevated-trust mode, I eventually get a SecurityException: An error relating to security occurred
The exception occurs when trying to access an UnmanagedFunctionPointerAttribute in a call to an imported function from the native DLL. It remains to find out whether this restriction will persist into the final release of Silverlight 5. According to the API documentation, the UnmanagedFunctionPointerAttribute is not intended for regular user code in Silverlight. This writing might not be entirely up-to-date, but realistically, I think the restriction will be there at least in Silverlight 5. After all, I am pushing the limits here, using P/Invoke and unsafe code at the same time.

So, bets are I have to wait for Silverlight 6 to employ csipopt in my Silverlight applications.