Htykuut

I have the following problem posed:
find at least one vector $mathbf{x}$ such that
$$
Amathbf{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!

Consider the linear optimization problem
$$min_{x} { 0^Tx : Ax geq b}.$$
This can be solved in many ways. Let me name 3:

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




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




3. 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_igeq 0$, $-1$ otherwise, and $c_i=1$ if $b_ileq 0$, $0$ otherwise.

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).