# Testing constrained linear least squares for optimality

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.

-
Do you mean "a given $x$ vector" satisfies $Gx \geq h$? – Mike Spivey Oct 18 '11 at 18:29
Yeah. The idea is that you're trying to find $x$ given some "hard" constraints and "soft" suggestions. – Jay Lemmon Oct 18 '11 at 18:56
Why don't you compare the solution your code gives to one from a mature linear algebra library, e.g. this one? – Chris Taylor Feb 16 '12 at 7:44
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 :/ – Jay Lemmon Feb 17 '12 at 17:49

You want the KKT conditions of the problem; since it is convex, a given $x$ is a minimizer if and only there exists Lagrange multipliers $\lambda$ such that \begin{align*}A^TAx - A^T b - G^T\lambda &= 0\\ Gx-h &\geq 0\\ \lambda &\geq 0\\ \lambda^T (Gx-h) &= 0\end{align*}.
I'm not completely sure of the best way of finding a $\lambda$ certifying the above or of proving one doesn't exist; you can start by using the last equation to split the constraints into an active set ($G_ax-h_a=0$, $\lambda_a \geq 0$) and inactive set $(G_i x - h_i > 0, \lambda_i = 0)$, and deleting the inactive constraints from the above equations. If $A^TA$ is invertible you can then directly solve for $\lambda_a$ and check if all entries are nonnegative. If $A^TA$ is singular I'm not sure how best to proceed; maybe another answer will elaborate.
That's more or less the way I'm solving the system right now, yeah. I have $\lambda$, and from that I can calculate $x$. I guess I could test those 4 conditions from the KKT directly. But I was hoping for a method (maybe something calculus based) that wasn't so closely coupled with how I solved the problem in the first place. – Jay Lemmon Oct 18 '11 at 21:10