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.

  1. Introduction

  2. Definitions, notations, and abbreviations

  3. The Sherman-Morrison formula and related topics

  4. Domain of copositivity of a parametral matrix

  5. Connection between quadratic optimization and copositivity of parametral matrices

  6. A finite algorithm to the general quadratic programming problem (with a condition set given by its internal representation)

  7. Theoretical background for the finite algorithm

  8. Proof of Algorithm 6.1.

  9. Generalizations of the results for broader classes of proper parametral matrices

  10. Computational results