How to maximize the sum of vectors in target direction. Given a number of vectors, and an unknown variable for each vector, say for example:
$v_1, v_2, v_3,\dots,v_n$ and $x_1, x_2, x_3,\dots,x_n$
and a target vector $v_t$
I am trying to create an algorithm to maximize $p$ by setting $x_1, x_2, x_3, \dots, x_n$ such that:
$$v_1\cdot x_1 + v_2\cdot x_2 + v_3\cdot x_3 + \dots + v_n\cdot x_n = v_t \cdot p$$
the coefficients, $x_1$, $x_2$, $x_3$, and $x_n$, are constrained like:
$$0 \le x_1 \le c_1$$
$$0 \le x_2 \le c_2$$
$$0 \le x_3 \le c_3$$
$$\vdots$$
$$0 \le x_n \le c_n$$
where, $c_1,c_2,c_3,\dots,c_n$ are given constants.
Can this be reduced to a linear program, and if so, how?
 A: I think @architectpianist's solution is far too complex. This is a very simple linear program in $x$ and $p$:
\begin{array}{ll}
\text{maximize} & p \\
\text{subject to} & \sum_{i=1}^n v_i x_i = p v_t \\
& 0 \leq x_i \leq c_i, ~ i=1,2,\dots, n
\end{array}
If you let $V$ be the matrix formed with $v_i$ as its columns, this becomes
\begin{array}{ll}
\text{maximize} & p \\
\text{subject to} & V x = p v_t \\
& 0 \leq x \leq c
\end{array}
This is a linear program with $n+1$ variables, $m$ equality constraints (where $m$ is the dimension of the $v$ vectors), and $2n$ simple bound constraints.
A: Here's my interpretation of the problem:
You're asking to determine a set of coefficients $x_1, x_2, ... , x_n$ for the m-dimensional vectors $\vec{v}_1,\vec{v}_2,...,\vec{v}_n$ such that $\vec{y}=\sum_{k=1}^{n}x_k\vec{v}_k$ is parallel to a given vector $v_t$. Also the coefficients are constrained by $0\leq x_k\leq c_k$. Then you want to find the set of coefficients that maximizes $||\vec{y}||$.
To say that $\vec{y}$ is parallel to $\vec{v}_t$ is equivalent to saying that
$$\frac{\vec{y}_1}{\vec{v}_{t1}} = \frac{\vec{y}_2}{\vec{v}_{t2}} = \cdot\cdot\cdot = \frac{\vec{y}_m}{\vec{v}_{tm}}$$
where $\vec{y}_i$ means the ith component of $\vec{y}$. Now we take these equalities in pairs for purposes of creating a linear system. For an arbitrary pair of components b and c, we would have
$$\frac{\sum_{k=1}^{n}x_{k}\vec{v}_{kb}}{v_{tb}}=\frac{\sum_{k=1}^{n}x_{k}\vec{v}_{kc}}{v_{tc}}$$
Rearranging that and putting the $x_k$'s together, we get
$$\sum_{k=1}^{n} x_k\left(\frac{\vec{v}_{kb}}{\vec{v}_{tb}}-\frac{\vec{v}_{kc}}{\vec{v}_{tc}}\right)=0$$
Over all possible pairs of values for b and c, these equations should form a linear system that can be optimized using linear programming. Since we took the equations in pairs we should have $m \choose 2$ equations. For example, it may be worth noting that if ${m \choose 2} > n$, you would be unlikely to find a solution that satisfied all the conditions.
