Scipy 最小化约束:两个值之一需要为零
Scipy minimize constraint: One of two values needs to be zero
我想最小化以下函数:
def objective(B, P, O):
return - (sum([(p * o - 1) * b for p, o, b in zip(P, O, B)]) /\
math.sqrt(sum([(1-p) * p * b**2 * o**2 for p, o, b in zip(P, O, B)])))
sol = minimize(objective, x0=bets, args=(P,O,), method='SLSQP', bounds=bnds, constraints=constr)
我想将以下约束添加到 B = [1,2,3,4,5,6,....]
(B 始终具有偶数长度):
对于列表 (1,2)、(3,4)、(5,6)...(b1,b2) 中的每一对,两个值中的一个应该在末尾变为 0优化。
所以从逻辑的角度来看:b1 + b2 = b1 xor b1 + b2 = b2
如果我把它写成约束,它看起来像这样:
def constb(B):
for i in range(0, len(B), 2):
b1, b2 = B[i:i+2]
if b1 == 0.0:
return b2 + b1 - b2
elif b2 == 0.0:
return b1 + b2 - b1
else:
return 42
约束如下所示:
constr = [{'type': 'ineq', 'fun': lambda x: sum(x) - 100},
{'type': 'eq', 'fun': constb}]
但它不起作用,因为我的对最后看起来像这样(每个值的界限是 (0,20)):
20.0 20.0
20.0 20.0
20.0 20.0
20.0 20.0
20.0 20.0
算法似乎默认了 else
语句的约束。我尝试将 B 初始化为 0,但随后出现 MathError,因为不能除以 0。
有办法实现吗?
没有。这在一般情况下是不可能的。
答:
这些约束就像析取或基数约束,是使优化问题变得 NP 难的典型事物。
B:
scipy.minimize 中的求解器基于一些强有力的假设,并通过设计在多项式时间内提供局部最优解。您忽略的核心假设是:
- 约束 + objective 是二次可微的
- 简单规则:如果你在你的 obj/constraints 中使用 if-else 东西,它可能不是两次差异!
A 和 B 结合起来应该清楚,你有点迷路了。
另请参阅斯坦福大学关于 Convex-Cardinality Problems 的相关介绍,其中概述了问题。 (请记住,这个主题更笼统,仅与您的问题 相关 ;对于您的示例,问题的 析取观点 更多专业!)
要么你放弃精确性/寻求近似并像在机器学习和 co 中那样做那些 l1-norm 技巧(参见 lasso-优化)。这对调整超参数选择来说很重要(而且在 scipy 内实现也很烦人 -> 记住 => twice-diff => 你不能使用 np.linalg.norm(x, 1)
但需要重新制定,这也使 scipy)
中的求解器的问题变得更加复杂
或者您放弃多项式时间算法并转向混合整数数学优化。这不是 scipy 的一部分。
那么候选方法是:
- 混合整数规划(线性)
- 例如CoinOR Cbc
- 各种凸整数规划
- QP、SOCP、SDP 和公司
- 一般非线性混合整数规划
- 例如CoinOR Bonmin(本地)/ Couenne(全球)
我懒得分析你的 objective,但似乎前者不在 table 因为你有非线性部分(平方根)。
我想最小化以下函数:
def objective(B, P, O):
return - (sum([(p * o - 1) * b for p, o, b in zip(P, O, B)]) /\
math.sqrt(sum([(1-p) * p * b**2 * o**2 for p, o, b in zip(P, O, B)])))
sol = minimize(objective, x0=bets, args=(P,O,), method='SLSQP', bounds=bnds, constraints=constr)
我想将以下约束添加到 B = [1,2,3,4,5,6,....]
(B 始终具有偶数长度):
对于列表 (1,2)、(3,4)、(5,6)...(b1,b2) 中的每一对,两个值中的一个应该在末尾变为 0优化。
所以从逻辑的角度来看:b1 + b2 = b1 xor b1 + b2 = b2
如果我把它写成约束,它看起来像这样:
def constb(B):
for i in range(0, len(B), 2):
b1, b2 = B[i:i+2]
if b1 == 0.0:
return b2 + b1 - b2
elif b2 == 0.0:
return b1 + b2 - b1
else:
return 42
约束如下所示:
constr = [{'type': 'ineq', 'fun': lambda x: sum(x) - 100},
{'type': 'eq', 'fun': constb}]
但它不起作用,因为我的对最后看起来像这样(每个值的界限是 (0,20)):
20.0 20.0
20.0 20.0
20.0 20.0
20.0 20.0
20.0 20.0
算法似乎默认了 else
语句的约束。我尝试将 B 初始化为 0,但随后出现 MathError,因为不能除以 0。
有办法实现吗?
没有。这在一般情况下是不可能的。
答: 这些约束就像析取或基数约束,是使优化问题变得 NP 难的典型事物。
B: scipy.minimize 中的求解器基于一些强有力的假设,并通过设计在多项式时间内提供局部最优解。您忽略的核心假设是:
- 约束 + objective 是二次可微的
- 简单规则:如果你在你的 obj/constraints 中使用 if-else 东西,它可能不是两次差异!
A 和 B 结合起来应该清楚,你有点迷路了。
另请参阅斯坦福大学关于 Convex-Cardinality Problems 的相关介绍,其中概述了问题。 (请记住,这个主题更笼统,仅与您的问题 相关 ;对于您的示例,问题的 析取观点 更多专业!)
要么你放弃精确性/寻求近似并像在机器学习和 co 中那样做那些 l1-norm 技巧(参见 lasso-优化)。这对调整超参数选择来说很重要(而且在 scipy 内实现也很烦人 -> 记住 => twice-diff => 你不能使用 np.linalg.norm(x, 1)
但需要重新制定,这也使 scipy)
或者您放弃多项式时间算法并转向混合整数数学优化。这不是 scipy 的一部分。
那么候选方法是:
- 混合整数规划(线性)
- 例如CoinOR Cbc
- 各种凸整数规划
- QP、SOCP、SDP 和公司
- 一般非线性混合整数规划
- 例如CoinOR Bonmin(本地)/ Couenne(全球)
我懒得分析你的 objective,但似乎前者不在 table 因为你有非线性部分(平方根)。