0

我想最小化以下功能：

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。

有没有办法实现这个？

4

1 回答 1

2

不，这通常是不可能的。

答： 这些约束就像析取或基数约束一样，是导致优化问题 NP-hard 的典型事物。

B： scipy.minimize 中的求解器基于一些强有力的假设，并通过设计提供多项式时间的局部最优。您忽略的核心假设是：

  • 约束+目标是两次可微的
    • 简单的规则：如果你在你的 obj/constraints 中使用 if-else 的东西，它可能不是两倍的差异！

A和B结合起来应该清楚地表明你有点迷失了。

另请参阅斯坦福大学关于凸基数问题的相关介绍，其中概述了该问题。（请记住，这个主题更笼统，仅与您的问题有关；对于您的示例，对问题的析取观点更专业！）

要么放弃精确性/寻求近似值，然后像机器学习和 co 中那样做那些 l1-norm 技巧（参见lasso -optimization）。调整 = 超参数选择并非易事（并且在 scipy 中实现也很烦人 -> 记住 => 两次差异 => 你不能使用np.linalg.norm(x, 1)但需要重新制定，这也使得问题对于求解器来说更加复杂在 scipy 内）

或者您放弃多项式时间算法并进行混合整数数学优化。这不是 scipy 的一部分。

候选方法是：

  • 混合整数规划（线性）
    • 例如 CoinOR Cbc
  • 各种凸整数规划
    • QP、SOCP、SDP 等。
  • 一般非线性混合整数规划
    • 例如 CoinOR Bonmin（本地）/ Couenne（全球）

我懒得分析你的目标，但前者似乎不在讨论范围内，因为你有非线性部分（平方根）。

于 2020-03-19T14:58:38.297 回答