In the book ''Interior-Point Polynomial Algorithms in Convex Programming'' (Nesterov and Nemirovskii) section 6.4, there is a computational complexity result for the general positive semi-definite problem
$ \text{minimize}\quad\sigma^{\top}\xi\quad \text{s.t.}\quad \xi \in \mathbb{R}^{n},\mathcal{A}(\xi)\in S_{\mu}^{+} $
where $\mathcal{A}(\xi)$ is a linear mapping from $\mathbb{R}^{n}$ into $S_{\mu}$. Then the computation cost of solving this problem is of order $O(1)\{n^{3}+n^{2}|\mu^{2}|+n|\mu^{3}|\}$.
So, for the linear mapping like $\pmatrix{Q&q\\q^{\top}&c}\succeq0$ in $(Q\succeq0,q\in\mathbb{R}^{m},c\in\mathbb{R})$, I can apply the result directly.
But, for the nonlinear matrix inequaltiy, how to use this result to analyze its complexity? For example, we need to solve the following problem
$ \text{minimize}\quad tr(\Sigma_{0}Q)+\sigma_{0}^{\top}q+\gamma c\quad \text{s.t.}\quad \pmatrix{Q&q\\q^{\top}&-c^{2}}\succeq0$
Maybe, one way to handle it is to reformulate the original problem as $ \text{minimize}\quad tr(\Sigma_{0}Q)+\sigma_{0}^{\top}q+\gamma c\quad \text{s.t.}\quad \pmatrix{Q&q\\q^{\top}&-\phi}\succeq0,\quad\phi\geq c^{2}.$
I add an inequality. Is there any effect on the complexity?