我的子集平均问题是否有 DP 解决方案？

Question

我有一个无法解决的组合数学问题。

给定一组向量和一个目标向量，return每个向量的标量，以便集合中缩放向量的平均值最接近目标。

编辑：权重 w_i 在 [0, 1] 范围内。这是一个约束优化问题：

最小化 d(avg(w_i * x_i), 目标) 以 sum(w_i) - 1 = 0

为准

如果我必须命名这个问题，那将是无界子集平均值。

我看过unbounded knapsack和类似的问题，但是由于数字的相互依赖性，动态规划实现似乎是不可能的。

我也实现了一个遗传算法，能够适度地近似权重，但是它花费的时间太长，我最初希望使用动态规划来解决这个问题。

还有希望吗？

Answer 1

可视化

在 2D 中 space 问题的解决方案可以这样表示

问题class鉴定

正如其他人所认识到的，这是一个优化问题。你有线性约束和凸 objective 函数，它可以转换为 quadratic programming, (read Least squares session)

转换为标准格式

如果要最小化w[i] * x[i]的平均值，这个就是sum(w[i] * x[i]) / N，如果把w[i]排列成一个(1 x N_vectors)矩阵的元素，每个向量x[i] 作为 (N_vectors x DIM) 矩阵的第 i 行，它变为 w @ X / N_vectors （@ 是矩阵乘积运算符）。

要转换为该形式，您必须构造一个矩阵，使 A*x < b 的每一行表示 -w[i] < 0，等式 sum(w) = 1 变为 sum(w) < 1 和 -sum(w) < -1。但是有一些很棒的工具可以使这部分自动化。

实施

这可以使用 cvxpy 轻松实现，您不必关心扩展所有约束。

以下函数解决了这个问题，如果向量的维度为 2，则绘制结果。


import cvxpy;
import numpy as np
import matplotlib.pyplot as plt

def place_there(X, target):
    # some linear algebra arrangements
    target = target.reshape((1, -1))
    ncols = target.shape[1]
    X = np.array(X).reshape((-1, ncols))
    N_vectors = X.shape[0]
    # variable of the problem
    w = cvxpy.Variable((1, X.shape[0]))
    # solve the problem with the objective of minimize the norm of w * X - T (@ is the matrix product)
    P = cvxpy.Problem(cvxpy.Minimize(cvxpy.norm((w @ X) / N_vectors - target)), [w >= 0, cvxpy.sum(w) == 1])
    
    # here it is solved
    print('Distance from target is: ', P.solve())
    
    # show the solution in a nice plot
    # w.value is the w that gave the optimal solution
    Y = w.value.transpose() * X / N_vectors
    path = np.zeros((X.shape[0] + 1, 2))
    path[1:, :] = np.cumsum(Y, axis=0)
    randColors=np.random.rand( 3* X.shape[0], 3).reshape((-1, 3)) * 0.7
    plt.quiver(path[:-1,0], path[:-1, 1], Y[:, 0], Y[:, 1], color=randColors, angles='xy', scale_units='xy', scale=1)
    plt.plot(target[:, 0], target[:, 1], 'or')

你可以运行像这样

target = np.array([[1.234, 0.456]]);
plt.figure(figsize=(12, 4))
for i in [1,2,3]:
    X = np.random.randn(20) * 100
    plt.subplot(1,3,i)
    place_there(X, target)
    plt.xlim([-3, 3])
    plt.ylim([-3, 3])
    plt.grid()
plt.show();

我的子集平均问题是否有 DP 解决方案？

Is there a DP solution for my subset average problem?

python

math

heuristics

dynamic-programming

combinatorics

可视化

问题class鉴定

转换为标准格式

实施