Runtime complexity of successive approximation method

1

As part of my research, I am currently dealing with a convex program whose objective function involves the maximization of the entropy of a random variable (and hence is part of the exponential family of functions) subject to affine equality constraints and a positivity constraint.

I am trying to precisely establish the following quantities:
a> cost per iteration as a function of the problem size,
b>number of iterations necessary to achieve a solution within a fixed tolerance as a function of the problem size.

Is there a reference where I can better understand the successive approximation method to answer these questions? I can also post the exact problem if that is something that will help with getting answers to a> and b>.

Any help with this matter would be greatly appreciated!

2

I’m afraid I can’t be of much help. I never developed this method academically. I just implemented it to see if it worked reasonably well, and it did.

3

Thanks for the response. May I ask how exactly you implemented the polynomial approximation of the log/exp function? That might help with getting an idea of the cost per iteration at least.

4

There is actually a block comment starting in line 125 of lib/@cvxprob/solve.m that represents pretty much all of the documentation I have on the subject :wink:

1 Like
5

Thanks! I think that pretty much gives me a good idea of what is going on.