Finding all local maxima of a function

Question

I have written code to find the global minimum of a function using the simulated annealing algorithm — down below — but how to use the same algorithm to find all local maxima of a function?

My code for finding the local minimum of a function, note that i know nothing about the function I am asking the interactor for the f(x) at x i.e. the cost of the function in a particular point.

#include <bits/stdc++.h>

using namespace std;

double myRand(double fMin, double fMax)
{
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}


int main()
{
    cout.flush();


    double x,fx,xMin;
    double fMin;

    cout << "? "<<fixed << setprecision(6) << -1<<endl;
    cin>>fMin;


    for(double T = 1000; T>1; T*=.995)
    {
        x=myRand(-100,100);
        cout << "? "<<fixed << setprecision(6) << x <<endl;
        cin>>fx;

        if (fx<fMin)
        {
            fMin=fx;
            xMin = x;
        }
        else
        {
            double P=exp((fMin-fx)/T);

            if (P>myRand(1,100))
            {
                fMin=fx;
                xMin=x;
            }
        }
    }

    cout << "! "<<fixed << setprecision(6)<<xMin<<endl;

    return 0;

}

my attempt to find the local maxima is

#include <bits/stdc++.h>

using namespace std;

double myRand(double fMin, double fMax)
{
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}


int main()
{
    cout.flush();


    double x,fx,xMax;
    double fMax;
    int n;
    double a,b;
    cin>>n>>a>>b;

    double answer[n];




    for(int i=0; i<n; i++)
    {
        cout << "? "<<fixed << setprecision(6) << a+i/5 <<endl;
        cin>>fMax;

        for(double T = 1000; T>1; T*=.995)
        {
            x=myRand(a,b);


// i am avoiding to get the same local max twice
            while(i>0&&answer[i-1]==x)
                x=myRand(a,b);
            cout << "? "<<fixed << setprecision(6) << x <<endl;
            cin>>fx;
            if (fx>fMax)
            {
                fMax=fx;
                xMax = x;
            }
            else
            {
                double P=exp((fMax-fx)/T);

                if (P<myRand(0,1))
                {
                    fMax=fx;
                    xMax=x;
                }
            }
        }
        answer[i]=xMax;
    }
    cout << "!";
    for(int i=0; i<n; i++)
    {
        cout<<" "<<fixed << setprecision(6)<<answer[i];
    }

    return 0;

}

Simulated annealing is an optimisation *heuristic*. It’s not an exhaustive search, and it doesn’t find *all* minima or maxima. — Konrad Rudolph, Mar 24 '20 at 08:47
Have a look here: https://en.wikipedia.org/wiki/Mathematical_optimization — MadScientist, Mar 24 '20 at 09:18

score 1 · Accepted Answer · answered Mar 25 '20 at 14:43

Place the algorithm inside a function:

double my_unknown_function(double x)
{
  cout << "? " << fixed << setprecision(6) << x << endl;
  cin >> fx;

  return fx;
}

using function = double(double);

double minimum(function func)
{
  double x, fx, xMin;

  /* ... */

  for(double T = 1000; T>1; T*=.995)
  {
    x = myRand(-100,100);
    fx = func(x);

    /* ... */
  }

  return xMin;
}

In this way you can simply get multiple local minima:

std::vector<double> lm;
for (int i(0); i < 100; ++i)
  lm.push_back(minimum(my_unknown_function));

As explained in the comments, simulated annealing is an optimization heuristic. It’s not an exhaustive search and it doesn’t find all minima.

Anyway calling minimum multiple times you can get different results, since it's stochastic. In expectation, with a large enough number of restarts, any local search method will someday give you the actual global minimum.

Do not rewrite the algorithm for the maximization task: you could introduce bugs and testing is harder.

Just take the opposite of your function:
```
double my_unknown_function(double x)
{
  cout << "? " << fixed << setprecision(6) << x << endl;
  cin >> fx;

  return -fx;
}
```

Also consider:

I would like to add that if n the number of minima is given then cutting the segment to n parts then applying the algorithm on each part as you described will get us the required minima points. so for example, if the number of local minima is n, and they are all between a and b then we should divide the segment to n parts each part equal to (b-a)/n — Amr, Apr 02 '20 at 21:08

Finding all local maxima of a function

1 Answers1