# 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?

• What is $v_t$? Do you mean you want to maximize the norm (length) of the vector $v_1 x_1 + \cdots + v_n x_n$? – angryavian Mar 21 '15 at 23:14
• vt when the calculation would actually be performed, is given. I am trying to maximize the length of the vector v1x1+⋯+vnxn when its normalization is equal to that of vt. – Patrick Mar 21 '15 at 23:17

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.

• That simplifies things quite a bit. – Patrick Mar 22 '15 at 16:40
• I'm confident any competent LP solver will be able to handle this for you without difficulty. It's not a particularly special problem structure. – Michael Grant Mar 22 '15 at 16:47
• Since I will be writing the lp solver myself (haven't been able to find affordable commercial solver for c#) Is there anything I should know about this particular problem structure? – Patrick Mar 22 '15 at 16:51
• No, there is nothing special. But please don't implement your own. There must be a free LP solver out there that works with C#. That may be worth a new question on another Q&A site somewhere (StackOverflow, CompSci.SE, OR-Exchange, but not here). – Michael Grant Mar 22 '15 at 16:59
• Thanks for the suggestion to use a wrapper! Just found a usable library in c++: coin-or.org/projects that will save me quite a bit of work! – Patrick Mar 22 '15 at 17:31

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.

• I lost you when you took the equalities as pairs, what are b and c? – Patrick Mar 22 '15 at 2:41
• For instance, if you were looking at vectors in 3D space, you would have an equation for the x and y components, one for the y and z components, and one for the x and z components. In higher dimensions, you would have to have more equations since there are more pairs of components. – architectpianist Mar 22 '15 at 2:45
• Ah so it just handles all the possible combinations. This is much more complicated the I had imagined, so the final equation you wrote could be used as the objective function for 2-dimensional vectors? How would I combine the combinations of equations for more then 2 dimensions to create an objective function? – Patrick Mar 22 '15 at 2:55
• Well, no, each equation would be a constraint on the values of x. The objective function would be maximizing $z=\vec{y}_1/\vec{v}_{t1}$ (using any one of the components, since they all reflect the length of the desired vector). But your solutions would be subject to the conditions I described in the answer. – architectpianist Mar 22 '15 at 3:46
• Ok, now I think I get it, so the last equation in the answer is a constraint, and there will be one of these for each possible combination of the components of the vector, and the objective function would look something like: z= y1.x/vt.x, is that correct? – Patrick Mar 22 '15 at 4:01