Convexity Conditions of Kantorovich Function and Related Semi-infinite Linear Matrix Inequalities

The Kantorovich function $(x^TAx)( x^T A^{-1} x)$, where $A$ is a positive definite matrix, is not convex in general. From a matrix or convex analysis point of view, it is interesting to address the question: When is this function convex? In this paper, we prove that the 2-dimensional Kantorovich function is convex if and only if the condition number of its matrix is less than or equal to $3+2\sqrt{2}. $ Thus the convexity of the function with two variables can be completely characterized by the condition number. The upper bound `$3+2\sqrt{2} $’ is turned out to be a necessary condition for the convexity of the Kantorovich function in any finite-dimensional spaces. We also point out that when the condition number of the matrix (which can be any dimensional) is less than or equal to $\sqrt{5+2\sqrt{6}}, $ the Kantorovich function is convex. Furthermore, we prove that this general sufficient convexity condition can be improved to $2+\sqrt{3} $ in 3-dimensional space. Our analysis shows that the convexity of the function is closely related to some modern optimization topics such as the semi-infinite linear matrix inequality or `robust positive semi-definiteness’ of symmetric matrices. In fact, our main result for 3-dimensional cases has been proved by finding an explicit solution range to some semi-infinite linear matrix inequalities.

Article

Download

View PDF