Solving under-determined matrix equation Ax =b for non-negative solutions efficiently

I need to know if there is a efficicient way of solving Ax=b in matlab. In my problem A is sparse matrix with size mxn, where n is in order of 1e6 while m is in 1000s. Also, A_ij is 0,1 or -1.

The solution needs to non-negative.

We were preciously using Z3 LP solver to solve this.

Answer 1

[Soumya]

Hi @Shadab Ahmed,

Given that A is a large sparse matrix with elements restricted to (−1, 0, or 1), it is highly favourable to use sparse optimization techniques. The non-negativity constraint (x≥0) is a necessary condition for the problem to be formulated as a linear program. The ‘linprog’ function can be used here as it solves linear optimization problems with linear constraints and bounds, making it an effective tool to find a feasible, non-negative solution to ‘Ax = b’.

The following steps can be followed to achieve the same:

• Set the conditions for the optimization, that is all values in ‘x>= 0’:

f = zeros(n, 1);   
lb = zeros(n, 1); % x must be greater than or equal to 0 

• Set up the solver parameters to efficiently solve large linear programming problems:

options = optimoptions('linprog', ... 
  'Algorithm', 'interior-point', ... % Good for large-scale problems 
  'Display', 'iter', ...             % Show solver progress 
  'MaxTime', 600);            % Optional: set a time limit (seconds)

• Run the solver to find a feasible solution:

[x, fval, exitflag, output] = linprog(f, [], [], A, b, lb, ub, options); 

Please refer to the following documentation to get to know more about the given concepts:

• ‘linprog’ function: https://www.mathworks.com/help/optim/ug/linprog.html
• Optimization Toolbox Documentation https://www.mathworks.com/help/optim/

I hope this helps!