Vraag Quadratic Program (QP) Oplosser die alleen afhankelijk is van NumPy / SciPy?


Ik wil graag dat studenten een kwadratisch programma in een opdracht oplossen zonder dat ze extra software zoals cvxopt moeten installeren. Is er een python-implementatie beschikbaar die alleen afhankelijk is van NumPy / SciPy?


27
2018-06-09 12:50


oorsprong


antwoorden:


Ik kwam een ​​goede oplossing tegen en wilde hem daar weg krijgen. Er is een python-implementatie van LOQO in de ELEFANT machine learning toolkit uit NICTA (http://elefant.forge.nicta.com.au vanaf dit bericht). Kijk eens naar optimalization.intpointsolver. Dit werd gecodeerd door Alex Smola en ik heb met veel succes een C-versie van dezelfde code gebruikt.


5
2017-11-04 14:37



Ik ben niet erg bekend met kwadratische programmering, maar ik denk dat je dit soort probleem alleen maar kunt oplossen scipy.optimizede beperkte minimaliseringsalgoritmen. Hier is een voorbeeld:

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')

Output:

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

enter image description here


32
2018-06-10 14:12



Dit is misschien een laat antwoord, maar ik heb het gevonden CVXOPT - http://cvxopt.org/ - zoals de veelgebruikte gratis python-bibliotheek voor Quadratic Programming. Het is echter niet gemakkelijk te installeren, omdat het de installatie van andere afhankelijkheden vereist.


9
2018-02-19 15:59



mystic biedt een pure python-implementatie van niet-lineaire / niet-convexe optimalisatie-algoritmen met geavanceerde beperkingen functionaliteit die meestal alleen wordt aangetroffen in QP-oplossers. mystic biedt eigenlijk meer robuuste beperkingen dan de meeste QP-oplossers. Als u echter op zoek bent naar optimaliseringsalgoritmische snelheid, dan is het volgende niet voor u. mystic is niet traag, maar het is pure python in tegenstelling tot python-bindingen naar C. Als je op zoek bent naar flexibiliteit en QP-beperkingen in een niet-lineaire oplosser, dan ben je misschien geïnteresseerd.

"""
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])

Dingen om op te merken is dat mystic kan generiek LP-, QP- en hogere-orde-gelijkheids- en ongelijkheidsbeperkingen toepassen op een bepaalde optimalisatieprogramma, niet alleen op een speciale QP-oplosser. Ten tweede, mystic kan symbolische wiskunde verwerken, dus het gemak van definiëren / invoeren van de beperkingen is een beetje leuker dan werken met de matrices en afgeleiden van functies. mystic hangt af van numpy, en zal gebruiken scipy als het is geïnstalleerd (echter, scipy is niet nodig). mystic maakt gebruik van sympy om symbolische beperkingen aan te kunnen, maar het is ook niet vereist voor optimalisatie in het algemeen.

Output:

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

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

Krijgen mystic hier: https://github.com/uqfoundation


3
2017-10-02 11:33