[Math] Minimum of sum of increasing and decreasing function

optimizationreal-analysis

Suppose we have a function $f(x)$ defined for integer $x$ in some bounded interval, which is positive and increasing
$$f(x+1)\geq f(x)\\
f(x)>0$$
, and a function g(x) which is positive and decreasing in the same interval
$$g(x+1)\leq g(x)\\
g(x)>0$$

Now consider the sum of these functions $h(x)=f(x)+g(x)$. We are interested in the global minimum of $h(x)$. Can the properties of these functions be exploited to speed up the search for this minimum, relative to the naive "just try every point in the interval"-approach?

An example of a property that might, possibly, be useful is this:$$ \text{min}_{x\in[A,B]}( h(x)) \geq f(A)+g(B)$$

Best Answer

As far as I can tell, the only thing you can do is use a current candidate for the minimum, say $y$, and then guarantee that the global minimum, if it is not $y$, must occur in the region $f(x) < y$ and $g(x) < y$ since your functions are positive. So you can restrict the region of your search.