क्वाड्रैटिक प्रोग्राम (क्यूपी) सॉल्वर जो केवल न्यूप्पी/साइपी पर निर्भर करता है?

Question

मैं चाहता हूं कि छात्रों को एक असाइनमेंट में एक वर्गबद्ध कार्यक्रम को हल करने के बिना उन्हें सीवीएक्सओपी आदि जैसे अतिरिक्त सॉफ़्टवेयर इंस्टॉल करना पड़े। क्या कोई पाइथन कार्यान्वयन उपलब्ध है जो केवल न्यूप्पी/साइपी पर निर्भर करता है?

Answer 1

मैं एक अच्छा समाधान भर में भाग गया और वहाँ यह पता प्राप्त करना चाहता था। इस पोस्टिंग के रूप में एनआईसीटीए (http://elefant.forge.nicta.com.au) से ELEFANT मशीन लर्निंग टूलकिट में LOQO का एक अजगर कार्यान्वयन है। Optimization.intpointsolver पर एक नज़र डालें। यह एलेक्स स्मोला द्वारा कोडित किया गया था, और मैंने बड़ी सफलता के साथ एक ही कोड के सी-संस्करण का उपयोग किया है।

Answer 2

मैं वर्गबद्ध प्रोग्रामिंग से बहुत परिचित नहीं हूं, लेकिन मुझे लगता है कि आप scipy.optimize के सीमित न्यूनतमकरण एल्गोरिदम का उपयोग करके इस तरह की समस्या को हल कर सकते हैं। यहाँ एक उदाहरण है:

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

आउटपुट:

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

यह देर से उत्तर हो सकता है, लेकिन मुझे CVXOPT - http://cvxopt.org/ - Quadratic Programming के लिए आमतौर पर उपयोग की जाने वाली मुफ्त पायथन लाइब्रेरी के रूप में मिला। हालांकि, इसे स्थापित करना आसान नहीं है, क्योंकि इसे अन्य निर्भरताओं की स्थापना की आवश्यकता है।

Answer 4

mystic उन्नत बाधा कार्यक्षमता के साथ गैरलाइनर/गैर-उत्तल अनुकूलन एल्गोरिदम का शुद्ध पायथन कार्यान्वयन प्रदान करता है जो आम तौर पर केवल क्यूपी हलकों में पाया जाता है। mystic वास्तव में अधिकांश क्यूपी हलकों की तुलना में अधिक मजबूत बाधा प्रदान करता है। हालांकि, अगर आप अनुकूलन एल्गोरिदमिक गति की तलाश में हैं, तो निम्नलिखित आपके लिए नहीं है। mystic धीमा नहीं है, लेकिन यह पाइथन बाइंडिंग के विपरीत शुद्ध पायथन है। यदि आप एक गैरलाइन सॉल्वर में लचीलापन और क्यूपी बाधाओं की कार्यक्षमता की तलाश में हैं, तो आपको रुचि हो सकती है।

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

बातें ध्यान दें कि mystic सामान्य रूप से किसी भी अनुकूलक, न सिर्फ एक विशेष QP solver के लिए एल.पी., QP, और उच्च आदेश समानता और असमानता की कमी लागू कर सकते हैं। दूसरा, mystic प्रतीकात्मक गणित को पच सकता है, इसलिए बाधाओं को परिभाषित करने/दर्ज करने में आसानी मैट्रिस और कार्यों के डेरिवेटिव के साथ काम करने से थोड़ा बेहतर है। mysticnumpy पर निर्भर करता है, और यदि यह स्थापित है तो scipy का उपयोग करेगा (हालांकि, scipy आवश्यक नहीं है)। mystic प्रतीकात्मक बाधाओं को संभालने के लिए sympy का उपयोग करता है, लेकिन यह सामान्य रूप से अनुकूलन के लिए भी आवश्यक नहीं है।

आउटपुट:

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

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

यहाँ mystic प्राप्त करें: https://github.com/uqfoundation