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.

  • $\begingroup$ 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. $\endgroup$ – alesia Aug 4 '17 at 0:35
  • 1
    $\begingroup$ The calculation is messier than I thought but it seems indeed to work in the end. Thanks again! $\endgroup$ – 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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.