Given a problem like this:

$$ \text{min } ||Ex-f|| \text{ s.t.}$$ $$ Gx \ge 0$$ $$ Cx = d $$

And assuming that the matrices are medium sized (dimensions in the low thousands) and dense, what's the state-of-the-art for solving this system (imagine for use in a real time system)? Preferably using something like an active set algorithm instead of gradient descent.

I have some classic books (eg: Numerical Methods for Least Squared Problems and Solving Least Squares Problems) that list some algorithms, but they're decades old, concentrate on algorithms for simpler problems (with conversions from the more complex form) and tend to only gloss over important details like storage, cache use, and numerical considerations.

There's some resources on the quadratic programming side (eg: quadprod in Matlab). I've ordered the "Practical Optimization" book (listed in the footnotes for quadprod) to see what sort of methods it has. But again, it's from the 80s.

Most google searches provide hits for recent research, but they tend to concentrate on either large sparse systems, interior point methods like gradient descent, or both.

So I'm curious what methods are considered modern for dense active-set style algorithms?


1 Answer 1


Read through the book "Numerical Optimization" by Nocedal and Wright to understand how active set methods work in general. The more modern variations use the primal-dual method by Kunisch et al. to predict which constraints will/will not be active.

  • $\begingroup$ When you say Kunsich et al., do you mean this one: dl.acm.org/citation.cfm?id=636324? $\endgroup$
    – Jay Lemmon
    Commented Jul 16, 2014 at 17:07
  • $\begingroup$ I believe that he wrote a great many papers on the topic. This is one. $\endgroup$ Commented Jul 17, 2014 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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