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?

  • $\begingroup$ 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:) $\endgroup$ – IronMan Jul 12 at 13:50

Your Answer

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

Browse other questions tagged or ask your own question.