A symbolic algorithm for determining convexity of a matrix function: how to get Schur complements out of your life

Inequalities involving polynomials in matrices and their inverses and associated optimization problems have become very important in engineering. When these polynomials are “matrix convex” interior point methods apply directly. A difficulty is that often an engineering problem presents a matrix polynomial problem whose convexity takes considerable skill, time, and luck to determine. Typically this is done by looking at a formula and recognizing complicated patterns involving Schur complements; a tricky hit or miss procedure. Certainly computer assistance in determining convexity would be valuable. The paper describes some symbolic methods and software which represent a beginning along these lines. Our procedure proceeds automatically and completely avoids Schur complement wizardry. The paper presents an algorithm which takes in a noncommutative rational function Γ(X) of X and puts out a family of inequalities which determine a domain F of X´s on which Γ is “matrix convex”. Somewhat surprising and decidedly non-trivial is our main theorem showing that when the variable X is symmetric, that is X=X^T, then the domain G determined by our algorithm is, in a certain sense, the largest possible domain of matrix convexity for T. Of possible independent interest is a theory of positivity of noncommutative quadratic functions and a noncommutative LDU algorithm. The algorithms described have been implemented under Mathematica and the noncommutative algebra package NCAlgebra. Examples presented in the article illustrate some of this software