A Combinatorial Active Set Algorithm for Linear and Quadratic Programming

Andrew J. Miller (1, 2)

1 IMB - Institut de Mathématiques de Bordeaux
2 Realopt - Reformulations based algorithms for Combinatorial Optimization

We propose an algorithm for linear programming, which we call the Sequential Projection algorithm. This new approach is a primal improvement algorithm that keeps both a feasible point and an active set, which uniquely define an improving direction. Like the simplex method, the complexity of this algorithm need not depend explicitly on the size of the numbers of the problem instance. Unlike the simplex method, however, our approach is not an edge-following algorithm, and the active set need not form a row basis of the constraint matrix. Moreover, the algorithm has a number of desirable properties that ensure that it is not susceptible to the simple pathological examples (e.g., the Klee-Minty problems) that are known to cause the simplex method to perform an exponential number of iterations. We also show how to randomize the algorithm so that it runs in an expected time that is on the order of mn^{2 log n} for most LP instances. This bound is strongly subexponential in the size of the problem instance (i.e., it does not depend on the size of the data, and it can be bounded by a function that grows more slowly than 2^m, where m is the number of constraints in the problem). Moreover, to the best of our knowledge, this is the fastest known randomized algorithm for linear programming whose running time does not depend on the size of the numbers defining the problem instance. Many of our results generalize in a straightforward manner to mathematical programs that maximize a concave quadratic objective function over linear constraints (i.e., quadratic programs), and we discuss these extensions as well.

Domaines: Recherche opérationnelle [math.OC]

Andrew J. Miller. A Combinatorial Active Set Algorithm for Linear and Quadratic Programming. 2009. ⟨hal-00387108⟩