2

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?

Michael Grant
  • 19,450
Patrick
  • 23
  • 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

2 Answers2

1

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.

Michael Grant
  • 19,450
  • 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
  • Does it have to be in C#? Can you not build a wrapper around an unmanaged library? – Michael Grant Mar 22 '15 at 17:00
  • Actually, I would be able to use a wrapper around an unmanaged library, it would have to be c++ though – Patrick Mar 22 '15 at 17:06
  • 1
    Thanks for the suggestion to use a wrapper! Just found a usable library in c++: http://www.coin-or.org/projects/ that will save me quite a bit of work! – Patrick Mar 22 '15 at 17:31
  • Great! May I request that you accept this as the solution then? (And upvote?) – Michael Grant Mar 22 '15 at 17:46
  • Don't have enough repution to upvote yet – Patrick Mar 22 '15 at 17:49
  • Ah, gotcha. Thanks for the checkmark though! – Michael Grant Mar 22 '15 at 18:14
0

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.

architectpianist
  • 1,046
  • I lost you when you took the equalities as pairs, what are b and c? – Patrick Mar 22 '15 at 02: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 02: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 02: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 03: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 04:01
  • Right. In two dimensions you could use the ratio of the x components of y and vt. In terms of x (the variables of the linear program), we would substitute and get $z=\frac{x_1 \vec{v}{1x} + x_2 \vec{v}{2x} + \cdot\cdot\cdot + x_n \vec{v}{nx}}{\vec{v}{tx}}$. – architectpianist Mar 22 '15 at 13:01
  • Would this be different for dimensions greater then 2? – Patrick Mar 22 '15 at 13:14
  • No, because the objective function will work with any component of any dimension vector (due to the constraints on the solutions, we know that all possible solutions will result in a vector parallel to vt). But watch out for this fact: the vectors you're studying are m-dimensional by definition, but the solution space for the linear program is n-dimensional (number of vectors being used to produce the target vector). – architectpianist Mar 22 '15 at 14:15
  • Ok, so that just means that the number of vectors in most cases must be greater then the length of the vectors? – Patrick Mar 22 '15 at 14:25
  • In most cases, yes. Of course, it's not a hard and fast rule. – architectpianist Mar 22 '15 at 14:28
  • Ok, I think I got it now, thank you! I really appreciate you taking the time to answer all this! – Patrick Mar 22 '15 at 14:31