Maximizing a convex function with a linear constraint
Yes, Convex Optimization with equality constraint is NP-Hard in general. However, there exist mature techniques that find very nice approximate solutions to convex optimization problems, like Coordinate Descent. 

Suppose you use coordinate descent and the matrix A has rank $k$. You can fix n-k-1 coordinates of your feasible solution $x = (x_1, x_2, x_3, ..., x_n)$ and then the solution vectors in the solution space are uniquely determined by one coordinate, for example $x_i$. In that case, you can just take the derivative of $f(\cdot)$ with respect to $x_i$ to find the maximum in this iteration. 

Then we iteratively fix n-k-1 coordinate and improve the solution until a approximately optimal one is found.