Scipy 最小化约束：两个值之一需要为零

Question

我想最小化以下函数:

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。

有办法实现吗？

Answer 1

没有。这在一般情况下是不可能的。

答：这些约束就像析取或基数约束，是使优化问题变得 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 因为你有非线性部分（平方根）。

Scipy 最小化约束：两个值之一需要为零

Scipy minimize constraint: One of two values needs to be zero

python

python-3.x

scipy

scipy-optimize-minimize