Find at least one solution to matrix inequality I have the following problem posed: 
find at least one vector $\mathbf{x}$ such that
$$
A\mathbf{x} + \mathbf{b} \geqslant \mathbf{0}
$$
for a given matrix $A$ and vector $\mathbf{b}$. Nothing is known about dimensions of the matrix. You may assume the set of solutions for this problem is non-empty and that the rank of the matrix is complete, i.e. $\mbox{rk}(A) = \mbox{min}(m, n)$. The inequality is understood as applied component-wise.
Do you know any algorithm capable of solving such problem? I checked textbooks on linear programming, but found nothing specifically dealing with this problem. Thanks for any comments!
 A: Consider the linear optimization problem
$$\min_{x} \{ 0^Tx : Ax \geq b\}.$$
This can be solved in many ways. Let me name 3:


*

*An infeasible interior point method. This solves 
$$\min_{s\geq 0, x} \{ 0^Tx : Ax - s = b\}.$$

*A feasible interior point method. Consider the extended linear optimization problem:
$$\min_{x,y\geq 0} \{ e^Ty : Ax+b+y \geq 0\}.$$
A feasible starting point for this problem is $x=0$, $y=\max\{0,-b\}$.

*With the two phase simplex method in which you only need the first phase. This is essentially solving 
$$\min_{x^- \geq 0,x^+\geq 0, y \geq 0} \{ c^Ty : A(x^+-x^-) + By \geq b\},$$
where $B$ is a diagonal matrix with $B_{ii}=1$ if $b_i\geq 0$, $-1$ otherwise, and $c_i=1$ if $b_i\leq 0$, $0$ otherwise.
A: Linear programming is your method of choice. 
A good way to visualize what is going on is to consider the rows of $A$ as vectors $A_i$. So you have a set of inequalities $ A_i x + b_i \geq 0$. Each of these inequalities defines a halfspace in $n$-dimensional space, with a boundary which is a hyperplane with normal vector  $A_i$ and distance from the origin   $b_i/ |A_i|$. Your matrix inequality equation is then the intersection of all of these   halfspaces. If the intersection is not empty, the intersection space is a polyhedron. 
Finding an $x$ is exactly the question whether this intersection is empty or not.  In linear programming, this  is called "interior point method" (you find it on wikipedia and elsewhere) and it is a well-known procedure for finding a feasible point to start any optimization procedure (which you do not have).
