0
$\begingroup$

I am working on a resource allocation problem, which is convex and has several constraints, and I want to compare the computational complexity of the following algorithms.

1) The algorithm that uses iterative subgradient method through dual decomposition: It starts with initial values for dual variables and then, in each iteration, it finds the primal variables based on the dual variables and the Lagrangian function. Then it updates the dual variables using the subgradient of dual function (which is obtained using the primal variables in each iteration) and continues until the error between dual variables of two consecutive iterations is less than an epsilon. This algorithm takes a lot of iterations and has low convergence speed, which I think is mostly due to the fact that there are several dual variables.

2) A heuristic algorithm in which I divide the problem into convex subproblems with one constraint and use Golden Section search method for each of the subproblems. This algorithm has clear steps, e.g. O(NM), for dividing the main problem into subproblems and also the Golden section search for each of the subproblems converges very fast.

I need to show the difference of these algorithms in terms of complexity through simulations as well as theory. In theory, how can I compare the computational complexity of these algorithms? In other words, is there a systematic way as in the case of algorithms with fixed number of iterations (in which we say that for example one algorithm is O(XY) and the other is O(Ylog(X))) to show the difference in computational complexity?

Thanks in Advance.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The running time of the algorithm is the sum of its subcomponents. Thus, the complexity is the asymptotically worst case complexity of the subcomponents. Experimentally, you just run the algorithms at different problem sizes (or numbers of constraints, or both) and plot/fit the resulting data. You need to make sure that you run the problem out to a large enough size that you demonstrate that you're really in the asymptotic regime and not dominated by lower-order but bigger-constant terms.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for your answer. The thing is that the problem has 3 dimensional variables and I will need to increase the size of each dimension. However right now, even with small size of the dimensions, algorithm 1 takes a lot of iterations to converge. Therefore testing with the large numbers for each dimension even might not be possible due to very low convergence. Is there any bound for the convergence rate of the subgradient method? It might be possible to explain complexity by saying that it needs O(f(error)) iterations and each iteration has O(f(Y)) computations. $\endgroup$
    – Cror2014
    Commented Jan 11, 2015 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.