C#: Loop to find minima of function

Question

I currently have this function:

    public double Max(double[] x, double[] y)
    {
        //Get min and max of x array as integer
        int xMin = Convert.ToInt32(x.Min());
        int xMax = Convert.ToInt32(x.Max());


        // Generate a list of x values for input to Lagrange

        double i = 2;
        double xOld = Lagrange(xMin,x,y);
        double xNew = xMax;
        do
        {
            xOld = xNew;
            xNew = Lagrange(i,x,y);
            i = i + 0.01;
        } while (xOld > xNew);

        return i;
    }

This will find the minimum value on a curve with decreasing slope...however, given this curve, I need to find three minima.

How can I find the three minima and output them as an array or individual variables? This curve is just an example--it could be inverted--regardless, I need to find multiple variables. So once the first min is found it needs to know how to get over the point of inflection and find the next... :/

*The Lagrange function can be found here.** For all practical purposes, the Lagrange function will give me f(x) when I input x...visually, it means the curve supplied by wolfram alpha.

*The math-side of this conundrum can be found here.**

Possible solution? Generate an array of input, say x[1,1.1,1.2,1.3,1.4...], get an array back from the Lagrange function. Then find the three lowest values of this function? Then get the keys corresponding to the values? How would I do this?

Answer 1

Assuming you're just trying to "brute force" calculate this to a certain level of prcision, you need your algorithm to basically find any value where both neighbors are greater than the current value of your loop.

To simplify this, let's just say you have an array of numbers, and you want to find the indices of the three local minima. Here's a simple algorithm to do it:

public void Test()
{
    var ys = new[] { 1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 4, 5, 4 };
    var indices = GetMinIndices(ys);
}

public List<int> GetMinIndices(int[] ys)
{
    var minIndices = new List<int>();
    for (var index = 1; index < ys.Length; index++)
    {
        var currentY = ys[index];
        var previousY = ys[index - 1];
        if (index < ys.Length - 1)
        {
            var neytY = ys[index + 1];
            if (previousY > currentY && neytY > currentY) // neighbors are greater
                minIndices.Add(index); // add the index to the list
        }
        else // we're at the last index
        {
            if (previousY > currentY) // previous is greater
                minIndices.Add(index);
        }
    }
    return minIndices;
}

So, basically, you pass in your array of function results (ys) that you calculated for an array of inputs (xs) (not shown). What you get back from this function is the minimum indices. So, in this example, you get back 8, 14, and 17.

Answer 2

It's been a while since I've taken a numerical methods class, so bear with me. In short there are a number of ways to search for the root(s) of a function, and depending on what your your function is (continuous? differentiable?), you need to choose one that is appropriate.

For your problem, I'd probably start by trying to use Newton's Method to find the roots of the second degree Lagrange polynomial for your function. I haven't tested out this library, but there is a C# based numerical methods package on CodePlex that implements Newton's Method that is open source. If you wanted to dig through the code you could.

The majority of root finding methods have cousins in the broader CS topic of 'search'. If you want a really quick and dirty approach, or you have a very large search space, consider something like Simulated Annealing. Finding all of your minima isn't guaranteed but it's fast and easy to code.