Scipy 最小化，如何获取一个 int 值数组作为输出

Question

我有这样的数据:

import random
data=random.sample(range(1, 100), 5)
x= [-1,1,1,-1,1]

def f(x,data):
        prod=[a * b for a, b in zip(data, x)]
        result=abs(sum(prod))
        return result

我想找到最好的由-1或1组成的x来最小化f(x)的值

也许我们可以使用 scipy.minimise() 但我们如何添加 -1 或 1 作为对 x 内部值的约束？有人有想法吗？

Answer 1

是的，您可以使用 scipy.optimize.minimize:

from scipy.optimize import minimize
minimize(f, [0] * len(data), args=data, bounds=[(-1, 1)] * len(data))

此调用最小化了您在原始 post 中定义的 f。它传递一个零数组作为最小化问题的初始猜测。 f 需要的参数是 'data'，它由参数 'args' 指定。您想要的约束由参数 'bounds' 指定为具有输入数据长度的 min/max 元组列表。

Answer 2

您想求解混合整数线性规划问题 (MILP)，scipy.optimize 尚不支持。

但是，您可以使用像 PuLP 这样的建模包来制定 MILP 并将其传递给 MILP 求解器。请注意，您的 MIP 可以表示为

(P)

min   |f(x)| = |d_0 * x_0 + ... + d_n * x_n|
s.t. x_i ∈ {-1, 1}  ∀ i = 0,...,n

与

相同

(P')

min   |f(x)| = |d_0 * (2*x_0 - 1) + ... + d_n * (2*x_n - 1)|
s.t. x_i ∈ {0, 1}  ∀ i = 0,...,n

并且可以这样实现

min abs_obj
s.t. f(x) <= abs_obj
     f(x) >= -1.0*abs_obj
     x_i   ∈ {0, 1}  ∀ i = 0,...,n

在代码中：

import pulp
import random

data = random.sample(range(1, 100), 5)

# pulp model
mdl = pulp.LpProblem("our_model", sense=pulp.LpMinimize)

# the binary variables x
x = pulp.LpVariable.dicts("x", range(5), cat="Binary")
# the variable that stores the absolute value of the objective
abs_obj = pulp.LpVariable("abs_obj")

# set the MIP objective
mdl += abs_obj

# Define the objective: |f(x)| = abs_obj
mdl += pulp.lpSum((2 * x[i] - 1) * data[i] for i in range(5)) <= abs_obj
mdl += pulp.lpSum((2 * x[i] - 1) * data[i] for i in range(5)) >= -1.0*abs_obj

# solve the problem
mdl.solve()

# your solution
signs = [1 if var.varValue > 0 else -1 for var in x.values()]

或者，如果您不想使用其他包，可以使用 scipy.optimize.minimize 并实施一个简单的惩罚方法。从而你通过解决惩罚问题

解决了问题（P'）

min |f(x)| + Ɛ * (x_0 * (1 - x_0) + ... + x_n * (1 - x_n))
with 0 <= x_i <= 1

其中 Ɛ 是给定的惩罚参数。这里的想法是，对于整数解，正确的惩罚项等于零。

请注意，视情况而定，您可能需要解决一系列惩罚问题才能收敛到整数解。因此，我强烈建议坚持使用 MILP 求解器，而不是自己实施惩罚方法。

Scipy 最小化，如何获取一个 int 值数组作为输出

Scipy minimise, How to get an int value array as an output

python

minimize

scipy