How to find minimum amount to add to achieve target proportions by adding to masses

Question

I am trying to solve the following problem:

Given a vector $\vec{m}$ of masses for $n$ substances, I want to find how much mass to add to each substance so that it can reach the vector of target proportions, $\vec{p}$, while minimizing the total amount of mass added (i.e., $\min \sum_{i=1}^n x_i$). Thus, I want to find $\vec{x}$ such that

$$ \frac{1}{\sum_{i=1}^n (m_i + x_i)} \biggr(\vec{m} + \vec{x} \biggr) = \vec{p} $$

where

$$ \vec{m} = \begin{bmatrix} m_1 \\ m_2 \\ ... \\ m_n \end{bmatrix} $$ $$ \vec{x} = \begin{bmatrix} x_1 \\ x_2 \\ ... \\ x_n \end{bmatrix} $$ $$ \vec{p} = \begin{bmatrix} p_1 \\ p_2 \\ ... \\ p_n \end{bmatrix} $$

I have written out these out in a system of linear equations, such that multiplying the scalar sum $\sum_{i=1}^n (m_i + x_i)$ which is the normalizing factor which is also in terms of the unknowns $x_i$'s,

$$ \biggr(\vec{m} + \vec{x} \biggr) = \biggr( \sum_{i=1}^n (m_i + x_i) \biggr) \vec{p} $$

Now, following from this, the system of linear equations is

$$ m_1 + x_1 = p_1 (m_1 + x_1 + ... + m_n + x_n) $$ $$ ... $$ $$ m_n + x_n = p_n (m_1 + x_1 + ... + m_n + x_n) $$

based on this, the equation may be re-written as

$$ \vec{m} + \vec{x} = \vec{p} \biggr( (\vec{m} + \vec{x}) \cdot \vec{1} \biggr) $$

Re-writing this in another form with just the independent variables $x_i$'s on one side, this becomes:

$$ \vec{m} - \biggr(\sum_{i=1}^n m_i \biggr) \vec{p} = (P - I_n) \vec{x} $$

where

$$ P = \begin{bmatrix} w_1 & w_1 & ... & w_1 & w_1 \\w_2 & w_2 & ... & w_2 & w_2 \\ ... & ... & ... & ... & ... \\ w_n & w_n & ... & w_n & w_n \end{bmatrix} $$

and $I_n$ is the identity matrix of size $n \times n$.

I am trying to find a way to solve this equation for the case where $x_i \ge 0$ $\forall i \in \{1, ..., n\}$ and minimizing the $x_i$'s. I realized that the inverse may not exist due to dependence.

For example, let

$$ \vec{m} = \begin{bmatrix} 500 \\ 900 \end{bmatrix}, \quad \vec{p} = \begin{bmatrix} 0.9 \\ 0.1 \end{bmatrix} $$

Then, the equations are

$$ 500 + x_1 = 0.9 (1400 + x_1 + x_2) $$ $$ 900 + x_2 = 0.1 (1400 + x_1 + x_2) $$

which yields

$$ 500 - 0.9 (1400) = -0.1 x_1 + 0.9 x_2 $$ $$ 900 - 0.1 (1400) = 0.1 x_1 - 0.9 x_2 $$

which has infinite solutions due to the dependence of the vectors in the $P - I_n$ matrix. Even for the simple 2 variable case, I am not sure how to formulate this problem in a way it can be solved. I have tried to utilize Python's numpy.linalg.solve and numpy.linalg.lstsq functions, both of which give the incorrect answer of $\vec{x} = (2992, -512)^T$ and for least squares a linear equation with slope and intercept of $92.68...$ and $-834.15...$, both of which are wrong (since $x_i \ge 0$).

While writing this, I realized that another implicit constraint (besides $x_i \ge 0$ $\forall i$) is that since $\vec{p}$ is a vector of $p$ is a vector of proportions of the masses we want, this implies

$$ \sum_{i=1}^n p_i = 1 $$

but this is already baked into the linear system of equations. Thus, I believe that there may be another way to formulate this problem by optimizing over the sum of $x_i$'s by somehow re-formulating this problem as an optimization problem

$$ \min \sum_{i=1}^n x_i $$ $$ s. t. $$ $$ m_i + x_i = w_i \sum_{j=1}^n (m_j + x_j) \quad \forall i \in \{1, ..., n \} $$ $$ x_i \ge 0 \quad \forall i \in \{1, ..., n \} $$

I am not sure how to proceed so that this is in a linear form that I can solve efficiently using linear algebra libraries in any language to solve such a problem (or even an iterative algorithm that can accomplish this without any matrix algebra/existing libraries). Is it just a matter of re-formulating the problem in a clever way? I don't believe I would need to formulate an affine or convex optimization in order to solve this, but perhaps I may need to.

Another approach I thought about was a greedy algorithm approach - i.e., find the highest target proportion $p_i$ out of $\vec{p}$, then add the next highest, etc. successively, but this would inevitably need to recalibration later on and it is definitely not a guaranteed correct solution (although numerically it may work). I want to ideally find a closed-form solution, and if that may not exist (due to the matrix representing the system of linear equations being singular or something), then an approximate solution (with caveat) that would work under most cases (ignoring pathological cases like $p_i = 1$ for a given $i$ and $p_j = 0$ where $i \ne j$ while the starting masses $m_i \ge 0$).

