Given a set of vectors and a target vector, find the set of scaling factors that minimizes distance of sum of those vectors from target

Question

I have a set of $n$ starting vectors $\vec i_n$ and a target vector $\vec t$. I have a set of scaling factors $a_n$ for which I can compute the sum $\vec s$:

$$ \vec s = \sum_{i=1}^n {a_i \vec i_i} $$

For each set of $a_n$, we can compute the distance to target using:

$$ d = \left| \vec s - \vec t \right| $$

I want to find the local minima (if any) for $d$, under the following constraints:

1. all starting vector coordinates and target vector coordinates are positive or $0$,
2. all scaling factors must be non-negative real numbers.

Is there a practical numerical method for solving such problems?

Answer 1

Suppose we are given a target $\mathrm{y} \in \mathbb{R}^d$ and vectors $\mathrm{b}_1, \mathrm{b}_2, \dots, \mathrm{b}_n \in \mathbb{R}^d$. Let

$$\mathrm{B} := \begin{bmatrix} | & | & & |\\ \mathrm{b}_1 & \mathrm{b}_2 & \ldots & \mathrm{b}_n\\ | & | & & | \end{bmatrix}$$

We would like to find a vector $\mathrm{x} \in (\mathbb{R}_0^+)^n$ such that $\|\mathrm{B} \mathrm{x} - \mathrm{y}\|_2$ is minimized. This is an inequality-constrained least-squares problem. Hence, we have the following (convex) quadratic program

$$\begin{array}{ll} \text{minimize} & \|\mathrm{B} \mathrm{x} - \mathrm{y}\|_2^2\\ \text{subject to} & \mathrm{x}\geq 0_n\end{array}$$

which should be easy to solve, as it is convex.

Answer 2

I would like to expand what I have said as a remark. And we can be helped in this by having a graphical view of what happens.

An essential thing is that you are working with what is called the (positive) convex cone generated by the $v_k$s. A geometrical view of it is the inside of a prismatic cone whose edges are directed by some of the $v_k$s (maybe not all, because some of the $v_k$s might be combination of others ; such $v_k$s should be to eliminated right at the beginning...).

Thus,

• either vector $t$ is situated inside this cone and there is an exact solution (i.e., $d=0$) or

• or $t$ is outside this cone. Then the closest $t$ is to be found either on an edge of the cone or on a face of it. Finding $t$ can be done, either by using the method proposed by @Rodrigo de Azevedo or by a specific method using the convex hull to be hopefully more efficient (if you are working with Matlab, it is the very powerful "convhull" function).

Remarks:

1) The cone might be either "full-rank" (I mean by this expression that the set of $v_k$s is full-rank, i.e., generate $\mathbb{R^4}$) or not.

2) The cone can fill the whole space (for example in $\mathbb{R^4}$ if you take as $v_k$s the four basis vectors and their four opposites) but I imagine you are not in this case.