How can I solve a constrained underdetermined system A*x=b? I am trying lsqlin and am getting an undocumented error code -3.

I have an underdetermined system A*x=b, where A is 192x372, x is 372x1, and b is 192x1. The solution for x should be close to the known curve x_model. I have been trying lsqlin with constraints to try and solve the underdetermined system, but I'm getting error code -3 (which is undocumented). The pseudoinverse solution pinv(A)*b doesn't work well and can't utilize constraints (as far as I know).

I have tried using 180 equality constraints with lsqlin to constrain the solution at 90 points on each end. The equality constraints use the curve x_model. This should in theory make the system solvable (192 equations + 180 equality constraints = 372). I have also tried adding the inequality constraint x>0.

I get the following error:

Warning: Large-scale algorithm requires at least as many equations as variables
    in C matrix; using medium-scale algorithm instead. 
> In lsqlin at 282
  In test_lsq at 28
Exiting: the solution is unbounded and at infinity;
 the constraints are not restrictive enough.

lsq_flag =

      -3

Any ideas on how to solve this system?

Answer 1

[Matt J]

To investigate what's wrong with LSQLIN, we'll probably need to see your code, your data, and an explanation of what the terminology "curve x_model" means.

However, if your 180 equality constrains are of the form x(i)=c(i) where the c(i) are known values, then there's no apparent reason to be using LSQLIN, unless the constraints x>=0 that you added later are eventually going to become important.

With these equality constraints, you really only have 192 unknown x(i) and can re-write your equations as a square system

 A_square=b_square

where A_square is 192x192. You claim that A_square is full rank. If you are right, then

 A_square\b_square

is the solution. Even if it is not, then pinv(A_square)*b_square should easily give you one of the non-unique solutions.

[John Westerhoff]

To explain, the vector x_model are model values for x which provides a good approximation for the unknown vector x. Ideally I would not use the equality constraints with these approximate values, but that was one approach to solving the underdetermined system.

But, since I am using those constraints, I see your point about transforming this into a square system. I'll try that. Thanks.

[John Westerhoff]

I'm still having problems finding a solution to this system. To simplify things, I've reduced the number of variables to 10 by increasing the sample size. I have tried 2 approaches. One uses the suggestion above to rewrite the equations into a square system using the known values of x (actually these are approximate values from x_model). I've used x=A\b and lsqnonneg on this system. The second approach is an underdetermined system as discussed in my original comment above. This system is 10x22. I've setup 12 equality constraints (again using the approximate solution x_model) to try and make this system solvable. The approximation x_model should match the actual solution x to within 5-10%. I still get the following error using lsqlin:

Warning: Large-scale algorithm requires at least as many equations as variables
    in C matrix; using medium-scale algorithm instead. 
> In lsqlin at 282
  In test_lsq5 at 41
Exiting: the solution is unbounded and at infinity;
 the constraints are not restrictive enough.

flag =

      -3

output = 

           iterations: 2
      constrviolation: 0
            algorithm: 'medium-scale: active-set'
        firstorderopt: []
         cgiterations: []
              message: [1x96 char]

I have attached my code this time, which contains the data as well saved in a .mat file. Please let me know if you have any further ideas on how to solve this system.

[Matt J]

I've used x=A\b and lsqnonneg on this system.

If this worked, why do you persist in trying to solve with lsqlin? What additional value does the latter give you?

In any case, it never makes sense to use equality constraints of the form x(i)=known. If x(i) is known then there's just no purpose to treating it as an unknown. Eliminate the known variables and solve using lsqlin with whatever constraints you wish. Although, because your constraints are lower bounds x>=0, it makes more sense (and is better) to specify them explicitly using the LB input argument, not with Aineq,bineq.

[Matt J]

When I run test_lsq5, the lsqlin optimization succeeds (in R2013a) with exitflag=1 and looks very similar to the result of lsqnonneg.

[Matt J]

Your units look a bit awkward. Does it really make sense that A1,A2 are on the order of 1.0e-14 while b1, b2 are on the order of 1e9? Your solutions are then always on the order of 1e24. It seems like you're trying to measure the distance between two cities in micrometers instead of kilometers.

I mention this because the choice of units can affect performance of some solvers in different ways. There is a stopping parameter TolFun that for some algorithms is an absolute value representing what you consider a small change in the objective function. In your case, with the units you've chosen, a negligible change is probably ~1e12. Usually, the default TolFun is much lower. Clearly, it didn't affected things in R2013, because the optimization succeeded, but it's something to be careful of in general.