Accession Number : ADA188049

Title :   A Schur-Complement Method for Sparse Quadratic Programming.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB

Personal Author(s) : Gill, Philip E ; Murray, Walter ; Saunders, Michael A ; Wright, Margaret H

PDF Url : ADA188049

Report Date : Oct 1987

Pagination or Media Count : 25

Abstract : In applying active-set methods to sparse quadratic programs, it is desirable to utilize existing sparse-matrix techniques. The authors describe a quadratic programming method based on the classical Schur complement. Its key feature is that much of the linear algebraic work associated wtih an entire sequence of iterations involves a fixed sparse factorization. Updates are performed at every iteration to the factorization of a smaller matrix, which may be treated as dense or sparse. The use of a fixed sparse factorization allows an off-the shelf sparse equation solver to be used repeatedly. This feature is ideally suited to problems with structure that can be exploited by a specialized factorization. Moreover, improvements in efficiency derived from exploiting new parallel and vector computer architectures are immediately applicable. An obvious application of the method is in sequential quadratic programming methods for nonlinearly constrained optimization, which require solution of a sequence of closely related quadratic programming subproblems. Some ways in which the known relationship between successive problems can be exploited are discussed. Keywords: Supercomputers; Variables; Computations.

Descriptors :   *QUADRATIC PROGRAMMING, ALGEBRA, COMPUTATIONS, COMPUTER ARCHITECTURE, EQUATIONS, ITERATIONS, OFF THE SHELF EQUIPMENT, PARALLEL PROCESSORS, SEQUENCES, SEQUENTIAL ANALYSIS, SUPERCOMPUTERS, SPARSE MATRIX

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE