具有更复杂函数的Scipy优化linprog

Question

我试图以以下形式优化函数：

1*abs(x_0) + 1*abs(x_1) + .. + 1*abs(x_n)

函数中的系数始终为1，但对于x_i的值，也存在一些条件

x₂-x₃<；=7和x₃-x₄<；=4等。。在

我正在使用scipy.optimize.linprog，但这只能解决以下形式的函数：

^{pr2}$

有没有办法将scipy.optimize.linprog用于第一个函数？在

Answer 1

问题是：

Minimize 1*abs(x_0) + 1*abs(x_1) + ... + 1*abs(x_n))
s.t.     x_2 - x3 <= 7

可以转化为问题：

^{pr2}$

这里我们引入了新的变量y_0, ..., y_n。在

你的一个稍微修改的问题（假设：最小化）如下：

from scipy.optimize import linprog
import numpy as np

N = 5
N_AUX = N

c = np.hstack((np.zeros(N), np.ones(N_AUX))) # objective -> sum of aux-vars

A_orig = [[0, 1, -1, 0, 0, 0, 0, 0, 0, 0],   # orig constraint 1
          [0, 0, 1, -1, 0, 0, 0, 0, 0, 0],   # orig constraint 2
          [-1, -1, 0, 0, 0, 0, 0, 0, 0, 0],  # more interesting problem
          [0, -1, -1, 0, 0, 0, 0, 0, 0, 0]]  # ""   ""          ""

A_aux = [[-1, 0, 0, 0, 0, -1, 0, 0, 0, 0],
         [0, -1, 0, 0, 0, 0, -1, 0, 0, 0],
         [0, 0, -1, 0, 0, 0, 0, -1, 0, 0],
         [0, 0, 0, -1, 0, 0, 0, 0, -1, 0],
         [0, 0, 0, 0, -1, 0, 0, 0, 0, -1],
         [1, 0, 0, 0, 0, -1, 0, 0, 0, 0],
         [0, 1, 0, 0, 0, 0, -1, 0, 0, 0],
         [0, 0, 1, 0, 0, 0, 0, -1, 0, 0],
         [0, 0, 0, 1, 0, 0, 0, 0, -1, 0],
         [0, 0, 0, 0, 1, 0, 0, 0, 0, -1]]

A = np.vstack((A_orig, A_aux))

b = [7, 4, -5, -8] + [0 for i in range(N_AUX*2)]
bnds = [(0, 50) for i in range(N)] + [(None, None) for i in range(N_AUX)] # some custom bounds

res = linprog(c, A_ub=A, b_ub=b, bounds=bnds)

print(res)

#     fun: 8.0
# message: 'Optimization terminated successfully.'
#     nit: 10
#   slack: array([  5.,   1.,   0.,  10.,   6.,   0.,   0.,   0.,   0.,          0.,   0.,
#     0.,  50.,  45.,  47.,  50.,  50.,   0.,   0.])
#  status: 0
# success: True
#       x: array([ 0.,  5.,  3.,  0.,  0.,  0.,  5.,  3.,  0.,  0.])

如果您对安装库有一点了解，我建议您使用cvxpy，它：

• 这种转换是自动进行的（除其他外）
• 支持更好的解决方案（开源和商业化；基于单一和非单一）

同样的例子：

from cvxpy import *

x = Variable(5)
constraints = [x[1] - x[2] <= 7,
               x[2] - x[3] <= 4,
               x[0] + x[1] >= 5,
               x[1] + x[2] >= 8,
               x >= 0,
               x <= 50]
objective = Minimize(sum_entries(abs(x)))
problem = Problem(objective, constraints)
problem.solve()
print(x.value)
print(problem.value)

# [[ -1.56436431e-11]
#  [  5.83767132e+00]
#  [  2.16232868e+00]
#  [  6.53497343e-10]
#  [  7.79511984e-10]]
# 8.00000000102