# What is the arithmetic cost (computational complexity) of an SDP with nonlinear matrix inequality constraint

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?

• For this specific problem, I guess the added inequaltiy constraint will not increase the complexity too much because I think it just narrows the search area of the decision variable $c$ into a new added subspace. I hope one can provide some evidences to support me, or tell me I am wrong:) – IronMan Jul 12 at 13:50