Find at least one solution to matrix inequality

Question

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!

Answer 1

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_{s\geq 0, x} \{ 0^Tx : Ax - s = b\}.$$

2. 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\}$.

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_i\geq 0$, $-1$ otherwise, and $c_i=1$ if $b_i\leq 0$, $0$ otherwise.

Answer 2

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