Timeline for mixed semi definite and second order programming complexity order
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 9, 2014 at 7:20 | vote | accept | user51780 | ||
| Jul 25, 2014 at 18:49 | answer | added | Cristóbal Guzmán | timeline score: 2 | |
| Jul 23, 2014 at 16:40 | comment | added | Cristóbal Guzmán | I think you will see it once you write your problem in standard form (meaning that you convert the norm into a second-order cone constraint). I can write it down later if you want, but let me warn you that the complexity upper bound you wrote above should also depend on $A$, $A^{\prime}$. | |
| Jul 23, 2014 at 7:52 | comment | added | user51780 | Thank you very much for your comment. To clarity, consider the following standard semi definite programming: [\begin{array}{l} \mathop {{\rm{min}}}\limits_{\bf{X}} & {\rm{Tr}}\left( {{\bf{XA}}} \right)\\ {\rm{s}}{\rm{.t:}} & {\rm{Tr}}\left( {{\bf{XA'}}} \right) = a\\ & {\bf{X}} \ge {\bf{0}} \end{array}] the worst case complexity of the above problem is given by ${\cal O}\left( {\sqrt M \log \left( M\right)\log \left( {M/\varepsilon } \right)} \right)$. I want to know how can I calculate the complexity of mixed semi definite and second order programming. | |
| Jul 22, 2014 at 20:20 | comment | added | Cristóbal Guzmán | What do you mean by order of complexity? In any case, it might help you to write the norm constraint in (second order) conic form, which will lead to only linear equality constraints + semidefinite + second order cone constraints. | |
| Jul 22, 2014 at 18:40 | history | asked | user51780 | CC BY-SA 3.0 |