Effiecient Repeat Evaluation of Large Multivariable Expressions

Question

I am working with a professor to implement an optimization algorithm for determining the maximum and minimum of large (100+ variable) multi-variable expressions (not restricted to polynomials). Part of this process involves picking random values for all variables and then evaluating the expression for near "neighbors" (slight variations in all sub-sets of the variables).

Simplified Example:

f(x,y,z) = x^2 + sin(y/x)/log2(3z)

1. Start at random point (1,1,1)

2. Test all neighbors by altering each variable by +/- 0.1:

   {1,1,1.1}, {1,1.1,1}, {1, 1.1, 1.1}, {1.1,1,1}, {1.1,1,1.1}, {1.1,1.1,1], ...

Over the course of the optimization the same expression will be evaluated many millions of times. It seems like there must be an efficient way to prevent reevaluating portions of the expression that have already be evaluated, or at least recently evaluated. I am struggling to come up with an efficient way of doing this. I understand that computers are smoking fast at math calculations so maybe attempting this optimization is unwarranted even with large expression size, however expression evaluation is the bottleneck in the process at the moment. Thanks for you time and thoughts on this!

Answer 1

In symbolic computation, hash consing is a technique that consists of systematically remembering the result of function calls in a cache. The cache is indexed by functions and their parameters. Before performing an operation, you look up the call in the cache, and if you find it, you don't perform the function call. Function calls include data constructors, so there is only a single copy of any data structure in memory, and data structures can be compared by physical address. If the computation is highly repetitive, involving many identical parts, this can be a huge performance and memory benefit as it removes any redundancy in computation and memory. If the computation involves little repetition then it's just wasted time doing failed cache lookups and wasted memory for a cache that isn't used.

The same technique can be applied to numerical computations: store all intermediate results in a cache indexed by function calls. I don't know how effective it could be in practice.

As floating point is involved, you need to decide what it means for values to be equal. The most straightforward approach is to use floating point equality; assuming consistent compilation, the same mathematical operation on the same parameters always yields the same result, but you will miss equalities resulting from obtaining the same result in two different ways that are mathematically equivalent (e.g. you may not get the same result for f(x,y) and f(y,x) even if f is mathematically symmetric).

Answer 2

This is known as continuous optimization or mathematical optimization. There's an enormous literature on this; I suggest you spend some time reading about it.

If you can compute gradients (partial derivatives), you can use "first-order methods", such as gradient descent. If you can't, you can use "gradient-free methods", such as hillclimbing. There are many others -- the best method will depend on the specific nature of your particular instance.

Depending on the structure of the specific objective function you want to minimize, there may be ways to avoid re-computing intermediate values. For instance, stochastic gradient descent is a version of gradient descent that does exactly this, when the objective function can be written as the sum of lots of terms, where each term can be computed efficiently. For instance, TensorFlow is a library that has nice support for this kind of optimization.

Without more detail about your specific problem, it's probably not possible to give a more specific recommendation about which method to use.