python - multiplicar - scipy documentation

¿Solver del Programa Cuadrático(QP) que solo depende de NumPy/SciPy?

Question

Me gustaría que los estudiantes resuelvan un programa cuadrático en una tarea sin que tengan que instalar un software adicional como cvxopt, etc. ¿Hay alguna implementación de Python disponible que solo dependa de NumPy / SciPy?

Answer 1

Encontré una buena solución y quería sacarla. Hay una implementación python de LOQO en el kit de herramientas de aprendizaje automático ELEFANT de NICTA ( http://elefant.forge.nicta.com.au a partir de esta publicación). Eche un vistazo a optimization.intpointsolver. Esto fue codificado por Alex Smola, y he usado una versión C del mismo código con gran éxito.

Answer 2

No estoy muy familiarizado con la programación cuadrática, pero creo que puedes resolver este tipo de problema simplemente usando los algoritmos de minimización restringida de scipy.optimize . Aquí hay un ejemplo:

import numpy as np
from scipy import optimize
from matplotlib import pyplot as plt
from mpl_toolkits.mplot3d.axes3d import Axes3D

# minimize
#     F = x[1]^2 + 4x[2]^2 -32x[2] + 64

# subject to:
#      x[1] + x[2] <= 7
#     -x[1] + 2x[2] <= 4
#      x[1] >= 0
#      x[2] >= 0
#      x[2] <= 4

# in matrix notation:
#     F = (1/2)*x.T*H*x + c*x + c0

# subject to:
#     Ax <= b

# where:
#     H = [[2, 0],
#          [0, 8]]

#     c = [0, -32]

#     c0 = 64

#     A = [[ 1, 1],
#          [-1, 2],
#          [-1, 0],
#          [0, -1],
#          [0,  1]]

#     b = [7,4,0,0,4]

H = np.array([[2., 0.],
              [0., 8.]])

c = np.array([0, -32])

c0 = 64

A = np.array([[ 1., 1.],
              [-1., 2.],
              [-1., 0.],
              [0., -1.],
              [0.,  1.]])

b = np.array([7., 4., 0., 0., 4.])

x0 = np.random.randn(2)

def loss(x, sign=1.):
    return sign * (0.5 * np.dot(x.T, np.dot(H, x))+ np.dot(c, x) + c0)

def jac(x, sign=1.):
    return sign * (np.dot(x.T, H) + c)

cons = {''type'':''ineq'',
        ''fun'':lambda x: b - np.dot(A,x),
        ''jac'':lambda x: -A}

opt = {''disp'':False}

def solve():

    res_cons = optimize.minimize(loss, x0, jac=jac,constraints=cons,
                                 method=''SLSQP'', options=opt)

    res_uncons = optimize.minimize(loss, x0, jac=jac, method=''SLSQP'',
                                   options=opt)

    print ''/nConstrained:''
    print res_cons

    print ''/nUnconstrained:''
    print res_uncons

    x1, x2 = res_cons[''x'']
    f = res_cons[''fun'']

    x1_unc, x2_unc = res_uncons[''x'']
    f_unc = res_uncons[''fun'']

    # plotting
    xgrid = np.mgrid[-2:4:0.1, 1.5:5.5:0.1]
    xvec = xgrid.reshape(2, -1).T
    F = np.vstack([loss(xi) for xi in xvec]).reshape(xgrid.shape[1:])

    ax = plt.axes(projection=''3d'')
    ax.hold(True)
    ax.plot_surface(xgrid[0], xgrid[1], F, rstride=1, cstride=1,
                    cmap=plt.cm.jet, shade=True, alpha=0.9, linewidth=0)
    ax.plot3D([x1], [x2], [f], ''og'', mec=''w'', label=''Constrained minimum'')
    ax.plot3D([x1_unc], [x2_unc], [f_unc], ''oy'', mec=''w'',
              label=''Unconstrained minimum'')
    ax.legend(fancybox=True, numpoints=1)
    ax.set_xlabel(''x1'')
    ax.set_ylabel(''x2'')
    ax.set_zlabel(''F'')

Salida:

Constrained:
  status: 0
 success: True
    njev: 4
    nfev: 4
     fun: 7.9999999999997584
       x: array([ 2.,  3.])
 message: ''Optimization terminated successfully.''
     jac: array([ 4., -8.,  0.])
     nit: 4

Unconstrained:
  status: 0
 success: True
    njev: 3
    nfev: 5
     fun: 0.0
       x: array([ -2.66453526e-15,   4.00000000e+00])
 message: ''Optimization terminated successfully.''
     jac: array([ -5.32907052e-15,  -3.55271368e-15,   0.00000000e+00])
     nit: 3

Answer 3

mystic proporciona una implementación pura de python de algoritmos de optimización no lineales / no convexos con funcionalidad de restricciones avanzadas que normalmente solo se encuentra en los solucionadores de QP. mystic realmente proporciona restricciones más robustas que la mayoría de los solucionadores de QP. Sin embargo, si está buscando la velocidad algorítmica de optimización, lo siguiente no es para usted. mystic no es lento, pero es puro python en oposición a los enlaces de python a C. Si está buscando flexibilidad y funcionalidad de restricciones QP en un solucionador no lineal, entonces podría estar interesado.

"""
Maximize: f = 2*x[0]*x[1] + 2*x[0] - x[0]**2 - 2*x[1]**2

Subject to: -2*x[0] + 2*x[1] <= -2
             2*x[0] - 4*x[1] <= 0
               x[0]**3 -x[1] == 0

where: 0 <= x[0] <= inf
       1 <= x[1] <= inf
"""
import numpy as np
import mystic.symbolic as ms
import mystic.solvers as my
import mystic.math as mm

# generate constraints and penalty for a nonlinear system of equations 
ieqn = ''''''
   -2*x0 + 2*x1 <= -2
    2*x0 - 4*x1 <= 0''''''
eqn = ''''''
     x0**3 - x1 == 0''''''
cons = ms.generate_constraint(ms.generate_solvers(ms.simplify(eqn,target=''x1'')))
pens = ms.generate_penalty(ms.generate_conditions(ieqn), k=1e3)
bounds = [(0., None), (1., None)]

# get the objective
def objective(x, sign=1):
  x = np.asarray(x)
  return sign * (2*x[0]*x[1] + 2*x[0] - x[0]**2 - 2*x[1]**2)

# solve    
x0 = np.random.rand(2)
sol = my.fmin_powell(objective, x0, constraint=cons, penalty=pens, disp=True,
                     bounds=bounds, gtol=3, ftol=1e-6, full_output=True,
                     args=(-1,))

print ''x* = %s; f(x*) = %s'' % (sol[0], -sol[1])

Lo que se debe tener en cuenta es que mystic puede aplicar genéricamente LP, QP y restricciones de igualdad y desigualdad de orden superior a cualquier optimizador dado, no solo a un solucionador de QP especial. En segundo lugar, el mystic puede digerir las matemáticas simbólicas, por lo que la facilidad de definir / ingresar las restricciones es un poco más agradable que trabajar con las matrices y derivadas de las funciones. mystic depende de numpy , y usará scipy si está instalado (sin embargo, scipy no es necesario). mystic utiliza sympy para manejar restricciones simbólicas, pero tampoco es necesario para la optimización en general.

Salida:

Optimization terminated successfully.
         Current function value: -2.000000
         Iterations: 3
         Function evaluations: 103

x* = [ 2.  1.]; f(x*) = 2.0

Obtenga mystic aquí: https://github.com/uqfoundation

Answer 4

Esta podría ser una respuesta tardía, pero encontré CVXOPT - http://cvxopt.org/ - como la biblioteca de python gratuita comúnmente utilizada para la Quadratic Programming . Sin embargo, no es fácil de instalar, ya que requiere la instalación de otras dependencias.