3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Are there any guarantee of differentiability? $\endgroup$ Commented Apr 9, 2018 at 20:16
  • $\begingroup$ Often you can figure out the spline exactly. It helps to know (or guess) how many knots it has and where they are located. Non-negativity is of little help. This is a very amenable problem in one variable, but quickly becomes more complicated and difficult in higher dimensions. $\endgroup$
    – whuber
    Commented May 13, 2022 at 18:55

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Commented May 13, 2022 at 18:56
  • $\begingroup$ 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. $\endgroup$
    – Ben
    Commented May 13, 2022 at 22:58
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Commented May 14, 2022 at 14:37
0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ The intervals are not known. Will that cause a problem? $\endgroup$ Commented Sep 11, 2018 at 5:09
  • $\begingroup$ if the knowledge about the intervals is not given, then it cannot be exploited and we should just deal with a one-dimensional black-box problem $\endgroup$ Commented Sep 11, 2018 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.