3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Ian
    Feb 16, 2019 at 1:20
  • $\begingroup$ (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$.) $\endgroup$
    – Ian
    Feb 16, 2019 at 1:37
  • $\begingroup$ Can you provide any more information about $g$? That will significantly affect how easy/hard this is $\endgroup$
    – David M.
    Feb 16, 2019 at 2:31
  • $\begingroup$ In my particular case g looks linear on semilog plot so $g(x) \approx \exp(-x)$ $\endgroup$
    – Ilya
    Feb 16, 2019 at 9:00
  • $\begingroup$ @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. $\endgroup$
    – Ilya
    Feb 16, 2019 at 9:36

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .