Я бы хотел, чтобы учащиеся решали квадратичную программу в задании без необходимости установки дополнительного программного обеспечения, такого как cvxopt и т.д. Существует ли реализация python, которая зависит только от NumPy/SciPy?
Квадратичная программа (QP), которая зависит только от NumPy/SciPy?
Ответ 1
Я столкнулся с хорошим решением и хотел получить его там. Существует реализация python LOQO в наборе инструментальных средств машинного обучения ELEFANT из NICTA (http://elefant.forge.nicta.com.au с этой публикации). Посмотрите на optim.intpointsolver. Это было закодировано Алексом Смолой, и я с успехом использовал C-версию того же кода.
Ответ 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
Ответ 3
Это может быть поздний ответ, но я нашел CVXOPT
- http://cvxopt.org/ - как обычно используемую бесплатную библиотеку python для Quadratic Programming
. Однако его нелегко установить, так как требует установки других зависимостей.
Ответ 4
mystic
обеспечивает чистую реализацию на питоне нелинейных/невыпуклых алгоритмов оптимизации с расширенными функциями ограничений, которые обычно встречаются только в решателях QP. mystic
фактически обеспечивает более надежные ограничения, чем большинство решателей QP. Однако, если вы ищете алгоритмическую скорость оптимизации, то следующее не для вас. mystic
не медленный, но чистый python в отличие от привязок python к C. Если вы ищете гибкость и функциональность QP-ограничений в нелинейном решателе, тогда вам может быть интересно.
"""
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
может в общих чертах применять ограничения LP, QP и более высокого порядка и ограничения неравенства для любого заданного оптимизатора, а не только для специального решателя QP. Во-вторых, mystic
может переварить символическую математику, поэтому легкость определения/ввода ограничений немного лучше, чем работа с матрицами и производными функций. mystic
зависит от numpy
и будет использовать 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