Over at How many points to find a polynomial? it was suggested to minimize $$ f(a,b,c,d,e) = \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 .$$
However I don't know if it is possible to find an efficient method that is guaranteed to find a global optimum. Is this a convex function?
No, this is not a convex function, as you could find by trying, say, $(x_1,y_1)=(2,20)$, $c=e=0$, $a=1$, and $b$ in the range shown below. By the way, it should probably be $f(a,b,c,d,e) = \sum_{1 \le k \le n} (y_k - a x_k^b - c x_k^d - e)^2$.
Of course, the function is convex (quadratic) with respect to $a,c,e$. For any fixed $b,d$ you can find the minimizing $a,c,e$ by solving a linear system. This will give you a function of just two parameters $b,d$ which you can approach with some numerical method for non-convex minimization.
But even before that, I would plot the data $(x_k,y_k)$ and try to fit some function $ax^b+cx^d+e$ to it roughly, just by plotting various guesses for the exponents $b,d$. Then find $a,c,e$ from least squares. Chances are that this will yield more agreeable results than any sophisticated approach.