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


0

首先要避免的一些事情:我不是在問函數必須具有哪些屬性以使得存在全局最優,我們假設目標函數具有一個(可能是非唯一的)全局最優,它可以從理論上通過詳盡搜索候選空間找到。我也以一種有點誤導的方式使用"理論上有用的",因為我真的不明白如何用其他方式表達這個問題。我定義的"理論上有用的成本函數"是:

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

此思想過程來自的一些簡化的一維示例:graph of a bimodal function exhibiting both a global and local maxima

這是一個函數,儘管它不是凸的或不可微的(因為它是離散的),但可以通過諸如模擬退火的算法輕鬆地優化(根據找到全局最大值)。

graph of a boolean function with 100 0 values and a single 1 value

這裡的一個函數顯然不能成為有用的成本函數,因為這暗示著傳統上比窮舉搜索更快地可以解決任意搜索問題。

graph of a function which takes random discrete values

這是一個我認為不能用作有用的成本函數的函數,因為在點之間移動並沒有提供有關必須移動以找到全局最大值的方向的有意義的信息。

到目前為止,我的思想的癥結在於"將成本函數應用於點附近的點必須產生有關全局最優位置的一些信息"。我試圖將其形式化(可能是令人費解):

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.

雖然這對於絕對有用的函數和絕對不有用的布爾函數都很好用,但是應用於隨機函數的此過程似乎是不正確的,因為導致沒有局部最優的函數的元素數量是非-佔總域的比例可忽略不計。

我的定義是否正確?這是一個我不知道如何找到答案的眾所周知的問題嗎?是否存在某種優化算法,理論上可以比窮舉搜索更快地找到完全隨機函數的最優值,或者我斷言它無法糾正?

總而言之,第一個功能有什麼不同,使它成為優化其他功能的理想人選。

0

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.