Thread Subject: How do I solve the following system of linear inequalities?

Let A=[1 -2 1 3 1;-1 1/2 -3 2 3;1 1 1 -3 -4;1 -3 2 2 4;-3 1 -2 1 2;3 0 -3 1 2]
and b=[0;0;0;0;0]
Ax >= b

How do I solve this in Matlab?
Please help me figure this out.

Thank you so much!

Hi there,

One possibility is the use of singular value decomposition of your matrix itself. You could also possibly use QR decomposition as well. See my attempt at solving this problem. You would use this approach if you want a minimal set of hyperplanes to describe the final solution which becomes important if dimension of your space is large. However, for this problem-a brutal solution of Ax>=b symbolically should also suffice.

% cleanup
clear all;
clc;
reset(symengine);

% To solve Ax>=b
A=[1 -2 1 3 1;-1 1/2 -3 2 3;1 1 1 -3 -4;1 -3 2 2 4;-3 1 -2 1 2;3 0 -3 1 2];
% b should have the same dimension as the number of rows of A
b=[2;3;4;1;2;1];

% Find the SVD of the matrix A(mxn). U(mxm) and V will(nxn) be unitary
% matrices with S as (mxn) with values along the diagonal, 0s will trail.
[U,S,V]=svd(A);

% Declare some symbolic variables
syms x y x1 x2 x3 x4 x5 x6
x=sym('[x1;x2;x3;x4;x5]');

% Do some math
% Basic idea is (USV)x>=b, start moving terms to the right to get equations in x
b_dash=U\b;
for i=1:(size(S,2))
    if S(i,i)~=0
    % Points within the solution should satisfy the following equation >=0. To test if a given point is a solution, plug
    % that value into all equations to see if they all satisfy y>=0 and we
    % are done. To express the solution symbolically, use
    y(i,1)=V(i,:)*x-b_dash(i,1)/S(i,i);
    else
        break;
    end
 end

Please note that these set of equations would describe the solution in terms of the hyperplanes. Visualization of this may require some creativity(some dimensions of the hyperplanes or using projections) for this 6D space. However, determining if a point belongs to the solution set should be easy based on the solution above.

Thanks,

Saurabh