# Optimizing intervals in piecewise function

I am not sure what the relevant tags are (or how to best described the problem).

I have a piecewise function where for a particular interval element there is a known functional form (e.g. for interval #4 there is a particular function) but I need to choose the optimal size for each interval.

Formally I can try to describe it as follows:

$$\underset{\{c_i\}}{\operatorname{arg\,max}}\int_{0}^{1} f(x,\{a_i\},\{b_i\},\{c_i\}) dx$$

Where elements of $$\{a_i\},\{b_i\}$$ are some real numbers (of which there are N in each set) and $$\{c_i\}$$ is constrained in the following way:

$$0\le c_i\le 1,c_i\le c_{i+1},|\{c_i\}|=N$$

(I use $$\le$$ because I could squeeze out/drop some of the intervals). Finally the integrand itself is:

$$f(x,\{a_i\},\{b_i\},\{c_i\}) = \begin{cases} a_0 g(x) + b_0, & \mbox{if } 0 \le x \le c_0 \\ a_1 g(x) + b_1, & \mbox{if } c_0\le x \le c_1 \\ ... \\ a_{N-1} g(x) + b_{N-1}, & \mbox{if } c_{N-1}\le x \le 1 \end{cases}$$

Where $$g(x)$$ is a continuous non-linear (in my particular case monotonic) real function. Notably the resulting $$f(x)$$ is not monotonic and a/b can be either positive or negative (so for some intervals increasing g(x) would yield decreasing f(x)).

How would I go about finding $$c_i$$ (is there an analytical way? numerical way?). Since in my case $$g(x)$$ is determined from data I just do brute force search, but that clearly doesn't scale for large N/not a good idea. I am also ok with a sufficiently good approximate numerical solution (in case this is a hard problem).

Ilya

• It seems that a good first approximation to the quantity being optimized is $\sum_{k=0}^N (a_k g(m_k) + b_k) h_k$ where $m_k$ is the midpoint between $c_{k-1}$ and $c_k$ (by definition $c_{-1}=0,c_N=1$) and $h_k=c_k-c_{k-1}$. That's a reasonably nice function of $c$ for traditional vector optimization (gradient descent, Gauss-Newton, etc.) especially if $g'$ (and for G-N, $g''$) is nice. You can refine once you have a good guess. Or you could just use a "Newton-like" method right from the start, if the objective function isn't too expensive to evaluate a lot of times. – Ian Feb 16 at 1:20
• (I seem to have had a fencepost error of some sort, but I think you understand my meaning, it is just evaluating the integral in question by using the midpoint rule with the partition given by the $c_i$.) – Ian Feb 16 at 1:37
• Can you provide any more information about $g$? That will significantly affect how easy/hard this is – David M. Feb 16 at 2:31
• In my particular case g looks linear on semilog plot so $g(x) \approx \exp(-x)$ – Ilya Feb 16 at 9:00
• @Ian, yeah, I think your approach is the correct solution (numerically). I think g(x) has well behaving derivatives. I am still curious if there is a more analytic approach. – Ilya Feb 16 at 9:36