Is There A Dp Solution For My Subset Average Problem?

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

Solution 1:

Visualization

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

Problem class identification

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)

Casting to standard form

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).

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.

Implementation

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

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

defplace_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 solvedprint('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')

And you can run it like this

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