Hi there, I'm coming to this from a practitioner's point of view. Your question as to whether non-convex optimization is always heuristically driven can be answered as follows:
No.
There are many gradient-based techniques for nonconvex global optimization out there that DO NOT rely on any heuristics at all. They are usually based on partitioning the solution space, and performing some sort of branch and bound search and using tight convex relaxations (the tightest relaxations obtainable for nonlinear functions are McCormick relaxations). But as As mentioned, these algorithms have a worst case exponential complexity, but they are rigorous (non-heuristic) and are able to give you a provably global solution.
Global nonconvex optimization is an active area of research: http://www.mat.univie.ac.at/~neum/glopt/techniques.html#branch
The well-known BARON software for instance, can rigorously find the global optimum of a nonlinear nonconvex problem.
Other software/algorithms include:
LaGO https://projects.coin-or.org/LaGO
Couenne https://projects.coin-or.org/Couenne
There are papers published
Papers that provide mathematical details for all the above solvers can be found in the open literature.
Practitioners in this area have come to realize that general procedures for finding the global solution to a general nonconvex problem are usually NP-hard (so far no exceptions have been found).
A special case of this can be seen in polynomial programming, where a nonconvex polynomial optimization problem can be solved by decomposing it its KKT (optimality) conditions into its Groebner basis. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.6266
On the surface, this looks attractive because it would seem that any nonconvex optimization problem can then be approximated as a polynomial programming problem by taking its Taylor expansion. However, the computation of Groebner bases is NP-hard.
Hope
I hope that gives you a few leads.
