Why cvx requires very few iterations steps to reach a high accuracy?

(Haobo Li) #1

Hi, I am new on cvx and I am not also an expert in optimization theory. I notice that if I put a convex optimization problem into cvx, the cvx only requires about 20 iterations to reach an accuracy of 10^-8. For the same problem I wrote an algorithm which has a geometry convergence performance and when I run the algorithm, it usually takes several hundred iterations to reach 10^-8 accuracy. So why is cvx so “iteratively” efficient?
Another thing is, although cvx takes few iteration steps to reach high accuracy, it seems it usually takes a long time to finish, i.e. the CPU time in each iteration step is very long, so what did cvx do during this long time? Still for the same optimization problem, my own algorithm takes 0.001 seconds with 200 iterations to finish while cvx takes 1 seconds with 20 iterations to finish. So I wonder what takes cvx so long in each iteration step?

(Mark L. Stone) #2

What you are describing is generally characteristic of the second order interior point algorithms in the solvers called by CVX. However, first order solvers, such as SCS, which can be called by CVX 3.0beta (not recommended due to CVX 3.0’s bugginess) usually require a very large number of fast executing per iteration iterations, and only achieve linear convergence.

(Haobo Li) #3

Thank you! You made it quite clear.