Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I'm familiar with gradient descent algorithm which can find local minimum (maximum) of a given function.
Is there any modification of gradient descent which allows to find absolute minimum (maximum), where function has several local extrema?
Are there any general techniques, how to enhance an algorithm which can find local extremum, for finding absolute extremum?
I presume you are talking about unconstrained minimization. Your question should specify if you are considering a specific problem structure. Otherwise, the answer is no.
First I should dispel a myth. The classical gradient descent method (also called steepest descent method) is not even guaranteed to find a local minimizer. It stops when it has found a first-order critical point, i.e., one where the gradient vanishes. Depending on the particular function being minimized and the starting point, you may very well end up at a saddle point or even at a global maximizer!
Consider for instance $f(x,y) = x^2 - y^2$ and the initial point $(x_0,y_0) := (1,0)$. The steepest descent direction is $-\nabla f(1,0) = (-2,0)$. One step of the method with exact line search leaves you at $(0,0)$ where the gradient vanishes. Alas, it's a saddle point. You would realize by examining the second-order optimality conditions. But now imagine the function is $f(x,y) = x^2 - 10^{-16} y^2$. Here, $(0,0)$ is still a saddle point, but numerically, the second-order conditions may not tell you. In general, say you determine that the Hessian $\nabla^2 f(x^*,y^*)$ has an eigenvalue equal to $-10^{-16}$. How do you read it? Is it negative curvature or numerical error? How about $+10^{-16}$?
Consider now a function such as $$ f(x) = \begin{cases} 1 & \text{if } x \leq 0 \\ \cos(x) & \text{if } 0 < x < \pi \\ -1 & \text{if } x \geq \pi. \end{cases} $$
This function is perfectly smooth, but if your initial point is $x_0 = -2$, the algorithm stops at a global maximizer. And by checking the second-order optimality conditions, you wouldn't know! The problem here is that some local minimizers are global maximizers!
Now virtually all gradient-based optimization methods suffer from this by design. Your question is really about global optimization. Again, the answer is no, there are no general recipes to modify a method so as to guarantee that a global minimizer is identified. Just ask yourself: if the algorithm returns a value and says it is a global minimizer, how would you check that it's true?
There are classes of methods in global optimization. Some introduce randomization. Some use multi-start strategies. Some exploit the structure of the problem, but those are for special cases. Pick up a book on global optimization. You will enjoy it.
There is probably no one-size-fits-all answer to your question. But you may want to look into simulated annealing algorithms, or other approaches that rely on Markov chain Monte Carlo (MCMC) methods. These can also be combined with local methods like gradient descent.
there are many references on "global optimization of neural networks". the techniques are similar to simulated annealing [see other answer]. the basic idea is to restart the network gradient descent starting at many different weight starting points, sampled randomly or systematically. each result of the gradient descent is then like a "sample". the more samples are taken, the higher probability that one of the samples is the global optimum, especially if the target function is "well behaved" in the sense of continuous, differentiable, etcetera.
online refs
[1] Global Optimization of Neural Network Weights by Hamm et al
[2] A global optimization approach to neural network training Voglis/Lagaris
[3] Calibrating Artificial Neural Networks by Global Optimization Pinter
[4] Global Optimization of Neural Networks using a Deterministic Hybrid Approach Beliakov
[5] Global Optimization for Neural Network Training Shang/Wah
In general it is computationally hard to optimize multivariate nonconvex functions. The hardness comes in different flavors (cryptographic, NP-hard). One way of seeing this is that mixture models (such as mixture of Guassians or HMMs) are hard to learn, but would be easy(*) if it were possible to efficiently maximize the likelihood. For results on the hardness of learning HMMs, see http://alex.smola.org/journalclub/AbeWar92.pdf http://link.springer.com/chapter/10.1007%2F3-540-45678-3_36 http://www.math.ru.nl/~terwijn/publications/icgiFinal.pdf
(*) modulo the usual conditions of nondegeneracy and identifiability
i must disagree with Dominique. it was shown by hajek in the mid-1980s that annealing a nonconvex problem under certain strict conditions is guaranteed to reach the global minimum: http://dx.doi.org/10.1287/moor.13.2.311
