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?

  • $\begingroup$ 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$? $\endgroup$ – angryavian Mar 21 '15 at 23:14
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ That simplifies things quite a bit. $\endgroup$ – Patrick Mar 22 '15 at 16:40
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Mar 22 '15 at 16:47
  • $\begingroup$ 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? $\endgroup$ – Patrick Mar 22 '15 at 16:51
  • $\begingroup$ 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). $\endgroup$ – Michael Grant Mar 22 '15 at 16:59
  • 1
    $\begingroup$ 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! $\endgroup$ – 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


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.

  • $\begingroup$ I lost you when you took the equalities as pairs, what are b and c? $\endgroup$ – Patrick Mar 22 '15 at 2:41
  • $\begingroup$ 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. $\endgroup$ – architectpianist Mar 22 '15 at 2:45
  • $\begingroup$ 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? $\endgroup$ – Patrick Mar 22 '15 at 2:55
  • $\begingroup$ 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. $\endgroup$ – architectpianist Mar 22 '15 at 3:46
  • $\begingroup$ 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? $\endgroup$ – Patrick Mar 22 '15 at 4:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.