The Sherman-Morrison formula for the determinant and its application for optimizing quadratic functions on condition sets given by extreme generators
Computer and Automation Institute
Hungarian Academy of Sciences
Abstract: First a short survey is made of formulas, which deal with either the inverse, or the determinant of perturbed matrices, when a given matrix is modified with a scalar multiple of a dyad or a finite sum of dyads. By applying these formulas, an algorithmic solution will be developed for optimizing general (i.e. nonconcave, nonconvex) quadratic functions on condition sets given by extreme generators. (In other words: the condition set is given by its internal representation.) The main idea of our algorithm is testing copositivity of parametral matrices. Finally, results of computational experiences will also be reviewed.
Keywords: copositive matrix, determinant calculus, extreme generator, matrix inversion, matrix perturbation, optimization, parametral matrix, quadratic programming.
Definitions, notations, and abbreviations
The Sherman-Morrison formula and related topics
Domain of copositivity of a parametral matrix
Connection between quadratic optimization and copositivity of parametral matrices
A finite algorithm to the general quadratic programming problem (with a condition set given by its internal representation)
Theoretical background for the finite algorithm
Proof of Algorithm 6.1.
Generalizations of the results for broader classes of proper parametral matrices