There is a huge class of non-linear problems where gradient descent (with line search) is guaranteed to find the global optimum: Convex optimization problems.

There is a huge class of non-linear problems where gradient descent (with line search) is guaranteed to find the global optimum: Convex optimization problems. And within convex problems there is a hierarchy of "difficulty": LP ⊂ QP ⊂ SOCP ⊂ SDP The Simplex algorithm solves only LP. And it was shown that the Simplex has an exponential worst-case runtime (in the number of constraints). Whereas interior-point methods (basically variations of Gradient Descent) have a much better worst-case runtime. See here for further reference: http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf