如何对两个向量的差使用scipy 'minimize'?

mo49yndu  于 2022-11-10  发布在  其他
关注(0)|答案(2)|浏览(217)

我有两个向量w1w2(每个长度为100),我想最小化它们的绝对差之和,即

import numpy as np

def diff(w: np.ndarray) -> float:
    """Get the sum of absolute differences in the vector w.

    Args:
        w: A flattened vector of length 200, with the first 100 elements
            pertaining to w1, and the last 100 elements pertaining to w2.

    Returns:
        sum of absolute differences.
    """
    return np.sum(np.absolute(w[:100] - w[-100:]))

我需要把diff()写为只接受一个参数,因为scipy.opyimize.minimize要求传递给x0参数的数组是一维的。
至于约束,我有

  1. w1是固定的,允许更改
  2. w2允许更改
  3. w2的绝对值之和在0.1和1.1之间:0.1 <= sum(abs(w2)) <= 1.1
  4. w2中任意元素i|w2_i| < 0.01
    对于如何使用BoundsLinearConstraints对象编写这些约束,我感到很困惑。
from scipy.optimize import minimize, Bounds, LinearConstraint

bounds = Bounds(lb=[-0.01] * 200, ub=[0.01] * 200)  # constraint #4
lc = LinearConstraint([[1] * 200], [0.1], [1.1])  # constraint #3
res = minimize(
    fun=diff,
    method='trust-constr',
    x0=w,  # my flattened vector containing w1 first 100 elements, and w2 in last 100 elements
    bounds=bounds,
    constraints=(lc)
)

我对bounds变量的逻辑来自约束#4,对于lc,变量来自约束#3。但是,我知道我的编码是错误的,因为下限和上限的长度都是200,这似乎表明它们同时适用于w1w2,而我只想不对w2应用约束(如果我尝试将Bounds中的数组长度从200更改为100,则会出现错误ValueError: operands could not be broadcast together with shapes (200,) (100,))。
LinearConstraint的形状和参数类型对我来说尤其令人困惑,但我确实尝试遵循了scipy的示例。
当前的实现似乎永远不会完成,它只是永远挂起。
我如何正确地实现boundsLinearConstraint,使其满足上面列出的约束条件(如果可能的话)?

yhqotfr8

yhqotfr81#

你的问题可以很容易地用线性优化问题(LP)来表达,你只需要重新表达优化变量的所有绝对值。
稍微改变一下符号(x现在是优化变量w2,w只是你给定的向量w1),你的问题读作

min |w_1 - x_1| + .... + |w_N - x_N|

s.t. lb <= |x1| + ... + |xN| <= ub         (3)
                       |x_i| <= 0.01 - eps (4) (models the strict inequality)

其中eps只是一个足够小的数,以便对严格的不等式进行建模。
让我们考虑约束(3)。这里,我们添加额外的正变量z并定义z_i =| x_i个|。然后,我们替换所有绝对值|x_i个|通过z_i并施加约束条件-x_i〈= z_i〈= x_i,该约束条件模拟关系z_i =| x_i个|类似地,你可以继续进行目标和约束(4),后者是微不足道的,等价于-(0.01 - eps)〈= x_i〈= 0.01 - eps。
最后,你的优化问题应该是这样的(假设你的所有w_i都是正的):

min u1 + .... + uN

s.t.      lb <= z1 + ... + zN <= ub
          -x <=      z        <= x
 -0.01 + eps <=      x        <= 0.01 - eps
    -(w-x)   <=      u        <= w - x
          0  <= z
          0  <= u

有3*N个优化变量x1,...,xN,u1,...,uN,z1,...,zN。将这些约束写为矩阵向量积A_ineq * x〈= b_ineq并不难。然后,您可以通过scipy.optimize.linprog求解如下:

import numpy as np
from scipy.optimize import minimize, linprog

n = 100
w = np.abs(np.random.randn(n))
eps = 1e-10
lb = 0.1
ub = 1.1

# linear constraints: A_ub * (x, z, u)^T <= b_ub

A_ineq = np.block([
    [np.zeros(n), np.ones(n), np.zeros(n)],
    [np.zeros(n), -np.ones(n), np.zeros(n)],
    [-np.eye(n),  np.eye(n), np.zeros((n, n))],
    [-np.eye(n), -np.eye(n), np.zeros((n, n))],
    [ np.eye(n), np.zeros((n, n)), -np.eye(n)],
    [ np.eye(n), np.zeros((n, n)),  np.eye(n)],
])

b_ineq = np.hstack((ub, -lb, np.zeros(n), np.zeros(n), w, w))

# bounds: lower <= (x, z, u)^T <= upper

lower = np.hstack(((-0.01 + eps) * np.ones(n), np.zeros(n), np.zeros(n)))
upper = np.hstack((( 0.01 - eps) * np.ones(n), np.inf*np.ones(n), np.inf*np.ones(n)))
bounds = [(l, u) for (l, u) in zip(lower, upper)]

# objective: c^T * (x, z, u)

c = np.hstack((np.zeros(n), np.zeros(n), np.ones(n)))

# solve the problem

res = linprog(c, A_ub=A_ineq, b_ub=b_ineq, method="highs")

# your solution

x = res.x[:n]
print(res.message)
print(x)

一些音符以任意顺序排列:

  • 强烈建议使用linprog而不是minimize来解决线性优化问题。前者提供了一个与HiGHS的接口,HiGHS是一个高性能的LP求解器HiGHs,它的性能优于minimize引擎下的所有算法。但是,值得一提的是,minimize是用于非线性优化问题的。
  • 如果你的值w不全是正的,我们需要改变公式。
nbewdwxp

nbewdwxp2#

您可以(为了清楚起见,也许应该)在minimize中使用args参数,并将固定向量作为额外参数提供给函数。
如果按如下方式设置方程式:

def diff(w2, w1):
    return np.sum(np.absolute(w1 - w2))

和您的约束

bounds = Bounds(lb=[-0.01] * 100, ub=[0.01] * 100)  # constraint #4
lc = LinearConstraint([[1] * 100], [0.1], [1.1])  # constraint #3

然后做了

res = minimize(
    fun=diff,
    method='trust-constr',
    x0=w1,
    args=(w2,),
    bounds=bounds,
    constraints=[lc]
)

然后道:

print(res.success, res.status, res.nit, np.abs(res.x).sum(), all(np.abs(res.x) < 0.01))

收益率(至少对我来说)

(True, 1, 17, 0.9841520351691752, True)

这似乎是你想要的。
请注意,我的测试输入为:

w1 = (np.arange(100) - 50) / 1000
w2 = np.ones(100, dtype=float)

这可能对装配过程有利或不利。

相关问题