Minimize an N-dimensional vector dot product with <N constraints

Question

I have a list of N variables $\vec{x}=(x_1, x_2, \cdots, x_N)$ where in my situation N will be around 10 and all of these variables must be nonnegative real numbers. I also have three linear constraint equations, which can be summarized with a matrix equation: $$\textbf{A}\vec{x}=\vec{B}.$$ If we write x as a N by 1 column vector, then A is a 3 by N matrix, and B is a 3 by 1 column vector. I know all of the elements of A and B, and they're all nonnegative reals. Also, no two rows of A are identical, so there will be solutions to this system of equations. To reasonable error, I want to find the minimum of this cost function (a dot product) and find the $\vec{x}$ that minimizes it: $$E=\sum_{n=1}^{N}x_i e_i.$$I know all of the (nonnegative and real) elements $e_i$.

Anyone know a way to calculate this in a reasonable amount of time using C++ or Mathematica? I expect it to be possible to find the global minimum because N is not huge and everything here is linear, but is that true? This is a basic enough problem that I'm sure someone has solved something similar to this, but I don't know what terminology to use to search for it.

Thanks!

Answer 1

1. You've got the answer right in the tags you selected -- this is a linear programming problem, almost the archetypal linear programming problem. There are many many packages to solve such problems in various languages. The simplest is probably Matlab, but that costs some money. I'm guessing it's built into mathematica as well, but I have used that in 25 years, so I really don't know.

2. Your problem statement isn't quite correct where you say "Also, no two rows of $A$ are identical, so there will be solutions to this system of equations". Consider the case $N = 5$, and $$ A = \pmatrix{1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0} $$ and $b = \pmatrix{3 \\ 3\\ 5}$. That becomes the equations \begin{align} x_1 &= 3 \\ x_2 &= 3 \\ x_1 + x_2 &= 5 \\ \end{align} which evidently have no solution, even though the rows of $A$ are all distinct. The condition you need is that the rows of $A$ are linearly independent.