In the above example, a greedy approach would be to notice that since mass cannot be subtracted, we need at least $9000$ total mass in order for $900$ to be $0.1$, or $10 \%$, of the total mass. Thus, the minimum mass needed to be added is $7600$ to substance $1$, and $0$ to substance $2$. Thus, the solution is

$$ \vec{x}^* = \begin{bmatrix} 7600 \\ 0 \end{bmatrix} $$

However, what is a generalized approach solution to $n$-element vectors with the constraint of minimizing total mass added across all substances?

Answer 1

I think you initially overengineered the problem and your insight at the very end

In the above example, a greedy approach would be to notice that since mass cannot be subtracted, ...

is what leads to a very simple solution.

Find for every component of $\overrightarrow m$ what the total mass would be if that component was already at the desired proportion, that is calculate $q_i=\frac{m_i}{p_i}$ for all $i=1,2,\ldots, n$. Note that the total mass of any solution must be at least $q_i \forall i=1,2,\ldots,n$, because if you have a total mass $q < q_i$, the proportion of the $i$-the substance in the total mass would be bigger than $p_i$:

$$ q < q_i \Rightarrow q\times p_i < q_i\times p_i = m_i \Rightarrow m_i/q > p_i,$$

which means the proportion of the the $i$-th substance is too big.

That means the total mass $q$ of any solution must be at least the maximum of all $q_i$,

$$q \ge \max (q_1,q_1, \ldots, q_n) =: q_{max}$$

But there is a solution with total mass $q_{max}$, simply set

$$\forall i=1,2,\ldots,n: x_i = q_{max}p_i - m_i$$

That is a valid choice, because

$$\forall i=1,2,\ldots,n: x_i = q_{max}p_i - m_i \ge q_ip_i - m_i = m_i-m_i=0.$$

It's easy to see that this makes the final mass of each component $q_{max}p_i = x_i + m_i$ and the final total mass

$$\sum_{i=1}^n q_{max}p_i = q_{max}\sum_{i=1}^n p_i = q_{max} \times 1 = q_{max},$$

so each substance is at the desired proportion.

Answer 2

You want to minimize

$ f = \mathbf{1}^T \mathbf{x} $

Subject to

$ \mathbf{m}+ \mathbf{x} = \alpha \mathbf{p} $

where $ \displaystyle \alpha = \mathbf{1}^T (\mathbf{m + x}) $

and

$ x_i \gt 0, i = 1, 2, \dots, n $

Since we're minimizing $f$, then we're automatically minimizing $\alpha$.

It is rather easy to imagine what's going on in $3D$, i.e. if $ n = 3 $. You have a vector $ \mathbf{m}$ in the first octant (where all components are positive), and you have another vector $\mathbf{p}$ also in the first octant, and you want to add a vector $\mathbf{x}$, which is also in the first octant, such that $ \mathbf{m} + \mathbf{x} $ lies somewhere on the line $\lambda \mathbf{p}$, and the problem asks for such a vector with minimum sum of components, which is the minimum dot product of $\mathbf{x}$ with the vector $\mathbf{1}$.

$ \mathbf{x} = \alpha \mathbf{p} - \mathbf{m} $

Since we're seeking the minimum $\alpha$, such that all components of $\mathbf{x}$ are positive or zero, then

$ \alpha p_i \ge m_i $

So that

$ \alpha_{\text{Min}} = \text{Max}\left( \dfrac{m_i}{p_i} \right) $

For example if

$ \mathbf{ m } = \begin{bmatrix} 2 && 1 && 1 \end{bmatrix}^T $

And

$ \mathbf{p} = \begin{bmatrix} 1 && 3 && 4 \end{bmatrix}^T $

Then

$ \alpha_{\text{Min}} = \text{Max} \left( \dfrac{2}{1}, \dfrac{1}{3}, \dfrac{1}{4} \right) = 2 $

Therefore, the optimal vector $\mathbf{x}$ is

$ \mathbf{x} = \alpha \mathbf{p} - \mathbf{m} = 2 \begin{bmatrix} 1 && 3 && 4 \end{bmatrix}^T - \begin{bmatrix} 2 && 1 && 1 \end{bmatrix}^T \\= \begin{bmatrix} 0 && 5 && 7 \end{bmatrix}^T $

If on the other hand, for the same $\mathbf{m}$, the target proportions $\mathbf{p}$ is given by

$ \mathbf{p} = \begin{bmatrix} 5 && 3 && 2 \end{bmatrix}^T $, then

$ \alpha_{\text{Min}} = \text{Max} \left( \dfrac{2}{5}, \dfrac{1}{3}, \dfrac{1}{2} \right) = \dfrac{1}{2} $

Hence,

$ \mathbf{x} = \dfrac{1}{2} \begin{bmatrix} 5 && 3 && 2 \end{bmatrix}^T - \begin{bmatrix} 2 && 1 && 1 \end{bmatrix}^T \\= \begin{bmatrix} \dfrac{1}{2}&& \dfrac{1}{2}&& 0 \end{bmatrix}^T $

Similar reasoning holds for dimensions $n \gt 3$.