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

Question

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

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

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

最小化d（平均（w_i*x_i），目标），条件是总和（w_i）-1=0

如果我不得不命名这个问题，它将是无界子集平均。

我已经研究过无界背包和类似的问题，但由于数字的相互依赖性，动态编程实现似乎是不可能的。

我还补充了一个遗传算法，它能够很好地近似权重，但是它需要太长时间，我最初希望使用动态规划来解决这个问题。

还有希望吗？

Answer 1

正如其他人所认识到的，这是一个最佳化问题。你有线性约束和凸目标函数，它可以转换为二次规划，（阅读最小二乘会话）

如果您想要最小化< code>w[i] * x[i]的平均值，这是< code>sum(w[i] * x[i]) / N，如果您将< code>w[i]排列为< code>(1 x N_vectors)矩阵的元素，并且每个vector x[i]作为< code>(N_vectors x DIM)矩阵的第I行，则它变成< code>w @ X

要转换为该形式，您必须构造一个矩阵，以便A*x的每一行

这可以使用 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();