Performance considerations

Memory usage

FuncLib is far from perfect. Each operation is represented by some object in a recursive structure (before it's possibly compiled to a linear structure), and this structure may indeed become too big to be feasible, using several gigabytes of memory in some extreme cases. In this case a DualNumber representation can be used instead. The penalty for using DualNumber (and the associated DualMatrix and DualVector) is that many short-lived objects are created during each evaluation, one object for each numerical operation, which is thrown away again as soon as the next operation has been performed. However, using DualNumber there's no memory limitation on the problems that can be handled by FuncLib, and hence it may be the only option for very complicated problems.

(A hybrid of DualNumber combined with Function inside may also be considered.)

The DualNumber representation works by keeping track of the first and second derivatives while performing operations, starting by specifying the known properties of the variables.

// Define DualNumber as variables. We specify our knowledge about the partial derivatives. The Hessian is implicitly zero.
DualNumber x = new DualNumber(2.0, new Vector(new double[] { 1.0, 0.0 }));
DualNumber y = new DualNumber(3.0, new Vector(new double[] { 0.0, 1.0 }));

// Computer a new value through some aritmetics. This is our function.
DualNumber f = x * DualNumber.Exp(x * y);

// Show one of the second order partial derivatives after the operations above.
Console.WriteLine(f.Hessian[0, 1]);

Since all intermediate computations are thrown away during the process, the memory usage keeps low, assuming that garbage collection works efficiently. I've used DualNumber, DualMatrix, and DualVector extensively for very complicated problems myself, and the garbage collection part has worked just fine. No worries here.

To do numerical optimization on a DualNumber structure, DualNumberFunction can be used to perform the proper transformation.

// Traditional variables (i.e. not DualNumber).
Variable x = new Variable();
Variable y = new Variable();

// Create the Function using DualNumberFunction.
Function f = DualNumberFunction.Create(
    delegate(IDualNumberTransform transform)
        // When this delegate is called a DualNumber is assigned to represent each Variable.
        DualNumber x0 = transform[x];
        DualNumber y0 = transform[y];

        // Compute the actual function using DualNumber. In this case the Rosenbrock function.
        return DualNumber.Sqr(1.0 - x0) + 100.0 * DualNumber.Sqr(y0 - DualNumber.Sqr(x0));
    }, x, y);

// Now just the usual procedure to start the optimizer.
IpoptOptimizer o = new IpoptOptimizer();
o.Variables.Add(x, y);
o.ObjectiveFunction = f;
o.Run(x | 0.5, y | 0.3);

Multi-core settings

There is one problem associated with the large amount of short-lived objects created by DualNumber, though, and this manifests itself when doing parallel computations in multiple threads. Each object creation (and memory allocation) requires obtaining a lock internally in .NET, and this has shown to cause the CPU utilization to drop to around 50% for 12 cores; the other 50% of the time the threads are waiting for obtaining this lock. One solution to this issue is to perform the computations in separate processes with their own virtual memory space and only synchronize the final value of the function.

Last edited Aug 11, 2011 at 7:17 PM by bakkedal, version 13


No comments yet.