3
$\begingroup$

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.

Active Set Method for Convex QP

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$?

|cite|improve this question|||||
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mark L. Stone Oct 6 '17 at 1:04
  • $\begingroup$ @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. $\endgroup$ – wyer33 Oct 6 '17 at 4:42
  • $\begingroup$ 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. $\endgroup$ – Mark L. Stone Oct 6 '17 at 12:56
  • $\begingroup$ 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. $\endgroup$ – Christian Clason Oct 9 '17 at 7:14
1
$\begingroup$

What breaks is typically that you can't prove any more that the method actually converges, as opposed to cycle between active sets.

I believe that Nocedal and Wright discuss this at least in passing, but I know that examples have been found in which the standard methods indeed cycle when one adds/subtracts more than one constraint at the time. I don't have a reference for that, but you should be able to find them in the literature.

|cite|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.