This is a convex function of a single variable, so a derivative free search method such as Golden Section search will converge without problems. These methods all converge linearly, but they don't move along corners. The effort per function evaluation is $O(n)$.
