Chương trình bậc hai (QP) Bộ giải mã chỉ phụ thuộc vào NumPy/SciPy?

Question

Tôi muốn học sinh giải quyết một chương trình bậc hai trong một bài tập mà không cần phải cài đặt thêm phần mềm như cvxopt vv. Có thực thi python có sẵn chỉ phụ thuộc vào NumPy/SciPy không?

Answer 1

tôi chạy qua một giải pháp tốt và muốn nhận được nó ra khỏi đó. Có một triển khai python của LOQO trong bộ công cụ học tập máy ELEFANT ra khỏi NICTA (http://elefant.forge.nicta.com.au như của bài đăng này). Có một cái nhìn tại optimization.intpointsolver. Điều này được mã hóa bởi Alex Smola, và tôi đã sử dụng một phiên bản C của cùng một mã với thành công lớn.

Answer 2

Tôi không quen thuộc với lập trình bậc hai, nhưng tôi nghĩ bạn có thể giải quyết loại vấn đề này chỉ bằng cách sử dụng thuật toán giảm thiểu hạn chế của scipy.optimize. Dưới đây là một ví dụ:

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 

Answer 3

Đây có thể là câu trả lời trễ, nhưng tôi đã tìm thấy CVXOPT - http://cvxopt.org/ - như thư viện python miễn phí thường được sử dụng cho Quadratic Programming. Tuy nhiên, nó không phải là dễ dàng để cài đặt, vì nó đòi hỏi phải cài đặt các phụ thuộc khác.

Answer 4

mystic cung cấp triển khai python tinh khiết của các thuật toán tối ưu hóa phi tuyến/không lồi với chức năng hạn chế nâng cao thường chỉ được tìm thấy trong bộ giải mã QP. mystic thực sự cung cấp các ràng buộc mạnh mẽ hơn so với hầu hết các bộ giải mã QP. Tuy nhiên, nếu bạn đang tìm kiếm tốc độ tối ưu hóa thuật toán, thì sau đây không phải dành cho bạn. mystic không phải là chậm, nhưng nó là python tinh khiết như trái ngược với python bindings để C. Nếu bạn đang tìm kiếm tính linh hoạt và chức năng hạn chế QP trong một giải quyết phi tuyến, sau đó bạn có thể quan tâm.

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

Những điều cần lưu ý là mystic quát có thể áp dụng LP, QP, và bình đẳng bậc cao và những hạn chế bất bình đẳng đối với bất kỳ ưu nhất định, không chỉ là một QP giải đặc biệt. Thứ hai, mystic có thể tiêu hóa toán học biểu tượng, do đó, dễ dàng xác định/nhập các ràng buộc là một chút đẹp hơn làm việc với các ma trận và các dẫn xuất của các hàm. mystic tùy thuộc vào numpy và sẽ sử dụng scipy nếu được cài đặt (tuy nhiên, không yêu cầu scipy). mystic sử dụng sympy để xử lý các ràng buộc tượng trưng, ​​nhưng cũng không cần thiết cho việc tối ưu hóa nói chung.

Output:

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

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

Nhận mystic đây: https://github.com/uqfoundation