CODEWITHSUNDEEP
pythonalgorithmoptimizationnumpyscipy
Gabriel
Gabriel

Reputation: 42329

Find global minimum for discrete function

This is what my code looks like when simplified:

# This function returns some value depending on the index (integer)
# with which it is called.
def funct(index):
    value <-- some_process[index]
    # Return value for this index.
    return value

where the indexes allowed are stored in a list:

# List if indexes.
x = [0,1,2,3,...,1000]

I need to find the x index that returns the minimum value for funct. I could just apply a brute force approach and loop through the full x list storing all values in new a list and then simply find the minimum with np.argmin():

list_of_values = []
for indx in x:
    f_x = funct(x)
    list_of_values.append(f_x)

min_value = np.argmin(list_of_values)

I've tried this and it works, but it becomes quite expensive when x has too many elements. I'm looking for a way to optimize this process.

I know that scipy.optimize has some optimization functions to find a global minimum like anneal and basin-hopping but I've failed to correctly apply them to my code.

Can these optimization tools be used when I can only call a function with an integer (the index) or do they require the function to be continuous?

Upvotes: 0

Views: 2408

Answers (1)

mgilson
mgilson

Reputation: 309891

the python builtin min accepts a key function:

min_idx = min(x, key=funct)
min_val = funct(min_idx)

This gives you an O(n) solution implemented about as well as you're going to get in python.

Upvotes: 4

Related Questions