CODEWITHSUNDEEP
algorithmoptimizationlinear-algebra
Ricoter
Ricoter

Reputation: 763

Find combination of vectors to approach target vector

I have about 10000 vectors of about 100 elements (floats) and 1 target vector of also 100 elements. My goal is to approach this target vector by using some combination of these 10000 vectors. However, I can use every vector only once and the elements can be positive or negative. Anybody any thoughts on this, and if its even possible to optimize?

A small example would be:

v1 = [1.5, 3.0, -1.5]
v2 = [-0.5, -1.0, 3.0]
v3 = [1.0, 0.0, 0.0]

target = [0.5, 2.0, 1.0]

# the best combination here would be v1 and v2

PS. I'm using Julia, but python, c(++) or thoughts on some algorithm are also very welcome

Upvotes: 1

Views: 621

Answers (1)

Bob
Bob

Reputation: 14654

Reading the comments, It seems that the interpretation of the problem is minimize distance(sum(w[i] * v[i]) - target), for w[i] in [0, 1].

If we use the standard Euclidean this is not even a MILP (mixed integer linear programming) problem it is a mixed integer quadratic programming problem. Since you did not define distance I will use the norm1 as measure of distance.

As mentioned in the comments you have basically 2**10,100 possibilities. But fortunately MILP can use bounds to prune the search (e.g. branch and bound), and the complexity in the typical case will be much less.

I posted a solution for the problem without the constraint w[i] in [0, 1] some time ago here. And that can easily modified for the problem we are talking about.

def place_there_ilp(X, target):
    # some linear algebra arrangements
    target = np.array(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]), integer=True)
    # solve the problem with the objective of minimize the norm of w * X - T (@ is the matrix product)
    P = cvxpy.Problem(cvxpy.Minimize(cvxpy.atoms.norm1((w @ X) / N_vectors - target)), [w >= 0, w <=1])
    
    # here it is solved
    return w.value

Trying with the problem instance you provided

v1 = [1.5, 3.0, -1.5]
v2 = [-0.5, -1.0, 3.0]
v3 = [1.0, 0.0, 0.0]

target = [0.5, 2.0, 1.0]

place_there_ilp([v1, v2, v3], target)

gives

array([[1., 1., 0.]])

That means 1 * v1 + 1 * v2 + 0 * v3

You will probably have a hard time, to run your 10000 x 100 problem but I would say that it is possible this.

With the code below I tried a 400 x 100 it runs in 1.38s, 800 x 100 runs in 9.64s

X = np.random.randn(801, 100) # 800 x 100 problem
place_there_ilp(X[1:, :], X[0, :])

Upvotes: 3

Related Questions