LSE

A linear least squares solver, subject to linear equality constraints

Description

This submission was written by request - as a tool to handle linear least squares problems, subject to linear equality constraints that may potentially be rank deficient. (It handles problems with full rank constraints of course too.) In the event of a rank deficient constraint system, it tests for consistency of the constraints.

I added a few other features to LSE:

- It allows multiple right hand sides to the least squares problem, fully vectorized of course.
- Weights may be supplied.
- You are offered a choice of least squares solvers, either backslash or pinv.

LSE solves the problem (for an unknown vector x)

   argmin norm(A*x - b)

subject to the constraints

   C*x = d

As an example, consider the random system
A = rand(10,3);
b = rand(10,1);

With a rank deficient constraint set
C = [1 1 1;1 1 1];
d = [1;1];

X = lse(A,b,C,d)
X =
       0.5107
       0.57451
     -0.085212

Verify that the constraints are satisfied

C*X
ans =
          1
          1

Column pivoting is used to eliminate variables from the constraint system when \ is specified, and when pinv is specified, an svd is used for the final solution.

• MATLAB release: MATLAB 7.3 (R2006b)
• Other requirements: Basic Matlab code - this should be accessible to most older releases.

[Lukas Malec]

Thank you. It's a very good work!

[Matt Ferrara]

Great code! Do you have any references on the approach you have implemented? (maybe you could put them in the documentation for release 3?)

[Greg]

Great piece of code! I do have a question? Is there a way to bound the results to be positive (i.e. x>0)?

[John D'Errico]

Greg - If you want to apply inequality or bound constraints, the simplest way is to use lsqlin from the optimization toolbox. That tool implements all forms of linear constraints.

[Michael Bevis]

I recently encountered a least squares problem with equality constraints that caused lsqlin to crash, but lse solved it nicely producing an excellent fit to the data vector, and obeying the constraints. Thanks, John!