Finding the global minimum of a nonnegative, black-box, polynomial spline 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?
 A: 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.
A: 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.  
