Computational complexity of maximising a concave function over a convex set

Question

Consider the following optimisation problem:

$$\max_{u\in \mathcal{B}} f(u)$$ where $\mathcal{B}$ is a convex set and $f$ is a concave function. The book says: "This problem is computationally tractable and several efficient algorithms in convex programming are available to solve it; see, for example, the MatLab software for disciplined convex programming CVX."

My question is about the computational complexity of solving this problem. Does the sentence above means that the problem can be solved in polynomial time?

Answer 1

Bubeck's book has a table on page 243 (page 16 of the pdf): https://api.semanticscholar.org/CorpusID:207179138

For example, for projected gradient descent if the function is Lipshitz continuous we need $O(1/\epsilon^2)$ iterations to achieve $\epsilon$ error.