Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer
    
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
    
But when the problem and constraints are convex, as in your problem, satisfying the KKT conditions is proof of optimality -- why look for other criteria (and, of course, these equations are Calculus-based; they're essentially "take the derivative and set it equal to zero.") –  user7530 Oct 18 '11 at 21:19
    
It's partly numerical issues. The KKT involve a lot of multiplications for things that are supposed to cancel out and hit 0. It's also partly that everything is my own code and I'm trying to find ways to test it that touch as many areas of the code base as possible. –  Jay Lemmon Oct 18 '11 at 21:33
    
What method are you using to solve the problem? As for testing for optimality, the KKT conditions are the way to go. –  Dominique Oct 29 '11 at 14:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.