The Sherman-Morrison formula for the determinant and its application for optimizing quadratic functions on condition sets given by extreme generators

G. Kéri

Computer and Automation Institute

Hungarian Academy of Sciences

Budapest, Hungary

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.