3

A polynomial spline is a function whose definition domain can be divided into partitions such that the function is a polynomial on each partition. An example of a polynomial spline is

$$ F(x)= \begin{cases} (x-3)^2 & if ~x<3 \\ (x-7)^3 & if ~x>7 \\ 0 & \texttt{ otherwise } \end{cases} $$

Suppose that we have a polynomial spline $F$, but I do not know details about its partitions. In other words, $F$ is a kind of black-box polynomial spline. An additional detail (which may or may not be useful) I know about $F$ is that it is non-negative.

I am looking for an efficient algorithm for finding minima of $F$. My guess is that this is an intractable problem. While there exists many blackbox global optimization algorithms, such as mcmc, genetic algorithms, I am looking for an algorithm that can take advantage our knowledge about the function structure aforementioned. Any idea?

zell
  • 473

2 Answers2

1

It's not entirely clear to me what you do and don't know in your optimisation, but if I understand correctly, you don't even know how many piecewise parts there are to your function. If the number of such parts is arbitrary then that looks like an inherently intractable problem to me. Indeed, we could take a much simpler case of an arbitrary piecewise constant function over unit intervals and it would still be impossible to ensure its minimisation. To see this, suppose we consider a piecewise constant function based on an infinite non-negative sequence $\mathbf{y} = (y_i | i \in \mathbb{Z})$, given by:

$$f(x | \mathbf{y}) = y_i \quad \quad \quad \text{for each } 0 \leqslant x < i.$$

Minimising this function is equivalent to finding the minimum value in the sequence $\mathbf{a}$, and there is no algorithm that can ensure this for an arbitrary sequence. Since the function is known to be non-negative, you can guarantee minimisation only if you find a point where the function is zero --- otherwise you cannot guarantee that you have found a minimum.

Ben
  • 124,856
  • On the contrary, this can be easily solved in many practical circumstances, because typically the polynomial degrees are low (1, 2, or 3 are commonest) and there often aren't many knots. You can find minima, and guarantee that, when you know the degree, the knots, and type of spline. Assuming the intervals between knots have a known nonzero lower bound, I suspect it wouldn't be hard to dispense with knowing the locations or numbers of knots. – whuber May 13 '22 at 18:56
  • Indeed; without knowing the number of piecewise parts, I don't see how the problem could be any simpler than the optimisation in my answer. – Ben May 13 '22 at 22:58
  • If you don't know the number, then the spline can approximate arbitrarily closely any piecewise continuous function: in effect, it's useless to know that it's a spline. But in practice we can almost always place some plausible bounds on the number of knots and the polynomial degree. That makes it possible to reverse-engineer the spline. – whuber May 14 '22 at 14:37
0

You can use Bayesian Optimization (BO) to solve this problem. Since you know that your problem consists of a set of sub-problems, you may additionally exploit that by running individual BO solvers for each interval and allocate more objective function evaluations to the intervals with lower objective function values found so far. You can use Multi-Armed Bandits or approaches for algorithm racing to perform the allocation.

IndieSolver
  • 164