A BLOCK ACTIVE SET ALGORITHM FOR LARGE-SCALE QUADRATIC-PROGRAMMING WITH BOX CONSTRAINTS

An algorithm for computing a stationary point of a quadratic program w ith box constraints (BQP) is proposed. Each iteration of this procedur e comprises a guessing strategy which forecasts the active bounds at a stationary point, the determination of a descent direction by means o f solving a reduced strictly convex quadratic program with box constra ints and an exact line search. Global convergence is established in th e sense that every accumulation point is stationary. Moreover, it is s hown that the algorithm terminates after a finite number of iterations , if at least one iterate is sufficiently close to a stationary point which satisfies a certain sufficient optimality condition. The algorit hm can be easily implemented for sparse large-scale BQPs. Furthermore, it simplifies for concave BQPs, as it is not required to solve strict ly convex quadratic programs in this case. Computational experience wi th large-scale BQPs is included and shows the appropriateness of this type of methodology.