Linear system solution with inequality constraints - methods?

Question

First of all, I hope I am posting this in the correct place. If not, I'm sorry and could you please direct me to where I should post this?

Problem: You are given a set of vectors, $\{\mathbf{a}^i\}_{i=1}^{24}$, and matrices $D_1$ and $D_2$ (both of dimension $[10\times6]$. Let the following be true:

• $\sum_{i=1}^{24} \mathbf{a}^i = \mathbf{1}\;,$
• $\mathbf{a}^i \geq \mathbf{0}\;,\forall i\;,$ (i.e. all elements positive),
• $(D_1 + D_2)\mathbf{1} = \mathbf{1}\;.$

Then, find vectors $\{\mathbf{b}^i\}_{i=1}^{24}$ and $\{\mathbf{c}^i\}_{i=1}^{24}$ that satisfy the equation, $$ \mathbf{c}^i - D_1 \mathbf{b}^i = D_2 \mathbf{a}^i\;,\quad \forall i\in \{1,2,\dots,24\}\;, $$

and the following constraints:

• $\sum_{i=1}^{24} \mathbf{c}^i = \mathbf{1}\;,$
• $\sum_{i=1}^{24} \mathbf{b}^i = \mathbf{1}\;,$
• $\mathbf{c}^i \geq \mathbf{0}\;,\forall i\;,$ (i.e. all elements positive),
• $\mathbf{b}^i \geq \mathbf{0}\;,\forall i\;,$ (i.e. all elements positive).

Could anyone please give me any pointers on how I could go about tackling this problem? I would be interested in finding a solution (if there are multiple), or even finding out that there are none. I think that this is a kind of optimization problem, but I have no idea about any methods I could use to solve this problem computationally.

Also, this is NOT homework.

Thanks a lot.

Answer 1

This is a linear programming feasibility problem (since you don't have an objective function to minimize or maximize.) You can simply use an objective function of $0$ and hand this off to any reasonable LP solver. You'll either get back a solution or the bad news that the problem is infeasible.