Back to Community
A Non-Convex Optimization Work Around/Avoiding Local Minima

I made a simple class that runs many optimizations simultaneously over a specified range. This way, only one or two of the optimizations need to stumble into the global minima while the others get lost. Example below.

import pandas as pd  
import numpy as np  
import math  
from scipy import optimize  
import threading  
from threading import Thread  
import random  
import time


class threaded_opt:

    #initializations  
    def __init__(self, function, min_x0, max_x0, num_threads):

        if (len(max_x0) != len(min_x0)):  #Error checking  
            print ("ERROR: max_x0 and min_x0 are not the same length")  
            return  
        self.function = function  
        self.min_x0 = min_x0  
        self.max_x0 = max_x0  
        self.num_threads = num_threads  
        self.lock = threading.Lock()  
        self.best_result = None  
        self.all_results_of_run = []

    #Run the optimization.  Make the threads here.  
    def run(self):  
        self.best_result = optimize.minimize(self.function, self.min_x0)  #Get an initial value to compare in traget_function  
        self.all_results_of_run = []  #Clear the all results list for each run  
        for x in range(self.num_threads):  #Make the threads and start them off  
            t = Thread(target=self.target_function, args=(x,))  
            t.start()

    #Each thread goes through this.  Find a random point in the space given, and optimize from it  
    def target_function(self, thread_ID):

        random_x0 = []  
        for x in range(len(self.max_x0)):  #Generate a random point in the allowed space  
            random_x0.append(random.uniform(self.min_x0[x], self.max_x0[x]))  
        result = optimize.minimize(self.function, random_x0)  #Optimize from that point  
        with self.lock:  #So the threads don't interfere with eachother  
            self.all_results_of_run.append(result)  
            if (result.fun < self.best_result.fun):  
                self.best_result = result

    #Returns the proportion of optimizations that returned the correct result  
    def score(self):  
        correct = 0  
        for x in self.all_results_of_run:  
            if (x.fun == self.best_result.fun):  
                correct += 1  
        return (float(correct)/self.num_threads)

3 responses

Here, the function being minimized resembles an egg carton that has been bent into a bowl shape. It has an incredible amount of local minima. scipy.optimize.minimze() had a lot of trouble with this one, but this class nails it. The global min is at -8.8...

#An example function to evaluate.  
#It is a 3D graph that resembles and bowl shaped egg carton.  
def evaluate(box):  
    x = box[0]  
    y = box[1]  
    a = 5  
    b = 0.1

            #Egg Carton                     #Paraboloid  
    return (a*(math.sin(x)+math.cos(y))) + (b*((x**2)+(y**2)))


opt = threaded_opt(evaluate,[-1000,-1000],[1000,1000], 1000)  
opt.run()  
print ("The best result is", opt.best_result.fun)  
print ("Only", 100*opt.score(), "percent of the optimizations were correct")  

It outputs:
The best result is -8.813796845199237 Only 0.3 percent of the optimizations were correct

Unfortunately, some of the modules needed aren't yet supported. But I hope someone can use it

EDIT: Picture of function being minimized with code I would've done this in a notebook but the 3D graphing modules are also not supported

Hmm which optimizer is it picking? Couldn't one just use a particle swarm or something if it's not a friendly function?

Simon,
Sorry it took so long. Being new I admittedly had to learn what PSO was. But frankly, yes. I used PySwarm for the particle swarm optimization and it works extremely well. Had I known about it prior I wouldn't have gone through the trouble of making this.