您的位置: 首页  >  技术问答  >  我的子集平均问题有DP解决方案吗?

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

分类: 技术问答 • 2022-05-02 23:06:39
问题描述：

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

I have a combinatorics problem that I can't solve.

给出一组矢量和一个目标矢量，为每个矢量返回一个标量，以使该组中缩放后的矢量的平均值最接近目标.

Given a set of vectors and a target vector, return a scalar for each vector, so that the average of the scaled vectors in the set is closest to the target.

权重w_i在[0，1]范围内.这是一个受约束的优化问题:

Weights w_i are in range [0, 1]. This is a constrained optimisation problem:

最小化d(avg(w_i * x_i)，目标)取决于总和(w_i)-1 = 0

minimise d(avg(w_i * x_i), target) subject to sum(w_i) - 1 = 0

如果我不得不说这个问题，那将是无界子集平均值.

If i had to name this problem it would be unbounded subset average.

我已经研究了无限制的背包和类似的问题，但是由于数字的相互依赖性，似乎无法实现动态编程.

I have looked at the unbounded knapsack and similar problems, but a dynamic programming implementation seems to be impossible due to the interdependence of the numbers.

我还补充了一种遗传算法，该算法能够很好地近似权重，但是它花费的时间太长，最初我希望使用动态编程来解决问题.

I also inplemented a genetic algorithm that is able to approximate the weights moderately well, but it takes too long and I was initially hoping to solve the problem using dynamic programming.

有希望吗?

答

可视化

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

Visualization

In a 2D space the solution to the problem can be represented like this

正如其他人所公认的，这是一个优化问题.您具有线性约束和凸目标函数，可以将其强制转换为二次规划，(阅读最小二乘会话)

As recognized by others this is a an optimization problem. You have linear constraints and a convex objective function, it can be cast to 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 (其中 @ 是矩阵乘积运算符).

If you want to minimize the average of w[i] * x[i], this is sum(w[i] * x[i]) / N, if you arrange w[i] as the elements of a (1 x N_vectors) matrix, and each vector x[i] as the i-th row of a (N_vectors x DIM) matrix, it becomes w @ X / N_vectors (with @ being the matrix product operator).

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

To cast to that form you would have to construct a matrix so that each rows of A*x < b expressing -w[i] < 0, the equality is sum(w) = 1 becomes sum(w) < 1 and -sum(w) < -1. But there there are amazing tools to automate this part.

可以很容易地使用 cvxpy 来实现，而且您不必担心扩展所有约束.

This can be readily implemented using cvxpy, and you don't have to care about expanding all the constraints.

以下函数解决了该问题，并且如果向量的维数为2，则绘制结果.

The following function solves the problem and if the vectors have dimension 2 plot the result.


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();

相关推荐