# Convex matrix optimization with a linear constraint on the inverse

Given a real matrix $A$ and a vector $v$, does anyone know the solution to the following optimization problem?

$$\begin{array}{ll} \text{supremize} & \mbox{Tr} (A^t X)\\ \text{subject to} & v^t X^{-1}v \leq 1\end{array}$$

where $X$ is a real symmetric positive definite matrix.

This is a convex problem, but the domain is not closed, which complicates a bit the situation.

Using the Schur complement test for positive semidefiniteness, the given problem can be rewritten as

$$\begin{array}{ll} \text{supremize} & \langle \mathrm A , \mathrm X \rangle\\ \text{subject to} & \begin{bmatrix} \mathrm X & \mathrm v\\ \mathrm v^\top & 1\end{bmatrix} \succeq \mathrm O_{n+1}\\ & \mathrm X \succ \mathrm O_n\end{array}$$

Using $\mathrm X \succeq \mathrm O_n$ instead of $\mathrm X \succ \mathrm O_n$, we obtain the following semidefinite program (SDP)

$$\begin{array}{ll} \text{maximize} & \langle \mathrm A , \mathrm X \rangle\\ \text{subject to} & \begin{bmatrix} \mathrm X & \mathrm v\\ \mathrm v^\top & 1\end{bmatrix} \succeq \mathrm O_{n+1}\\ & \mathrm X \succeq \mathrm O_n\end{array}$$

If the optimal $\rm X$ is positive definite, then we have solved the original problem.

• Thanks, this may be helpful. Since I am interested in a formula for the value of the sup only, the SDP will work even if the optimal X is degenerate. – alesia Aug 4 '17 at 0:35
• The calculation is messier than I thought but it seems indeed to work in the end. Thanks again! – alesia Aug 4 '17 at 3:30

If $A$ is positive definite, you can make $\operatorname{Tr}(A^tX)$ as big as you like by taking $X$ to be a huge multiple of the identity matrix.

In any case $A$ might as well be symmetric, and hence the difference of 2 p.s.d. matrices. Maybe you can then take $X$ to look like a huge multiple of the identity restricted to the subspace where $A$ looks p.s.d., to the same effect?