最小化带有元组列表作为参数的函数

Question

我需要最小化一个函数 objective()，这个函数的参数是一个元组的列表 x。

但是有个限制：这些元组只能从一个预先定义好的元组集合中选择。

一个简单的例子是：

import numpy as np
from scipy.optimize import minimize

initial_guess = [(2.,0.6), (0.9,8.1)]
possible_values = [(0.,0.), (1.7,2.2), (10.,1.2), (0.,0.15), (4.1,6.2)]

def objective(x:list):
    return np.sum([item[0]**2 + item[1]**2 for item in x])

# Need to add a constraint to select elements of x in elements of possible_values

# Minimize objective function
result = minimize(fun = objective,
                  x0 = initial_guess)

print(result.x)

这段代码会产生以下错误：

ValueError: 'x0' must only have one dimension.

谢谢

Answer 1

你可以只保留在 possible_values 中出现的那些元组，放在 x 里：

def objective(x: list):
    x = [t for t in x if t in possible_values]
    return np.sum([item[0]**2 + item[1]**2 for item in x])

Answer 2

如果你想找到一个元组，使得它的向量范数最小，使用scipy.optimize.minimize这个工具可能不是最合适的选择。要有效解决这种问题，关键是要使用二进制决策变量。这会把你的任务转变成一个混合整数规划问题，这时候选择 milp 就是正确的做法：

import numpy as np
from scipy.optimize import milp, LinearConstraint, Bounds

possible_values = [(0.,0.), (1.7,2.2), (10.,1.2), (0.,0.15), (4.1,6.2)]

c = np.array([v[0]**2 + v[1]**2 for v in possible_values])

A_eq = np.ones((1, len(possible_values)))
b_eq = np.array([1])
constraints = LinearConstraint(A=A_eq, lb=b_eq, ub=b_eq)
bounds = Bounds(lb=np.zeros(len(possible_values)), ub=np.ones(len(possible_values)))
integrality = np.ones(len(possible_values))

res = milp(c, integrality=integrality, constraints=constraints, bounds=bounds)