Optimización no lineal restringida de Python

¿Cuál es el paquete recomendado para la optimización no lineal restringida en Python?

El problema específico que estoy tratando de resolver es este:

Tengo un X (Nx1) desconocido, tengo vectores M (Nx1) u y matrices M (NxN).

 max [5th percentile of (ui_T*X), i in 1 to M] st 0<=X<=1 and [95th percentile of (X_T*si*X), i in 1 to M]<= constant 

Cuando comencé el problema, solo tenía una estimación puntual para u y pude resolver el problema anterior con cvxpy .

Me di cuenta de que en lugar de una estimación para u y s , tenía toda la distribución de valores, así que quería cambiar mi función objective para poder usar toda la distribución. La descripción del problema anterior es mi bash de incluir esa información de manera significativa.

    cvxpy no se puede usar para resolver esto, he intentado scipy.optimize.anneal , pero parece que no puedo establecer límites en los valores desconocidos. También he visto pulp pero no permite restricciones no lineales.

    scipy tiene un paquete espectacular para la optimización no lineal restringida.

    Puede comenzar leyendo el documento de optimize , pero aquí hay un ejemplo con SLSQP:

     minimize(func, [-1.0,1.0], args=(-1.0,), jac=func_deriv, constraints=cons, method='SLSQP', options={'disp': True}) 

    Si bien el algoritmo SLSQP en scipy.optimize.minimize es bueno, tiene muchas limitaciones. El primero de ellos es que es un solucionador de QP , por lo que funciona con ecuaciones que encajan bien en un paradigma de progtwigción cuadrática. ¿Pero qué pasa si tienes limitaciones funcionales? Además, scipy.optimize.minimize no es un optimizador global, por lo que a menudo debe comenzar muy cerca de los resultados finales.

    Existe un paquete de optimización no lineal restringido (llamado mystic ) que ha existido durante casi tanto tiempo como scipy.optimize . Lo sugeriría como el lugar para manejar cualquier optimización no lineal restringida general.

    Por ejemplo, su problema, si entiendo su pseudocódigo, se parece a esto:

     import numpy as np M = 10 N = 3 Q = 10 C = 10 # let's be lazy, and generate s and u randomly... s = np.random.randint(-Q,Q, size=(M,N,N)) u = np.random.randint(-Q,Q, size=(M,N)) def percentile(p, x): x = np.sort(x) p = 0.01 * p * len(x) if int(p) != p: return x[int(np.floor(p))] p = int(p) return x[p:p+2].mean() def objective(x, p=5): # inverted objective, to find the max return -1*percentile(p, [np.dot(np.atleast_2d(u[i]), x)[0] for i in range(0,M-1)]) def constraint(x, p=95, v=C): # 95%(xTsx) - v <= 0 x = np.atleast_2d(x) return percentile(p, [np.dot(np.dot(x,s[i]),xT)[0,0] for i in range(0,M-1)]) - v bounds = [(0,1) for i in range(0,N)] 

    Entonces, para manejar su problema en mystic , solo necesita especificar los límites y las restricciones.

     from mystic.penalty import quadratic_inequality @quadratic_inequality(constraint, k=1e4) def penalty(x): return 0.0 from mystic.solvers import diffev2 from mystic.monitors import VerboseMonitor mon = VerboseMonitor(10) result = diffev2(objective, x0=bounds, penalty=penalty, npop=10, gtol=200, \ disp=False, full_output=True, itermon=mon, maxiter=M*N*100) print result[0] print result[1] 

    El resultado se ve algo como esto:

     Generation 0 has Chi-Squared: -0.434718 Generation 10 has Chi-Squared: -1.733787 Generation 20 has Chi-Squared: -1.859787 Generation 30 has Chi-Squared: -1.860533 Generation 40 has Chi-Squared: -1.860533 Generation 50 has Chi-Squared: -1.860533 Generation 60 has Chi-Squared: -1.860533 Generation 70 has Chi-Squared: -1.860533 Generation 80 has Chi-Squared: -1.860533 Generation 90 has Chi-Squared: -1.860533 Generation 100 has Chi-Squared: -1.860533 Generation 110 has Chi-Squared: -1.860533 Generation 120 has Chi-Squared: -1.860533 Generation 130 has Chi-Squared: -1.860533 Generation 140 has Chi-Squared: -1.860533 Generation 150 has Chi-Squared: -1.860533 Generation 160 has Chi-Squared: -1.860533 Generation 170 has Chi-Squared: -1.860533 Generation 180 has Chi-Squared: -1.860533 Generation 190 has Chi-Squared: -1.860533 Generation 200 has Chi-Squared: -1.860533 Generation 210 has Chi-Squared: -1.860533 STOP("ChangeOverGeneration with {'tolerance': 0.005, 'generations': 200}") [-0.17207128 0.73183465 -0.28218955] -1.86053344078 

    mystic es muy flexible y puede manejar cualquier tipo de restricciones (por ejemplo, igualdad, desigualdades), incluidas las restricciones simbólicas y funcionales. Especifiqué las restricciones como "penalizaciones" arriba, que es la forma tradicional, en el sentido de que aplican una penalización al objective cuando se viola la restricción. mystic también proporciona transformaciones no lineales del kernel, que restringen el espacio de la solución al reducir el espacio de las soluciones válidas (es decir, mediante un mapeo espacial o transformación del kernel).

    A modo de ejemplo, aquí hay una solución mystic resolver un problema que rompe muchos de los solucionadores de QP, ya que las restricciones no tienen la forma de una matriz de restricciones. Se está optimizando el diseño de un recipiente a presión.

     "Pressure Vessel Design" def objective(x): x0,x1,x2,x3 = x return 0.6224*x0*x2*x3 + 1.7781*x1*x2**2 + 3.1661*x0**2*x3 + 19.84*x0**2*x2 bounds = [(0,1e6)]*4 # with penalty='penalty' applied, solution is: xs = [0.72759093, 0.35964857, 37.69901188, 240.0] ys = 5804.3762083 from mystic.symbolic import generate_constraint, generate_solvers, simplify from mystic.symbolic import generate_penalty, generate_conditions equations = """ -x0 + 0.0193*x2 <= 0.0 -x1 + 0.00954*x2 <= 0.0 -pi*x2**2*x3 - (4/3.)*pi*x2**3 + 1296000.0 <= 0.0 x3 - 240.0 <= 0.0 """ cf = generate_constraint(generate_solvers(simplify(equations))) pf = generate_penalty(generate_conditions(equations), k=1e12) if __name__ == '__main__': from mystic.solvers import diffev2 from mystic.math import almostEqual from mystic.monitors import VerboseMonitor mon = VerboseMonitor(10) result = diffev2(objective, x0=bounds, bounds=bounds, constraints=cf, penalty=pf, \ npop=40, gtol=50, disp=False, full_output=True, itermon=mon) assert almostEqual(result[0], xs, rel=1e-2) assert almostEqual(result[1], ys, rel=1e-2) 

    Encuentre esto, y aproximadamente 100 ejemplos como este, aquí: https://github.com/uqfoundation/mystic .

    Soy el autor, así que estoy un poco parcial. Sin embargo, el sesgo es muy leve. mystic es a la vez maduro y bien soportado, y no tiene paralelo en su capacidad para resolver problemas de optimización no lineales con restricciones estrictas.

    Como otros también han comentado, el paquete de minimización SciPy es un buen lugar para comenzar. He incluido un ejemplo a continuación (Hock Schittkowski # 71 benchmark) que incluye una función objective, una restricción de igualdad y una restricción de desigualdad.

     import numpy as np from scipy.optimize import minimize def objective(x): return x[0]*x[3]*(x[0]+x[1]+x[2])+x[2] def constraint1(x): return x[0]*x[1]*x[2]*x[3]-25.0 def constraint2(x): sum_eq = 40.0 for i in range(4): sum_eq = sum_eq - x[i]**2 return sum_eq # initial guesses n = 4 x0 = np.zeros(n) x0[0] = 1.0 x0[1] = 5.0 x0[2] = 5.0 x0[3] = 1.0 # show initial objective print('Initial SSE Objective: ' + str(objective(x0))) # optimize b = (1.0,5.0) bnds = (b, b, b, b) con1 = {'type': 'ineq', 'fun': constraint1} con2 = {'type': 'eq', 'fun': constraint2} cons = ([con1,con2]) solution = minimize(objective,x0,method='SLSQP',\ bounds=bnds,constraints=cons) x = solution.x # show final objective print('Final SSE Objective: ' + str(objective(x))) # print solution print('Solution') print('x1 = ' + str(x[0])) print('x2 = ' + str(x[1])) print('x3 = ' + str(x[2])) print('x4 = ' + str(x[3])) 

    También hay un hilo de discusión más completo sobre los solucionadores de progtwigción no lineal para Python si SLSQP no puede resolver su problema. El material de mi curso sobre optimización del diseño de ingeniería está disponible si necesita información adicional sobre los métodos de resolución.

    Por lo general, para la adaptación puede usar scipy.optimize funciones scipy.optimize , o lmfit que simplemente extiende el paquete scipy.optimize para que sea más fácil pasar cosas como límites. Personalmente, me gusta usar kmpfit , parte de la biblioteca kapteyn y se basa en la implementación C de MPFIT.

    scipy.optimize.minimize() es probablemente el más fácil de obtener y se usa comúnmente.