There is likely an unclear assumption: The optimization problem is a minimization or we would be talking about non-concave.
To drag out NP-complete is a bit vague and maybe evasive: Sure, usually we think of NP-complete with optimization in the context of discrete optimization or, to be simple, integer linear programming. And for a little more, IIRC, minimizing a concave function subject to linear constraints is NP-complete. But for minimizing a non-convex objective function, the assumption is that we are dealing with continuous variables where the role of NP-complete is less common?
It's not so clear what properties the constraints have -- are they also to be from functions that are non-convex?
Usually in optimization with non-convex objective functions, as a first cut we look to satisfy the corresponding Kuhn-Tucker necessary conditions with also having some suitable constraint qualifications, but in the abstract I saw no mention of Kuhn-Tucker.
IIRC there is some old work on, e.g., pits, peaks, and passes, that might help find sufficient conditions for global optima. IIRC for some special case objective functions, there are some transformations that can help.
It may be that the OP would be more clear if we assume a context, say, image recognition? But the last time I heard about non-convex optimization was for investment portfolio rrebalancing, so maybe the context is not just image recognition?
In the work I've done in optimization, the most powerful approach I found was exploit special structure. So, basically give up on general approaches and attack each problem one at a time.
That the abstract does suggest that what is being considered are evaluations of heuristics suggests that the paper is for some particular class of problems and is more like a report on computational experience than math.
I might get interested in the paper except for the concerns above.