Quadratic Programming with Activesets
3 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
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 comentarios
Respuestas (1)
Matt J
el 17 de Dic. de 2013
Editada: Matt J
el 17 de Dic. de 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 comentarios
Matt J
el 17 de Dic. de 2013
Editada: Matt J
el 17 de Dic. de 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.
Ver también
Categorías
Más información sobre Quadratic Programming and Cone Programming en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!