11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You may want to check Cross Validated or the AI Q&A linked from the FAQ. $\endgroup$ – Kaveh Mar 11 '12 at 14:35
  • $\begingroup$ 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. $\endgroup$ – Joe Mar 12 '12 at 0:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Mar 12 '12 at 2:24
  • $\begingroup$ 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. $\endgroup$ – vzn Jun 28 '12 at 3:07
  • $\begingroup$ somewhat related see also comments here that strongly argue that global NN or numerical method/heuristic type approaches are not "approximation algorithms" $\endgroup$ – vzn Jun 29 '12 at 2:57
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Roman: Very welcome. $\endgroup$ – Dominique Apr 19 '12 at 20:58
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ In light of the hardness results mentioned above, those conditions must indeed be pretty strict! $\endgroup$ – Aryeh Feb 3 '15 at 10:59

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.