How to minimise integer function that's known to be U-shaped?

Question

Let f be a function defined on the non-negative integers n ≥ 0. Suppose f is known to be U-shaped (convex and eventually increasing). How to find its minimum? That is, m such that f(m) ≤ f(n) for all n.

Examples of U-shaped functions:

• n**2 - 1000*n + 100
• (1 + 1/2 + ... + 1/n) + 1000/sqrt(1+n)

Of course, a human mathematician can try to minimise these particular functions using calculus. For my computer though, I want a general search algorithm that can minimise any U-shaped function.

---

Those functions again, in Python, to help anyone who wants to test an algorithm.

f = lambda n: n**2 - 1000*n + 100
g = lambda n: sum(1/i for i in range(1,n+1)) + 1000/sqrt(1+n)

Don't necessarily need code (of any language) in an answer, just a description of an algorithm. Would interest me though to see its answers for these specific functions.

Answer 1

You are probably looking for ternary search .
Ternary search will help to find f(m) as your requirement in O(logN) time , where N is number of points on the curve .

It basically takes two points m1 and m2 in range (l,r) and then recursively searches in 1/3 rd part .

code in python (from wikipedia) :

def ternarySearch(f, left, right, absolutePrecision):
    while True:
        #left and right are the current bounds; the maximum is between them
        if abs(right - left) < absolutePrecision:
            return (left + right)/2

        leftThird = (2*left + right)/3
        rightThird = (left + 2*right)/3

        if f(leftThird) < f(rightThird):
            right = rightThird
        else:
            left = leftThird