Cómo minimizar una función con valores de variable discretos en scipy

Estoy tratando de optimizar una función de destino que tiene múltiples variables de entrada (entre 24 y 30). Estas variables son muestras de tres variables estadísticas diferentes, y los valores de la función objective son valores de probabilidad de prueba t. Una función de error representa el error (sum de cuadrados de diferencias) entre las probabilidades de prueba t deseadas y las reales. Solo puedo aceptar soluciones en las que el error sea inferior a 1e-8, para las tres pruebas t.

Estaba usando scipy.optimize.fmin y funcionó muy bien. Hay muchas soluciones donde la función de destino se convirtió en cero.

El problema es que necesito encontrar una solución donde las variables estén entre 0 y 10.0, y sean números enteros o no tengan una parte fraccionaria de más de un dígito. Ejemplos de valores válidos son 0 10 3 5.5 6.8 . Ejemplos de valores inválidos: -3 2.23 30 o 0.16666667 .

Me he dado cuenta de que hay al menos una solución, porque los valores objective provienen de datos medidos reales. Los datos originales se perdieron, y mi tarea es encontrarlos. Pero no sé cómo. El uso de prueba / error no es una opción, porque hay alrededor de 100 valores posibles para cada variable, y dado el número de variables, el número de casos posibles sería 100 ** 30, que es demasiado. Usar fmin es genial, sin embargo, no funciona con valores discretos.

¿Hay una manera de resolver esto? No es un problema si necesito ejecutar un progtwig durante muchas horas para encontrar una solución. Pero necesito encontrar soluciones para unos 10 valores objective en unos pocos días, y no tengo nuevas ideas.

Aquí hay un ejemplo de 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)5: print "!!!!!!!!!!!! GIVING UP !!!!!!!!!!!" break if __name__ == "__main__": main() 

Lo que está intentando hacer (si entendí su configuración) se llama progtwigción de enteros y es NP-hard; http://en.wikipedia.org/wiki/Integer_programming . Me doy cuenta de que no está buscando soluciones de enteros, pero si multiplica todas sus entradas por 10 y divide su función de destino por 100, obtiene un problema equivalente en el que las entradas son todas enteras. El punto es, sus entradas son discretas.

La función de destino con la que está trabajando es una función cuadrática convexa, y hay buenos algoritmos de optimización restringida que lo resolverán rápidamente para entradas de valor real en el intervalo [0, 10]. A partir de esto, puede intentar redondear o verificar todos los puntos aceptables cercanos, pero hay 2 ^ n de ellos, donde n es el número de entradas. Incluso si haces esto, no se garantiza que la solución óptima sea uno de estos puntos.

Existen algoritmos de aproximación para problemas de progtwigción de enteros y es posible que a veces uno de ellos funcione lo suficientemente bien como para llegar a un punto óptimo. Hay una lista de cosas que podrías probar en el artículo de Wikipedia que cité, pero no sé si estarás contento tratando de resolver este problema.