How to get conditioned solutions of Ax=B with least square?

Hello everybody,

I have an underdetermined matrix equation Ax=B, for which I want to apply least square method. The solution should be nonnegative.

I used “x=lsqnonneg(A,B)” for that. But it gives me a basic solution with many zero components in matrix x that is not suitable for my application. Therefore I tried “x=pinv(A)*B” and “x=A\B”. pinv gives me a solution with negative components and by backslash I get a warning that the matrix is singular and the components of x are NaN.

Is there any trick to get other nonnegative (and nonzero) solutions for an underdetermined equation?

Thank you in advance.

Monireh

[Matt J]

Is there any trick to get other nonnegative (and nonzero) solutions for an underdetermined equation?

Note that, even though your A is under-determined, it is unclear, because of the non-negativity constraints, whether "other solutions" exist to the least squares problem.

Answer 1

[Matt J]

The trick is to add equations or constraints so that the problem is not under-determined anymore. Since you do have further demands on properties that the solution should have, there should be a way to express those requirements in equation form.

[Walter Roberson]

Matt, in a posting a while ago, you indicated something along the lines that adding non-negative constraints to a least-squared problem made the problem no longer a linear one, so using a least-squares solver might no longer be viable ?

The user might need to use something like fmincon() with the objective function being the sum-of-squares of the residues. Unfortunately that has a really bad tendency to get stuck in global minima, so using something from the global minimization toolbox might be needed for multiple iterations. Or sometimes it is affordable to run fminsearch over a grid of values; the practical limit for that is somewhere around 3 million sample points, which doesn't take long to exhaust in a higher-dimensional problem.

[Matt J]

I'd have to see that post again, Walter, but in principle, I agree with everything you've said. My hope, though, is that the constraints yet to be specified by the OP might turn out to be convex, obviating the problem of local minima.

[Walter Roberson]

Now that I think of it, the previous posting was about linsolve(), a completely different situation.

[Monireh]

Thanks for your answers.

it is about the modeling of a battery. There are limited data points (equations) and other measuring points provide dependent equations. it is a linear problem and x>= 0 is a boundary condition. The matrix A includes only values 1 and 0, and the matrix B includes the voltage values. The unknown x correlates the weight that should not be negative.

Least square should actually give me some solutions, where I can look for the non-negative solutions. Can Matlab show all possible solutions for the problem??

[Torsten]

Yes.

Solve

A*x_inh=B

(e.g. using x_inh = lsqnonneg(A,B)).

Then

x_inh + null(A)

gives all solutions for your problem.

Best wishes

Torsten.

[Matt J]

Torsten's proposal with null(A) doesn't take non-negativity constraints into account. Modifying his proposal so that it does leads to solutions x(z) parametrized in z according to,

x(z) = x_inh - null(A)*z >=0

Here z is any vector lying in the polyhedral region

null(A)*z <= x_inh   %ensure positivity

For small A, you can find the vertices of this polyhedron using LCON2VERT ( Download ) assuming that it is bounded. If the polyhedron is not bounded, you may need to apply upper bounds on x(z) as well. Note also that the polyhedron might contain only the single point z=0 (see also my comment to your original post) meaning that x_inh is already the unique solution to the least squares problem.

If the solution is non-unique, the best thing to do is to pose an optimization problem in z,

   max.  g(z) =  F( x_inh - null(A)*z )

      subject to

   null(A)*z <= x_inh

where F(x) is some measure of merit of the different possible choices of x. You could solve this with fmincon or maybe a simpler solver, depending on what F looks like.