Complexity analysis using CVX


(Radhika Gour) #1

As part of my research, I am currently dealing with a convex program whose objective function involves the maximization of the Shannon capacity (function of power needs to optimized) subject to affine inequality constraints and a positivity constraint.

I am solving it using SeDuMi solver. That is using Successive Approximation method.

How can i know the computational complexity in terms of Big O.
Any help with this matter would be greatly appreciated!


(Michael C. Grant) #2

I get this question a lot, and I’m afraid I can’t be of any help. But I question the wisdom of even trying to offer a complexity analysis by studying the successive approximation method. It was not designed with any sort of academic study in mind; it was a hack, developed in the hopes it would sometimes work, and luckily, it does. That doesn’t seem like the kind of algorithm that ought to be offered as an example of the “right way to do things” in any sort of academic paper.


(Radhika Gour) #3

Thank you Sir for your reply. I also studied that log, exp, entropy type functions in CVX implemented using successive approximation method which can be slow , unreliable. can I use another method for solving such kind of functions?


(Mark L. Stone) #4

Use CVX 3.0.beta with
ECOS solver (2nd order, but can not handle SDPs)
or
SCS solver (1st order, and can handle SDPs).

In both cases, CVX makes use of the native exponential cone support in the solver, thereby avoiding the successive approximation method.


(Radhika Gour) #5

Thank you so much sir, I will try this.