4
$\begingroup$

I've written a C# solver for linear least squares problems with inequality constraints. That is, given $A$, $b$, $G$, $h$

$$\min\|Ax-b\|^2\text{ s.t. }Gx\ge h$$

I have a few hand crafted test problems that my solver gives the correct answer for, and now I'd like to throw a gauntlet of randomly generated problems of various ranks at it to make sure there aren't any edge cases I'm missing.

So what I need is a way to determine that a given $b$ vector calculated satisfies the constraints $Gx \ge h$ (which is easy to check for) and that the solution vector can't be improved by perturbing it in a given non-constrained direction. The second part is what I'm at a loss for.

  • 0
    Do you mean "a given $x$ vector" satisfies $Gx \geq h$?2011-10-18
  • 0
    Yeah. The idea is that you're trying to find $x$ given some "hard" constraints and "soft" suggestions.2011-10-18
  • 0
    Why don't you compare the solution your code gives to one from a mature linear algebra library, e.g. [this one](http://en.wikipedia.org/wiki/Galahad_library)?2012-02-16
  • 0
    I'd like to but I couldn't ever find an actual implementation of a solver for this specific problem. I can't tell if the one you link has one. Of course, even if it does, I have to write the bridge code to let me use the fortran libraries from C#, which is a lot of work :/2012-02-17
  • 0
    How did you solve the problem? What method the solver use?2017-02-21
  • 0
    @Royi: Do you mean how did I test for optimality, or how did I write the solver? If for optimality, I put it on hold and went to other problems. If you mean how did I write the solver, you can take a look at my code here: http://svn.darwinbots.com/Darwinbots3/Trunk/Modules/Azimuth/Azimuth/DenseLinearAlgebra/ConstrainedLeastSquares.cs. There's a few abortive attempts in there that are commented out, but the LSI code at the top is what I'm using. The algorithm is from "Solving least squares problems" by Lawson and Hanson. It transforms the problem in to non negative LS and solves that.2017-02-22
  • 0
    Better than code, where is the theoretical background of your solver? Thank You.2017-02-22
  • 0
    @Royi: It's from "Solving least squares problems" by Lawson and Hanson. ISBN 978-0-898713-56-5. Chapter 23: "Linear least squares with linear inequality constraints". It transforms this problem ("Problem LSI") in to a non-negative least squares problem ("problem NNLS"), for which it provides a pivoting algorithm. NNLS here just means a least squares problem where x >= 0. There are other ways to solve the problem, I'm sure. I think there's a transformation in to linear complimentary problem (LCPs), for instance. But I could never get a robust pivoting solver for those working.2017-02-22
  • 0
    I see. I don't have access to this book and I'm looking for a source which describes how to solve it. I could write the dual form which indeed has a form of OLS with Non Negativity Constrain.2017-02-22
  • 0
    @Royi I don't think you'll find a good source without buying a book. Believe me I've looked. Most of the research on pivoting methods was done in the 70s or earlier, and most of it's not online. In contrast, if you wanted to do an interior method, there's lots of resources online around conjugate gradient and gradient descent.2017-02-22
  • 0
    This is the best source I've found that's free: http://infolab.stanford.edu/pub/cstr/reports/cs/tr/69/134/CS-TR-69-134.pdf2017-02-22
  • 0
    I see. I'm not talking specifically about Pivoting but just how to solve Linear Least Squares with Inequality Constraints.2017-02-23
  • 0
    @Royi: Outside my sphere of knowledge. But maybe this will get you pointed in the right direction: http://www2.esm.vt.edu/~zgurdal/COURSES/4084/4084-Docs/LECTURES/GradProj.pdf2017-02-23
  • 0
    @JayLemmon, by the way, Maybe it can be solved easily using Augmented Lagrangian or Penalty Method.2017-02-23
  • 0
    @JayLemmon, See here: https://ipvs.informatik.uni-stuttgart.de/mlr/marc/teaching/13-Optimization/03-constrainedOpt.pdf2017-02-23
  • 0
    Another nice source: https://www.cs.ubc.ca/~schmidtm/MLSS/constrained.pdf2017-02-23
  • 0
    Note to myself - Add full solution.2017-09-04

2 Answers 2