Quadratic Programming with Activesets

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.

Answer 1

[Matt J]

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.

[Quantum]

I agree with your statement. But my main question is regarding "how to". Can you please provide some reference/insight into how I can remove redundant constraints. A few pointers will work.

[Matt J]

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

http://www.mathworks.com/help/optim/ug/quadratic-programming-algorithms.html#bsqsqiy

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.