using splinter to find minima

[mikevitz]

I am using splinter 3.0 for finding minima in high-dimensional functions (DIM=4,5). Call the function F.

I evaluate F at a grid of points, but I cannot pass a grid to my minimization routine. it needs both first and second derivatives to find the minima, so I must pass a "smooth" function to it. If I have a function that interpolates between the data points, I can pass this function to my routine, but must use an interpolation method that produces a smooth structure. Linear splines won't work, because even first derivatives will not exist at data points. So I use cubic splines. But I have a few questions:

1. I see you have removed radial basis function approximation from the latest release. Is there a plan to restore this? (And maybe you can confirm that the interpolated function using RBFA is smooth?)

I read your conversation here #49 on the curse of dimensionality (I am sadly familiar with it). With regard to that conversation, I thought that it should be possible to evaluate the splines locally by knowing the function at the nearest points, and estimating the derivative using the next-to-nearest points. In other words, I don't understand why we need explicit knowledge of derivatives to evaluate locally. Can't we just use the points?

2. It is not clear to me that I need the "global" cubic spline method used by splinter, perhaps you can point to some libraries using local interpolation?

3. Is there a plan to introduce a local method? If it were much faster and allows to use more points in my grid, then it is a great feature...

My issue is that evaluating F is too expensive to pass directly to my minimization--the routine could evaluate F many millions of times, and each time could be minutes. But I have access to massive parallel batch-systems. So I could evaluate F in parallel easily 10^7 times in a couple of days, and form a grid from it, and interpolate between the points. Clearly 10^7 data points in 4-DIM will not work with splinter! :)

My basic goal is to try to speed up the interpolation so that I can use more points in my grid.

Many thanks for your work! I really enjoy this library!

[bgrimstad]

Hi @mikevitz,

The Christmas was quite busy so I forgot to answer you earlier.

1. We have decided to focus on spline approximation in SPLINTER and do not have any plans to reintroduce RBFA. The reason is simply that we lack developers to maintain the library. (Yes, I believe most of the commonly used radial basis functions are smooth, and a sum of smooth functions is smooth.)

2. You do not need to use a global spline interpolation method to optimize F. There are a wealth of optimization methods that work locally on F. Some of these methods are even guaranteed to converge to a global optimum given a sufficiently large number of iterations, under some conditions on F (typically, these methods converge very slowly). Keywords that you can search for is black-box, derivative-free, pattern search, surrogate model, and Bayesian optimization. To find a method that suits your problem, try to answer questions like the following: is F expensive to evaluate, what is the dimension of F's domain, do you need a global solution, can you find a good starting point, is the problem unconstrained, do you need to update F (will it change), will you optimize F more than once, etc. A nice property with surrogate model optimization is that you can separate model building (using spline interpolation, RBFA, or another function approximation method) from the optimization. It may be easier to first focus on sampling and constructing of a good model, before you attempt to optimize. If you do both at once, you should at least try to save the evaluations of F that is done during optimization. As you have pointed out, the curse of dimensionality limits the applicability of these methods. However, the problem persists for all optimization methods that try to optimize a high-dimensional black-box function like F. From what you have written, it sounds like you should focus on the modeling first and perhaps consider using a smarter sampling algorithm. Do you really need the same resolution across the whole domain of F? I have successfully modeled and optimized many 4-D functions using splines built by SPLINTER, so unless you have a particularly exotic function you should be fine using less samples.

3. Unfortunately, we do not have any plans to add a local interpolation method. The reason is again a lack of developers.

Side note: If you are familiar with SQP methods, these actually construct local quadratic functions to approximate F and its derivatives.

Side note 2: For splines built by splinter you can either use a local gradient-descent method (perhaps using multi-start to improve your chances of finding a good optimum) or the global spline solver CENSO. Note that CENSO requires some setup that may be difficult and the documentation is lacking.

Best of luck with you optimization endeavors!

[mikevitz]

Many thanks for the reply! And I hope you had a blessed Christmas season!

I will continue to look into both the my needs as answers to the questions you ask. Since my F is a chisquared of physical functions I can answer mostly:

1. F is expensive...
2. Domain of F is 4-dimensional.
3. I need global but do not anticipate local minima (i.e. I hope it is convex...)
4. I can find a good starting point.
5. F is not updated.

I will also look into CENSO for sure! Thanks again!

P.S. I may post some more issues to understand more the constraints of splinter, like whether the constraint for increasing points is memory-limited or compute-limited or both...