# Why do active set methods or the simplex method pivot only one variable at a time?

Why do active set methods or the simplex method pivot only one variable at a time? Ostensibly, we could add multiple columns to the basis during pivoting, but the standard presentation of the methods don't do this. Likely, something breaks, but I don't understand what.

If something more concrete would help, on page 472 of Numerical Optimization, we have the active set method for a convex QP in Algorithm 16.3.

Pivoting occurs in the choice of $j$ and and that single index $j$ entering the working set $W$. Why choose a single $j$? Couldn't we choose multiple indices that correspond to multiple negative multipliers $\lambda$?

• There are block active set methods which move multiple variables in or out of the active (working) set on each iteration. However, special measures may need to be put in place to prevent cycling. Oct 6 '17 at 1:04
• @MarkL.Stone Do you know of any good references for that? I did some more searching around and it looks like the complementarity folks do this with what are called block principal pivoting algorithms or just block pivoting algorithms. That's good enough to get me started, but certainly I'd like more references or an example of where a block pivoting algorithm cycles. Oct 6 '17 at 4:42
• I don't know of a good general reference. There are several journal articles, which might be behind paywalls, discussing specific algorithms.. I suggest googling. Oct 6 '17 at 12:56
• If you recompute the active set from scratch in every iteration, it is sometimes possible to interpret the active set strategy as a generalized (specifically, semismooth) Newton method and show convergence (i.e., non-cycling) via a contraction property. Oct 9 '17 at 7:14