How to minimize a function with discrete variable values ​​in scipy

Question

I am trying to optimize an objective function with multiple input variables (24 to 30). These variables are samples of three different statistical variables, and the values ​​of the objective function are the probabilities of the t-test. The error function is the error (the sum of the squared differences) between the desired and real probabilities of the t-test. I can only make decisions where the error is less than 1e-8, for all three t-tests.

I used scipy.optimize.fmin and it worked perfectly. There are many solutions in which the objective function becomes zero.

The problem is that I need to find a solution in which the variables are in the range from 0 to 10.0, and are integers or do not have more than one fractional part. Examples of valid values ​​are 0 10 3 5.5 6.8 . Examples of invalid values: -3 2.23 30 or 0.16666667 .

I know that there is at least one solution, because the target values ​​come from the actual measured data. The original data was lost, and my task is to find them. But I do not know how to do this. Using trial / error is not an option, because for each variable there are about 100 possible values, and taking into account the number of variables, the number of possible cases will be 100 ** 30, which is too much. Using fmin is fine, however it does not work with discrete values.

Is there any way to solve this? This is not a problem if I need to run the program for many hours to find a solution. But I need to find solutions for about 10 targets in a few days, and I have no new ideas.

Here is an example of MWE:

 import math import numpy import scipy.optimize import scipy.stats import sys def log(s): sys.stdout.write(str(s)) sys.stdout.flush() # List of target T values: TAB, TCA, TCB TARGETS = numpy.array([ [0.05456834, 0.01510358, 0.15223353 ], # task 1 to solve [0.15891875, 0.0083665, 0.00040262 ], # task 2 to solve ]) MAX_ERR = 1e-10 # Maximum error in T values NMIN,NMAX = 8,10 # Number of samples for T probes. Inclusive. def fsq(x, t, n): """Returns the differences between the target and the actual values.""" a,b,c = x[0:n],x[n:2*n],x[2*n:3*n] results = numpy.array([ scipy.stats.ttest_rel(a,b)[1], # ab scipy.stats.ttest_rel(c,a)[1], # ca scipy.stats.ttest_rel(c,b)[1] # cb ]) # Sum of squares of diffs return (results - t) def f(x, t, n): """This is the target function that needs to be minimized.""" return (fsq(x,t,n)**2).sum() def main(): for tidx,t in enumerate(TARGETS): print "=============================================" print "Target %d/%d"%(tidx+1,len(TARGETS)) for n in range(NMIN,NMAX+1): log(" => n=%s "%n) successful = False tries = 0 factor = 0.1 while not successful: x0 = numpy.random.random(3*n) * factor x = scipy.optimize.fmin(f,x0, [t,n], xtol=MAX_ERR, ftol=MAX_ERR ) diffs = fsq(x,t,n) successful = (numpy.abs(diffs)<MAX_ERR).all() if successful: log(" OK, error=[%s,%s,%s]\n"%(diffs[0],diffs[1],diffs[2])) print " SOLUTION FOUND " print x else: tries += 1 log(" FAILED, tries=%d\n"%tries) print diffs factor += 0.1 if tries>5: print "!!!!!!!!!!!! GIVING UP !!!!!!!!!!!" break if __name__ == "__main__": main() 

Answer 1

What you are trying to do (if I understand your setup) is called whole programming, and it is NP-hard; http://en.wikipedia.org/wiki/Integer_programming . I understand that you are not looking for integer solutions, but if you multiply all your inputs by 10 and divide the objective function by 100, you will get an equivalent problem where the inputs are integer. The fact is that your inputs are discrete.

The objective function you are working with is a convex quadratic function, and there are good bounded optimization algorithms that will quickly solve it for real inputs in the interval [0, 10]. From this, you can try to round up or check all the acceptable points nearby, but there are 2 ^ n of them, where n is the number of inputs. Even if you do, one of these points is not guaranteed to be the optimal solution.

There are approximation algorithms for integer programming problems, and you may find that sometimes one of them works well enough to lead you to the optimal point. There is a list of things you can try in the Wikipedia article I cited, but I don’t know that you will be happy trying to solve this problem.