Why Locating Local Optima Is Sometimes More Complicated Than Locating Global Ones

In most applications, practitioners are interested in locating global optima. In such applications, local optima that result from some optimization algorithms are an unnecessary side effect. In other words, in such applications, locating global optima is a much more computationally complex problem than locating local optima. In several practical applications, however, local optima themselves are of interest. Somewhat surprisingly, it turned out that in many such applications, locating all local optima is a much more computationally complex problem than locating all global optima. In this paper, we provide a theoretical explanation for this surprising empirical phenomenon