Can $\mbox{tr}(AX) \leq \frac{\mbox{tr}(\Omega BXB)}{\mbox{tr}(BXB)}$ be reduced to known programs?

62 Views Asked by At

Assume all the matrices mentioned below are in $\mathbb{R}^{n\times n}$ and symmetric. Also, below, $M \preceq N$ denotes that all eigenvalues of $N-M$ are non-negative.

Given $0\preceq A, B\preceq I$, find $\Omega$ with the minimal trace, such that $$\mbox{tr} (AX) \leq \frac{\mbox{tr} (\Omega BXB)}{\mbox{tr}(BXB)}$$ for all $X$ where $X \succeq 0$ and $\mbox{tr}(X) = 1$. One trivial feasible solution is $\Omega=I$. Can this problem be reduced to any known programming problems, e.g., LP or SDP?

The difficulty, I think, lies in the degree of $X$ on both side are not the same. If the LHS is a constant $c$, then it is equivalent to $cB^2 \preceq B\Omega B$ which is a semidefinite program (SDP).


Motivation

This question stems from (section 5 of) one paper$^\color{red}{\star}$ I am reading which requires preliminaries (about quantum computation and verification of programs). It is about generating multiplicative invariants of programs.


$\color{red}{\star}$ Mingsheng Ying, Shenggang Ying, Xiaodi Wu, Invariants of quantum programs: characterisations and generation, Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, January 2017.