CODEWITHSUNDEEP
algorithmmathmathematical-optimization
Colonel Panic
Colonel Panic

Reputation: 137594

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

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:

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.

Upvotes: 1

Views: 625

Answers (3)

Colonel Panic
Colonel Panic

Reputation: 137594

This also works. Use binary search on the derivative to maximise f' <= 0 

def minimise_convex(f):
    """Given a U-shaped (convex and eventually increasing) function f, find its minimum over the non-negative integers. That is m such that f(m) <= f(n) for all n. If there exist multiple solutions, return the largest. Uses binary search on the derivative."""
    f_prime = lambda n: (f(n) - f(n-1)) if n > 0 else 0
    return binary_search(f_prime, 0)

Where binary search is defined

def binary_search(f, t):
    """Given an increasing function f, find the greatest non-negative integer n such that f(n) <= t. If f(n) > t for all n, return None."""

Upvotes: 0

user1196549
user1196549

Reputation:

If your function is known to be unimodal, use Fibonacci search. http://en.wikipedia.org/wiki/Fibonacci_search_technique

For a discrete domain, the way to decide where new "test points" are probed must be slightly adapted as the formulas for the continuous domain don't yield integers. Anyway the working principle remains.

As regards the number of tests required, we have the following hierarchy:

#Fibonacci < #Golden < #Ternary < #Dichotomic

Upvotes: 0

Aseem Goyal
Aseem Goyal

Reputation: 2723

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

Upvotes: 2

Related Questions