Vector decomposition into a convex combination of two vectors with constraints on the sum of their elements

146 Views Asked by At

Given the vector $\mathbb{v}$ of $n$ elements and a scalar $0<q<1$, how can I find the vectors $\mathbb{v}_1$ and $\mathbb{v}_2$ such that

$$ \mathbb{v} = q\, \mathbb{v}_1 + (1-q)\,\mathbb{v}_2 $$

subject to $\sum \mathbb{v}_{1i} = c_1$ and $\sum \mathbb{v}_{2i} = c_2$,

being $c_1$ and $c_2$ two given integer scalars ?

1

There are 1 best solutions below

5
On BEST ANSWER

Let $\vec 1$ be a vector for which every element is $1$. We can write your constraints as:

$$\vec 1\cdot\vec v_1=c_1,\ \ \ \vec 1\cdot\vec v_2=c_2$$

It should be clear that these define a pair of parallel (hyper)planes. If $\vec v$ is to be written as a convex combination of a point from each plane (which is to say, it lies on a line segment connecting them), it must lie between them. This gives us a simple feasibility test (assume without loss of generality $c_2>c_1$).

$$\exists\ \vec v_1, \vec v_2\iff c_1\le\vec 1\cdot\vec v\le c_2$$

To actually find $v_1$ and $v_2$, we can draw a line from $\vec v$ that intersects both planes. To do this, choose any $\vec u$ such that $\vec 1\cdot\vec u\neq 0$. The line $\vec v+\vec ut$ must intersect both planes. Solving for the intersections gives:

$$v_1=\vec v+(c_1-\vec 1\cdot\vec v)\frac{\vec u}{\vec 1\cdot\vec u},\ \ \ v_2=\vec v+(c_2-\vec 1\cdot\vec v)\frac{\vec u}{\vec 1\cdot\vec u}$$