Description of algorithm for small scale linear least squares with box constraints

Question

I have small scale dense least squares problem with box constraints

$$\mbox{argmin}||Ax - b||^2 \quad $$ $$\mbox{subject to} \quad l_i \leq x_i \leq u_i,$$

Number of variables is about 10-50, several hundreds in worst case. Number of constraints is equal to number of variables. So i can factorize $A$ and/or $A^TA$. Also in my particular problem very often solution will "touch" only several "sides of box".

I understand that many modern numerical packages have functions to deal with such QP problem. What i seek is detailed description or paper of efficient algorithm (first of all in terms of speed and then accuracy) because i want to understand how it works and implement it by myself.

Currently i only found this paper based on active set. But it looks like (if i am not mistaken) it adds only one variable into "free" variables set per iteration which looks like not very effective for me.

Answer 1

You should take a look at the excellent book by Nocedal and Wright on "Numerical Optimization". It has a great deal of material on these kinds of problems.

The algorithm you refer to, where one only adds or subtracts one variable to the active set at a time is described in detail in the book. The reason for only adding or subtracting one variable at a time is that if you do more than one, one can come up with examples where the algorithm cycles without converging. There are, however, other methods (e.g., "primal-dual active set methods") that are more liberal in this regard.