<p>There is probably no one-size-fits-all answer to your question. But you may want to look into <a href="http://en.wikipedia.org/wiki/Simulated_annealing" rel="nofollow">simulated annealing</a> algorithms, or other approaches that rely on Markov chain Monte Carlo (MCMC) methods. These can also be combined with local methods like gradient descent.</p>

CC BY-SA 3.0
2012-06-27T21:01:49.343Z
2012-06-27T21:01:49.343Z
mrig
<p>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
<a href="http://alex.smola.org/journalclub/AbeWar92.pdf" rel="nofollow">http://alex.smola.org/journalclub/AbeWar92.pdf</a>
<a href="http://link.springer.com/chapter/10.1007%2F3-540-45678-3_36" rel="nofollow">http://link.springer.com/chapter/10.1007%2F3-540-45678-3_36</a>
<a href="http://www.math.ru.nl/~terwijn/publications/icgiFinal.pdf" rel="nofollow">http://www.math.ru.nl/~terwijn/publications/icgiFinal.pdf</a></p>

<p>(*) modulo the usual conditions of nondegeneracy and identifiability</p>

CC BY-SA 3.0
2015-02-03T10:56:56.037Z
2015-02-03T18:54:19.623Z
2015-02-03T18:54:19.623Z
Aryeh
<p>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.</p>

<p>online refs</p>

<p>[1] <a href="http://faime.demon.co.uk/~streetm/wcci_2002/IJCNN02/PDFFiles/Papers/1373.pdf" rel="nofollow">Global Optimization of Neural Network Weights</a> by Hamm et al</p>

<p>[2] <a href="http://www.cs.uoi.gr/~lagaris/papers/PREPRINTS/globnn-npc.pdf" rel="nofollow">A global optimization approach to neural network training</a> Voglis/Lagaris</p>

<p>[3] <a href="http://www.optimization-online.org/DB_FILE/2010/07/2685.pdf" rel="nofollow">Calibrating Artificial Neural Networks by Global Optimization</a> Pinter</p>

<p>[4] <a href="http://www.mat.univie.ac.at/~neum/glopt/mss/BelA02" rel="nofollow">Global Optimization of Neural Networks using a Deterministic Hybrid Approach</a> Beliakov</p>

<p>[5] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.6147" rel="nofollow">Global Optimization for Neural Network Training</a> Shang/Wah</p>

CC BY-SA 3.0
2012-06-28T16:03:50.887Z
2012-06-28T16:09:00.770Z
2012-06-28T16:09:00.770Z
vzn
<p>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: <a href="http://dx.doi.org/10.1287/moor.13.2.311" rel="nofollow">http://dx.doi.org/10.1287/moor.13.2.311</a></p>

CC BY-SA 3.0
2015-02-03T10:59:01.083Z
In light of the hardness results mentioned above, those conditions must indeed be pretty strict!
Aryeh
CC BY-SA 3.0
2015-02-03T04:30:25.383Z
2015-02-03T04:30:25.383Z
Aaron Brick
<p>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.</p>

<p>First I should dispel a myth. The classical gradient descent method (also called <em>steepest descent</em> 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!</p>

<p>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}$?</p>

<p>Consider now a function such as
$$
f(x) =
\begin{cases}
 1 &amp; \text{if } x \leq 0 \\
\cos(x) &amp; \text{if } 0 &lt; x &lt; \pi \\
-1 &amp; \text{if } x \geq \pi.
\end{cases}
$$</p>

<p>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!</p>

<p>Now virtually all gradient-based optimization methods suffer from this by design. Your question is really about <em>global optimization</em>. 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?</p>

<p>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.</p>

CC BY-SA 3.0
2012-04-19T20:58:11.067Z
@Roman: Very welcome.
Dominique
CC BY-SA 3.0
2012-04-19T20:16:38.077Z
2012-04-19T20:16:38.077Z
Dominique
<p>I'm familiar with gradient descent algorithm which can find local minimum (maximum) of a given function. </p>

<p>Is there any modification of gradient descent which allows to find absolute minimum (maximum), where function has several local extrema? </p>

<p>Are there any general techniques, how to enhance an algorithm which can find local extremum, for finding absolute extremum?</p>

