2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for answer! I will read it. Small question what do you think about QuickQP algorithm from alglib? (alglib.net/translator/man/…). Description says that it can make many "activations" during one iteration via constrained CG. But i cannot find any detailed description/analysis of this algorithm $\endgroup$ – Dark_Daiver Aug 31 '17 at 6:39
  • $\begingroup$ I don't know what they do, sorry. $\endgroup$ – Wolfgang Bangerth Aug 31 '17 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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