Abstract

We study active set methods for optimization problems in Block Angular Form (BAF). We begin by reviewing some standard basis factorizations, including Saunders' orthogonal factorization and updates for the simplex method that do not impose any restriction on the pivot sequence and maintain the basis factorization structured in BAF throughout the algorithm. We then suggest orthogonal factorization and updating procedures that allow coarse grain parallelization, pivot updates local to the affected blocks, and independent block reinversion. A simple parallel environment appropriate to the description and complexity analysis of test procedures is defined in Section 5. The factorization and updating procedures are presented in Sections 6 and 7. Our update procedure outperforms conventional Updating procedures even in a purely sequential environment.