Almost all optimization algorithms work
Since we are dealing with real numbersnumber computation, so we cannot use the traditional Turing machine model of for complexity analysis. There is will always be some $\epsilon$ \epsilon$s lurking in there.
That said, there are a few different when analyzing optimization algorithms, several approaches exist:
Now(analyzing rate of convergence near an optimum)
A very popular, and in fact very useful model is approach 2: information based complexity. This, is probably the closest to what you have in mindis the information based complexity model, pioneered by and it starts with the pioneering work of Nemirovksii and Yudin.
The complexity depends on the structure of the convex function: Lipschitz continuous gradients help, strong convexity helps, a certain saddle point structure helps, and so on.Even if your convex function is not differentiable, then depending on its structure, different results exist, and some of these you can chase by starting from Nesterov's "Smooth minimization of nonsmooth functions" cited by Brian in his answer.
But for the sake of clarity, I will provide just one example illustrate below the simplest upper-bound on the (information based) complexity of gradient descent. The This complexity is worse than the lower bound (optimal methods that attain this do exist). In any case, the references cited will help you study this subject in much greater detail.