I have formulated a linear programming problem on the form
\begin{align} &\min\limits_{x_1,\cdots,x_p}\sum\limits_{i=1}^p x_i \\ &\text{st. } \begin{split} Ax &= b \\ x_1&\geq0,\cdots,x_p\geq 0. \end{split} \end{align}
$A$ is similar to a Vandermonde matrix, and reads \begin{align} A = \begin{bmatrix} a_1^2 & a_2^2 & \cdots & a_p^2\\ a_1^3 & a_2^3 & \cdots & a_p^3 \\ \vdots & & \ddots & \vdots \\ a_1^m & a_2^m & \cdots & a_p^m \end{bmatrix}. \end{align} Here is where my problem gets interesting: The vector $b$ is fixed, but the matrix $A$ is not; neither the elements of $A$, nor the parameter $p$. I want to determine $A$ (equivalently $a_1,a_2,\cdots,a_p$) and $p$ so that the above LP problem has a solution. In other words, given $b$, I want to find $A$ such that the feasible region is nonempty.
Observations/more information
- All the odd elements of $b$ are positive, i.e. $b_1 > 0,b_3 > 0,\cdots$.
- The $a_i$'s are distinct and nonzero.
- The problem can be simplified by fixing the parameter $p$ to some $p \geq m$, e.g. $p = m,$ $p = m+1,\cdots$.
Attempt of solution
The solutions for small $m$ are quite explicit, but the general case seems much harder. In the end one would need to solve $m$th order polynomials for $a_i$, where the existence of a real solution falls into doubt.
Question
My question boils down to this: Does anyone have any clues/ides as to how to proceed? Do you know of any theorems in linear programming(or elsewhere) that can help me? Can you find an example (i.e. a $b$ with the odd elements positive) where no solution can exist?
Thanks in advance!