What properties of a discrete function make it a theoretically useful objective function?
No, I don't think your formalization is heading in a useful direction.  It seems convoluted and focused on one particular algorithm, but there might be other optimization algorithms that you haven't considered.
I don't expect there to be a useful characterization of which objective functions can and can't be optimized effectively.  It's a notoriously hard problem.  There is work on the literature on identifying classes of problems that can provably be optimized efficiently (e.g., convex objective functions, linear programming, semidefinite programming), but the reality is that what we can prove falls short of what empirically often seems to be feasible in practice.
For instance, what you're looking for is at least as hard as the P vs NP problem, since every NP problem can be expressed as an optimization problem; and I don't expect there to be a simple characterization of which NP problems are NP-complete.