Matrix inequalities: A symbolic procedure to determine convexity automatically (Q1402354)

This paper describes algorithms, and the theory behind them, for determining regions on which noncommutative rational functions are matrix convex or matrix positive. The algorithms where implemented in NCAlgebra (a Mathematica-package) and many examples of their use are presented. In Part I (ca. 25 pages) the style is deliberately choosen to be readable by professionals from the engineering sciences where inequalities involving polynomials in matrices and their inverses, and associated optimization problems have become very important; matrix convexity in particular for the application of interior point methods. Part II (remaining 30 pages) is dedicated to theoretical results and proofs. Let \(\vec{A}=\{A_1,\ldots, A_m\}, \vec{X}=\{X_1,\ldots, X_k\}\) be noncommutative variables, \(\Gamma(\vec{A},\vec{X})\) be a noncommutative rational function to be analyzed; for example \(\Gamma(A,D,E;X,Y)= A(I+DXD^T)^{-1}A^T+E(YXY^T)E^T,\) \(X=X^T,\) where superscript \(T\) denotes an involution. In practice \(\vec{A}\) represents known matrices, \(\vec{X}\) unknowns ones, and superscript \(T\) transposition. Notation will be simplified often by suppressing \(\vec{A},\) (so that writing \(\Gamma(X)\) makes sense) and by defining \(\vec{Z}=(\vec{A},\vec{X}).\) Directional derivatives \(D\Gamma(\vec{X})[\vec{H}]= \lim_{t\rightarrow 0}\frac{1}{t}(\Gamma(\vec{X}+t\vec{H})-\Gamma(\vec{X}))\) and the Hessian \({\mathcal Q}(\vec{Z})[\vec{H}]={\mathcal H}\Gamma(\vec{X})[\vec{H}]=\frac{d^2}{dt^2}\Gamma (\vec{X}+t\vec{H})| _{t=0}\) are defined largely as usual. Note that the Hessian is quadratic in \(\vec{H}.\) A formal expression \({\mathcal G}_\rho :=\{\vec{Z}:\rho_j(\vec{Z})\geq 0, j=1,\dots, r\}\) is called a symbolic inequality domain (SID). \({\mathcal M}({\mathcal G}_\rho)\) is the set of all matrix(!)-tuples \(\vec{Z}\) yielding positive semidefinite matrices \(\rho_j(\vec{Z}),\) \(j=1,\dots,r.\) A noncommutative rational function \(Q(\vec{Z})[\vec{H}]\) quadratic in \(\vec{H}\) is called matrix positive quadratic on SID \(\;{\mathcal G}_\rho,\) provided it is a positive semidefinite for all matrix tuples \(\vec{H},\) whenever one chooses matrix-tuple \(\vec{Z}\) in \({\mathcal M}({\mathcal G}_\rho).\) Function \(\Gamma(\vec{A}, \vec{X})\) is said to be matrix convex w.r.t. \(\vec{X}\) on SID \(\;{\mathcal G}_\rho,\) provided \({\mathcal H}\Gamma(\vec{X})[\vec{H}]\) is a positive semidefinite matrix for all \(\vec{H}\) and all \(\vec{A},\vec{X}\) in \({\mathcal M}({\mathcal G}_\rho).\) To convey more of the mathematics involved, we mention the following: a. a representation theorem for noncommutative rational functions quadratic in \(\vec{H};\) b. a theorem for a noncommutative LDU algorithm: a symmetric \(r\times r\) matrix with noncommutative rational function entries can be factored in the form \(LDL^T,\) where \(L\) is lower triangular, and \(D\) is 'roughly' diagonal; c. results on the codimension of subspaces of form \(S=\{[(Hv_1)^T, \dots (Hv_l)^T]^T: H \text{ symmetric real }n\times n\) matrix