I am trying to optimize a function in the form of:
1*abs(x_0) + 1*abs(x_1) + .. + 1*abs(x_n)
Coefficients in the function are always 1, but there are conditions for the values of xi, for example
x2 - x3 <= 7 and x3 - x4 <= 4, etc..
I am using scipy.optimize.linprog, but this can only solve functions in the form of:
a_0*x_0 + a_1*x_1 + .. + a_n*x_n
Is there a way to use scipy.optimize.linprog for the first function?
The problem:
Minimize 1*abs(x_0) + 1*abs(x_1) + ... + 1*abs(x_n))
s.t. x_2 - x3 <= 7
can be converted into the problem:
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
Here we introduced new variables y_0, ..., y_n.
So a slightly modified problem of yours (assumption: minimization) looks like this:
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.])
If you got a bit knowledge on installing libraries, i recommend using cvxpy which:
Same example:
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