¿Cómo encontrar el mínimo global en la optimización de python con límites?

Tengo una función de Python con 64 variables, y traté de optimizarla utilizando el método L-BFGS-B en la función de minimizar, sin embargo, este método tiene una fuerte dependencia de la estimación inicial, y no pude encontrar el mínimo global.

Pero me gustó su capacidad para establecer límites para las variables. ¿Existe una forma / función para encontrar el mínimo global mientras se tienen límites para las variables?

Algunas sugerencias de sentido común para depurar y visualizar cualquier optimizador en su función:

¿Son su función objetiva y sus limitaciones razonables?
Si la función objective es una sum, digamos f() + g() , imprímalos por separado para todas las x en "fx-opt.nptxt" (abajo); si f() es el 99% de la sum y g() 1%, investigue.

Restricciones: ¿cuántos de los componentes x_i en xfinal están bloqueados en los límites, x_i <= lo_i o >= hi_i ?


¿Qué tan irregular es tu función a escala global?
Ejecute con varios puntos de inicio aleatorios y guarde los resultados para analizar / trazar:

 title = "%sn %d ntermhess %d nsample %d seed %d" % ( # all params! __file__, n, ntermhess, nsample, seed ) print title ... np.random.seed(seed) # for reproducible runs np.set_printoptions( threshold=100, edgeitems=10, linewidth=100, formatter = dict( float = lambda x: "%.3g" % x )) # float arrays %.3g lo, hi = bounds.T # vecs of numbers or +- np.inf print "lo:", lo print "hi:", hi fx = [] # accumulate all the final f, x for jsample in range(nsample): # x0 uniformly random in box lo .. hi -- x0 = lo + np.random.uniform( size=n ) * (hi - lo) x, f, d = fmin_l_bfgs_b( func, x0, approx_grad=1, m=ntermhess, factr=factr, pgtol=pgtol ) print "f: %gx: %s x0: %s" % (f, x, x0) fx.append( np.r_[ f, x ]) fx = np.array(fx) # nsample rows, 1 + dim cols np.savetxt( "fx-opt.nptxt", fx, fmt="%8.3g", header=title ) # to analyze / plot ffinal = fx[:,0] xfinal = fx[:,1:] print "final f values, sorted:", np.sort(ffinal) jbest = ffinal.argmin() print "best x:", xfinal[jbest] 

Si algunos de los valores ffinal parecen razonablemente buenos, intente más puntos de inicio aleatorios cerca de esos, eso es seguramente mejor que puro aleatorio.

Si las x s son curvas, o algo real, traza las mejores pocas x0 y xfinal .
(Una regla general es nsample ~ 5 * d o 10 * d en dimensiones d . ¿Demasiado lento, demasiado? Reduzca el valor de maxiter / maxeval , reduzca ftol ; no necesita ftol 1e-6 para realizar una exploración como esta).

Si desea resultados reproducibles, debe enumerar TODOS los parámetros relevantes en el title y en los archivos y gráficos derivados. De lo contrario, te preguntarás "¿De dónde viene esto ?"


¿Qué tan irregular es tu función en la escala de épsilon ~ 10 ^ -6?
Los métodos que se aproximan a un gradiente a veces devuelven su última estimación, pero si no:

 from scipy.optimize._numdiff import approx_derivative # 3-point, much better than ## from scipy.optimize import approx_fprime for eps in [1e-3, 1e-6]: grad = approx_fprime( x, func, epsilon=eps ) print "approx_fprime eps %g: %s" % (eps, grad) 

Sin embargo, si la estimación del gradiente es deficiente / irregular antes de que se cierre el optimizador, no verá eso. Luego tienes que guardar todo el intermedio [f, x, approx_fprime] para verlos también; fácil en python - pregunta si eso no está claro.

En algunas áreas problemáticas, es común realizar una copia de seguridad y reiniciar desde un xmin supuesto. Por ejemplo, si está perdido en un camino rural, primero encuentre un camino principal y luego reinicie desde allí.


Resumen:
no espere que ningún optimizador de caja negra funcione en una función con baches de gran escala, baches de epsilon o ambos.
Invierta en andamios de prueba y en formas de ver qué está haciendo el optimizador.

Muchas gracias por su respuesta detallada, pero como soy bastante nuevo en Python, no sabía cómo implementar el código en mi progtwig, pero aquí estaba mi bash de optimización:

 x0=np.array((10, 13, f*2.5, 0.08, 10, f*1.5, 0.06, 20, 10, 14, f*2.5, 0.08, 10, f*1.75, 0.07, 20, 10, 15, f*2.5, 0.08, 10, f*2, 0.08, 20, 10, 16, f*2.5, 0.08, 10, f*2.25, 0.09, 20, 10, 17, f*2.5, -0.08, 10, f*2.5, -0.06, 20, 10, 18, f*2.5, -0.08, 10, f*2.75,-0.07, 20, 10, 19, f*2.5, -0.08, 10, f*3, -0.08, 20, 10, 20, f*2.5, -0.08, 10, f*3.25,-0.09, 20)) # boundary for each variable, each element in this restricts the corresponding element above bnds=((1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), (1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), ) from scipy.optimize import basinhopping from scipy.optimize import minimize merit=a*meritoflength + b*meritofROC + c*meritofproximity +d*(distancetoceiling+distancetofloor)+e*heightorder minimizer_kwargs = {"method": "L-BFGS-B", "bounds": bnds, "tol":1e0} ret = basinhopping(merit_function, x0, minimizer_kwargs=minimizer_kwargs, niter=10, T=0.01) zoom = ret['x'] res = minimize(merit_function, zoom, method = 'L-BFGS-B', bounds=bnds, tol=1e-5) print res 

la función de mérito combina x0 con algunos otros valores para formar 6 puntos de control para 8 curvas, luego calcula sus longitudes, radios de curvatura, etc. Devuelve el mérito final como combinaciones lineales de esos parámetros con algunos pesos.

basinhopping con precisiones bajas para encontrar algunos mínimos, y luego usé minimize para boost la precisión del munimum más bajo.

ps la plataforma en la que estoy funcionando es Enthoght canopy 1.3.0, numpy 1.8.0 scipy 0.13.2 mac 10.8.3