A few things to get out of the way first: I'm not asking what properties the function must have such that a global optimum exists, we assume that the objective function has a (possibly non-unique) global optimum which could be theoretically found by an exhaustive search of the candidate space. I'm also using "theoretically useful" in a slightly misleading way because I really couldn't understand how to phrase this question otherwise. A "theoretically useful cost function" the way I'm defining it is:

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

A few simplified, 1-dimensional examples of where this thought process came from: graph of a bimodal function exhibiting both a global and local maxima

Here's a function which, while not being convex or differentiable (as it's discrete), is easily optimisable (in terms of finding the global maximum) with an algorithm such as Simulated Annealing.

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

Here is a function which clearly cannot be a useful cost function, as this would imply that the arbitrary search problem can be classically solved faster than exhaustive search.

graph of a function which takes random discrete values

Here is a function which I do not believe can be a useful cost function, as moving between points gives no meaningful information about the direction which must be moved in to find the global maximum.

The crux of my thinking so far is along the lines of "applying the cost function to points in the neighbourhood of a point must yield some information about the location of the global optimum". I attempted to formalise (in a perhaps convoluted manner) this as:

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.

Whilst this works well for the function which definitely is useful and the definitely not useful boolean function, this process applied to the random function seems incorrect, as the number of elements that would lead to a function with no local optima IS a non-negligible proportion of the total domain.

Is my definition on the right track? Is this a well known question I just can't figure out how to find the answer to? Does there exist some optimisation algorithm that would theoretically be able to find the optimum of a completely random function faster than exhaustive search, or is my assertion that it wouldn't be able to correct?

In conclusion, what is different about the first function that makes it a good candidate for optimisation to any other functions which are not.

  • $\begingroup$ Convex implies continuous, while your use of graph and neighbour is inherently discrete. If you are looking for some theoretical results about functions that are easy to optimize, I suggest googling for "local search" and "objective function landscape" $\endgroup$ – Gabriel Gouvine Jul 6 '20 at 11:58
  • $\begingroup$ @GabrielGouvine Hi thanks for commenting! I've replaced instances of "convex" with "containing no non-global local optima", as I was misusing the term. Furthermore, I think I may have been a bit unclear in my wording of the question, perhaps you could help me clarify? I don't necessarily want to know whether a function is "easy" to optimise, but rather if, from I suppose an information theoretic perspective, it CAN be optimised any faster than exhaustive search in the worst case (even if the advantage is minimal and is still not practical): e.g. the given boolean function provably cannot be $\endgroup$ – arcaynia Jul 6 '20 at 12:23
  • 1
    $\begingroup$ Well it's a well known hard question. It's very difficult to caracterize local search performance theoretically, although it's been done for some cases (problem+neighborhood) $\endgroup$ – Gabriel Gouvine Jul 6 '20 at 13:13
  • $\begingroup$ @GabrielGouvine awesome, if you could point me to an article or paper which mentions/discusses the problem I would be happy to accept that as an answer as i couldn't find any just looking up what you suggested :) $\endgroup$ – arcaynia Jul 6 '20 at 15:04

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.

  • $\begingroup$ Thank you, I've been racking my brains over this all day and something like the comparison to P vs NP was exactly what I was looking for, I just couldn't see it. As you can probably tell, I'm fairly unfamiliar with the field of optimisation on the whole and this seems like the kind of answer which is entirely obvious to anyone who has any grasp on the theory to the point where its quite hard to actually find somewhere that says "it's a known hard problem" :) $\endgroup$ – arcaynia Jul 6 '20 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.