SciPy оптимизировать linprog с более сложной функцией

Question

Я пытаюсь оптимизировать функцию в виде:

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

коэффициентов в функции всегда 1, но есть условия для значений х _я, например

х - х < = 7 и х - х < = 4 и т.д ..

Я использую scipy.optimize.linprog, но это может решить только функции в виде:

a_0*x_0 + a_1*x_1 + .. + a_n*x_n 

Есть ли способ использовать scipy.optimize.linprog для первая функция?

Answer 1

Проблема:

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

может быть превращена в проблему:

Minimize 1*y_0 + 1*y_1 + ... + 1*y_n 
s.t.  x_2 - x3 <= 7 
     -y_i <= x_i <= y_i // for i in n 

Здесь мы ввели новые переменные 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