# 離散函數的哪些屬性使其成為理論上有用的目標函數？

A function to which some theoretical optimisation algorithm can be applied such that the algorithm has a non-negligible chance of finding the global optimum in less time than exhaustive search

Consider the set $$D$$ representing the search space of the problem and thus the domain of the function and the undirected graph $$G$$, where each element of $$D$$ is assigned a node in $$G$$, and each node in $$G$$ has edges which connect it to its neighbours in $$D$$. We then remove elements from $$D$$ until the objective function has no non-global local optima over this domain and no plateaus exist (i.e. the value of the cost function at each point in the domain is different from the value of the cost function at each of its neighbours). Every time we remove an element $$e$$ from $$D$$, we remove the corresponding node from the graph $$G$$ and add edges which directly connect each neighbour of $$e$$ to each other, thus they become each others' new neighbours. The number of elements which remain in the domain after this process is applied is designated $$N$$. If $$N$$ is a non-negligible proportion of $$\#(D)$$ (i.e. significantly greater than the proportion of $$\#(\{$$possible global optima$$\})$$ to $$\#(D)$$) then the function is a 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.