1

In the active-set optimisation method (especially quadratic programming), when we found multiple Lagrangian multipliers are negative at the stationary point, why couldn't we delete all of the corresponding constraints rather than deleting just one (usually the most negative one) of such constraints?

user112758
  • 287
  • 1
  • 7

1 Answers1

1

You are able to remove and add multiple constraints per iteration without loss of correctness. Regarding why, a constraint can have a positive lagrange multiplier if it does not reside in the final active set, but a constraint will never have a negative lagrange multiplier if it does reside in the final active set.

I've implemented an inequality constrained quadratic programming solver that uses the active set method, and multiple constraints can be removed or added in multiple stages of the algorithm. Consider the above observation about lagrange multipliers, and how the algorithm never needs to correct itself after removing 'too many' negative lagrange multiplier constraints.

  1. Start from an arbitrary feasible point. Your initial active set is all equality constraints (always active) and you may add all inequality constraints that are active at the your initial point. If you do not add all active inequality constraints, they will likely be added in the first few iterations of the algorithm.
  2. Solve the ECQP defined by your active set.
  3. Remove all dependent constraints. Make sure equality constraints are removed only if they are dependent relative to other equality constraints. This step can remove more than one constraint from the active set. The algorithm is still correct if you only remove one of these constraints per iteration. Go to step 2.
  4. If the optimum of the ECQP violates and of the inequality constraints that are outside the active set, move from the previous feasible point (the optimum of the previous iteration or the initial arbitrary point) to the new infeasible point until you reach a constraint. You may reach multiple constraints at once, in which case you can 'bind' to all of them (add them all to the active set). The algorithm is still correct if you only add one binding constraint per iteration. If the previous feasible point resided on active constraints that were not in the active set, they will be added by this step. Go to step 2.
  5. All constraints with non-positive lagrange multipliers can be removed. In my implementation I chose to remove all constraints with negative lagrange multipliers, leaving those with zero valued lagrange multipliers. Again, the algorithm is correct if only one constraint is removed per iteration in this step. If any lagrange multipliers were negative (either removed or still in the active set) go to step 2.
  6. If the entire active set has non negative lagrange multipliers, your optimum is a solution to the problem. If you still have constraints with zero valued lagrange multipliers, they can be removed from the active set (this is important if your final solution is not a point.

I studied the linked lecture to learn this. For anyone looking for an in-depth description and example of solving an ICQP with the active set method, I recommend this video, and the preceding and following videos in the series.

RGB mathematics Lecture 19: Inequality-constrained Quadratic Programming (IQP) https://www.youtube.com/watch?v=bVN7gNFlSPA

user1920703
  • 36