How to check whether a solution set exists, which satisfies a set of linear inequalities?

Question

Is it possible to determine whether a set of solution exists that satisfies a set of linear inequalities outside Matlab (programmatically) Just a true/false would be enough but is it possible to do using a library in JavaScript (preferably as it is just a small working prototype) or if not then any simple python library?

I can do it by having a self written function with some constraints but that solution could be very shaky therefore before reinventing the wheel need some experts opinion.

So far what my understanding is for determining whether a solution set exists for a set of inequalities is as follows:

suppose the inequalities are:

y >= 2x + 1 
y <= 2x - 5
x >  1

making Y the subject here, I can try putting some finite positive values of X and some finite negative values of X inclusive zero.

More easily said domain for all inequalities would be [3,2,1,0,-1,-2,-3]

and will get the range(value of Y for each inequality)

later will compare all values of Y and see if there is some region of intersection over a given value of X.

for example:

   when X = 1 
   inequality 1 gives Y >= 3
   inequality 2 gives Y <= -3 
   inequality 3 says X >  1

so X = 1 does not found any common ground and I will move to another value of X.

but I am not really really sure as to when to stop? will a few values in each direction(positive or negative ) will define good constraints and help me determine whether a solution set exists for the inequalities, or not?

because the over lapping region of the inequalities can be at a very corner of the graph and a few initial values on either side of X domain will just prove them as non intersecting independent region, but we need to keep on iterating may be for a very large value of X where both inequalities have an overlapping region and some times even then they will be non intersecting.

So is there a basic library or function already written that could help me with this ? Or if not, then is my logic /understanding for solving such conditions is correct?

Instead of Matlab but just simple programming library in JavaScript.

The solution later will be extended to more than 2 may be 3 variable inequalities too.

My problem is some how or very similar to what is asked in this question from past

I am really new to solving mathematical equations, therefore I hope to have explained my problem nicely.

Answer 1

If you have a set of linear inequalities and you just want to know if they are feasible or not, you can form a simple convex optimisation problem or simply a feasibility problem. Say you have a variable vector X = [x, y] which you want to check the solution for and a set of linear inequalities each of the form a1x + a2y <= b.

Then you can basically form a matrix A and a column vector B by stacking the inequations rowwise, such that each row of A has the coefficients a1 and a2 for each inequality and the corresponding row of B has the constant b. Note that it is better to use either <= or >= for all inequalities, so adjust signs accordingly.

Now focus on this problem (assuming all inequalities are in <= form). You want to solve the following optimization problem, where the objective function has a constant value 0. This is also known as a feasibility problem.

minimize    0
subject to  AX <= B

Note that if the solution (minimized value) returns infinity, that means there is no X which satisfies the above constraints. If the solver returns 0 (which is the value of the constant objective function), that means there is atleast one X which satisfies the constraints. Hence you can find if there exists any solution to your inqualities.

You can use cvxpy library for this. Here is a nice tutorial in python. Also cvxpy library goes well with numpy and it takes care of all the internal solver details for you. You can even restrict your variable X to take real or integer values and also impose bound constraints in terms of linear inequalities like x + 0.y < = a etc.