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?


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.


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.