CC BY-SA 3.0
2012-03-11T14:35:16.893Z
You may want to check [stats.se] or the AI Q&A linked from the [FAQ].
Kaveh
CC BY-SA 3.0
2012-03-12T00:45:54.450Z
I think that's one of the drawbacks of gradient descent- it can get stuck in local extrema. Other techniques like simulated annealing may be less susceptible to this, but still can't make guarantees, from what I understand.
Joe
CC BY-SA 3.0
2012-03-12T02:24:01.230Z
I'm not sure what the 'multidimensional space' has to do with this. even a function to R can have multiple local extrema that gradient search will have problems with.
Suresh Venkat
CC BY-SA 3.0
2012-06-28T03:07:52.993Z
Im pretty sure there is a theorem along the lines that if the function is continuous, and sampled at enough points, you can guarantee that gradient descent will find the global minimum starting at some point. ie something along the lines of powell's algorithm. the literature is so vast that a theorem like this is probably published somewhere, but havent heard of it. it also proves that local optimization can approach global optimums under enough sampling, as sampling goes up.
vzn
CC BY-SA 3.0
2012-06-29T02:57:45.050Z
somewhat related see also comments [here](http://cstheory.stackexchange.com/a/10076/7884) that strongly argue that global NN or numerical method/heuristic type approaches are _not_ "approximation algorithms"
vzn
<ds.algorithms><approximation-algorithms><machine-learning>
Is there any gradient descent based technique for searching absolute minimum (maximum) of a function in multidimensional space?
Roman
# Is there any gradient descent based technique for searching absolute minimum (maximum) of a function in multidimensional space?

(Asked by: username_0 on 2012-03-11)

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?

**Tags:** ds.algorithms, approximation-algorithms, machine-learning
> **Comments:**
> **username_1**: You may want to check [stats.se] or the AI Q&A linked from the [FAQ].  
> **username_2**: I think that's one of the drawbacks of gradient descent- it can get stuck in local extrema. Other techniques like simulated annealing may be less susceptible to this, but still can't make guarantees, from what I understand.  
> **username_3**: I'm not sure what the 'multidimensional space' has to do with this. even a function to R can have multiple local extrema that gradient search will have problems with.  
> **username_4**: Im pretty sure there is a theorem along the lines that if the function is continuous, and sampled at enough points, you can guarantee that gradient descent will find the global minimum starting at some point. ie something along the lines of powell's algorithm. the literature is so vast that a theorem like this is probably published somewhere, but havent heard of it. it also proves that local optimization can approach global optimums under enough sampling, as sampling goes up.  
> **username_4**: somewhat related see also comments [here](http://cstheory.stackexchange.com/a/10076/7884) that strongly argue that global NN or numerical method/heuristic type approaches are _not_ "approximation algorithms"  

---

## 5 answers

### Answer by username_8 on 2012-04-19. Score: 18 | Accepted answer

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.

> **Comments:**
> **username_8**: @Roman: Very welcome.  

---

### Answer by username_5 on 2012-06-27. Score: 3

There is probably no one-size-fits-all answer to your question. But you may want to look into [simulated annealing](http://en.wikipedia.org/wiki/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.


---

### Answer by username_6 on 2015-02-03. Score: 1

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


---

### Answer by username_4 on 2012-06-28. Score: 1

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](http://faime.demon.co.uk/~streetm/wcci_2002/IJCNN02/PDFFiles/Papers/1373.pdf) by Hamm et al

[2] [A global optimization approach to neural network training](http://www.cs.uoi.gr/~lagaris/papers/PREPRINTS/globnn-npc.pdf) Voglis/Lagaris

[3] [Calibrating Artificial Neural Networks by Global Optimization](http://www.optimization-online.org/DB_FILE/2010/07/2685.pdf) Pinter

[4] [Global Optimization of Neural Networks using a Deterministic Hybrid Approach](http://www.mat.univie.ac.at/~neum/glopt/mss/BelA02) Beliakov

[5] [Global Optimization for Neural Network Training](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.6147) Shang/Wah


---

### Answer by username_7 on 2015-02-03. Score: 0

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>

> **Comments:**
> **username_6**: In light of the hardness results mentioned above, those conditions must indeed be pretty strict!  

---

