how do i check whether a solution set exists which satisfies a set of linear inequalities?

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.

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top