Quadratic Programming with Activesets
3 views (last 30 days)
Show older comments
Hi, I have a question regarding the description of Activeset based Quadratic programming as described here: http://www.mathworks.com/help/optim/ug/quadratic-programming-algorithms.html#brozzpo.
It is not clear how the constraints are handled. In general, the number of constraints can turn out to be more than the number of variables (they can be redundant), if we combine the bounds, inequality and equality constraints. Can someone give me some pointers on how to simplify the constraints?
1. For equality constraints, I can use Gauss-Elimination (not sure if it is the optimal way of doing it). 2. For inequality constraints, I was reading that Fourier-Motzkin Elimination can be used, but it ends up creating more constraints than in the original system. 3. Can I carry out Gauss-Elimination on the Activeset (all active constraints combined)? My main problem is that if I do Gauss-Elimination, I will lose track of the correspondence with the Lagrange Multipliers, as mentioned in Eq (6-95).
All references I have read assume that the number of constraints is less than the number of variables. How to get there is not clear to me. I will appreciate any help. Thank you.
0 Comments
Answers (1)
Matt J
on 17 Dec 2013
Edited: Matt J
on 17 Dec 2013
I haven't delved into the documentation that you've cited, but I think the idea is that only the number of active constraints must be less than the number of variables. Otherwise, you surely have redundant constraints.
2 Comments
Matt J
on 17 Dec 2013
Edited: Matt J
on 17 Dec 2013
I doubt you have to do this manually. It says in the link you posted that the interior-point algorithm has a pre-processing step to remove redundant constraints
Hard to imagine that active-set wouldn't do the same if it is sensitive to this, even if the documentation doesn't mention it explicitly.
I would also mention that active-set methods are intended for problems with a small number of constraints, where this normally isn't an issue. Even forgetting about redundancy for a moment, the algorithm will be very burdened computationally and convergence-wise if you have lots of constraints.
See Also
Categories
Find more on Quadratic Programming and Cone Programming in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!