How to find local minima of a function?

I have a 2D data with discrete intervals. I am using polyfit to get the 2nd degree polynomial expression for this data. Is there anyway to find the local minima of this function(2 variables) ? The RMS value or the absolute difference between the fit data and the actual data will give me the local minima based on discrete points, not the acccurate position.

Here is the function from my code of which I a trying to find minima: fit = polyfitn([res(:,3),res(:,4)],res(:,2),2);

res(:,2) is the data and res(:,3) and res(:,4) are the variables.

Answer 1

[Image Analyst]

If you have the Image Processing Toolbox, simply use imregionalmin():

minLocations = imregionalmin(your2Ddata);

minLocations will be a binary image the same size as your data where it's true wherever there is a local min. Though you have only one, there could potentially be lots of local min for other functions. If you want (row, column) locations, then use find():

[rows, columns] = find(minLocations);

or if you prefer x,y notation:

[y, x] = find(minLocations);

[jupiter]

@Image Analyst, Thank you. But this will also again give me the minima from the data which I have, which is discrete points. My question is, if I have a function in the form of a 2nd degree polynomial, just by giving that function as an input, can I get to know one single point wherein the minima for that function exist treating the function as continous one? No matter what is the data given or the points given as input.

[Image Analyst]

It seems like you're going for sub-pixel resolution, thinking that you can do slightly better by analyzing the fitted formula than taking an actual min value on the digitized fitted data. To do that you'd need to take the derivative d/dx and d/dy. If you're using John's polyfitn it gives you the coefficients of the 2-D polynomial, and from that just put them into the analytical formula and take the derivative. There should be an x and y where the derivative is zero in both directions. You can solve for that point.

Answer 2

[John D'Errico]

First, you are using polyfitn, not polyfit. But without seeing your data, it is hard to really help you that much.

If a globally quadratic polynomial fit is adequate, then you can compute the min of that function. But there is no assurance that it will even have a minimum. So there are constraints on the quadratic fit, and polyfitn does not offer constraints in the fit.

So I'm not really sure what is your question. Are you asking how to find the minimum of the function produced? That seems to be basic calculus. Assuming the function has a minimum, then just differentiate it (by computing the gradient) and then solve for where those two derivatives equal zero. Not that may be a local max or local min, or a stationary point, and you need to test which it is.

Or, are you asking about a noisy surface, with many local minima? So then maybe you are trying to local all of the minima? Your title does state that you want to solve for local minima.

Sorry, but your question is very unclear, and without some data to show you how to solve it, or even a picture, it is quite difficult to know how to answer.

[jupiter]

Thank you John!

Basically I have the distribution of the data like shown in the figure with the minima spread over a region at the center of the figure. I need to figure out how to find the exact minima from the function. As per the figure, there is a jump in discrete steps whereas I want to find the minima for the whole function. Differentiating and finding zero will again give me the minima at some point which is already in my dataset.

Or in general, the basic problem could be defined as : Is there any way in which I get the minima for a function of two variables? just by giving the function as an input and location of the minima as an output?

I am trying to attach the data in xl sheet format, but somehow no luck in that. File with data points

[Image Analyst]

Perhaps I didn't make it clear in my answer (using imregionalmin), but you can pass it either the actual data, or the fitted data to get the actual min location.

[John D'Errico]

I think you need to be careful here. A simple quadratic model in 2-dimensions. I'll be lazy and just use the curve fitting toolbox. It will give me the same result as polyfitn, and it has plot enabled directly.

sf = fit([x,y],z,'poly22')
     Linear model Poly22:
     sf(x,y) = p00 + p10*x + p01*y + p20*x^2 + p11*x*y + p02*y^2
     Coefficients (with 95% confidence bounds):
       p00 =   1.334e-07  (1.33e-07, 1.338e-07)
       p10 =   5.152e-08  (5.024e-08, 5.281e-08)
       p01 =  -8.742e-07  (-8.844e-07, -8.64e-07)
       p20 =   5.424e-08  (5.266e-08, 5.581e-08)
       p11 =  -7.452e-07  (-7.578e-07, -7.325e-07)
       p02 =    1.16e-05  (1.147e-05, 1.173e-05)

plot(sf,[x,y],z)

See the significant lack of fit at the bottom. You may think you are finding the global min, but in reality, the lack of fit is relatively huge. And if you think it will give you an accurate estimate of the location of that min, given that amount of lack of fit, you would be far better off just taking the lowest point, and using that! You simply will never get realistic sub-"pixel" resolution from a model with that significant lack of fit.

You could use a higher order model, as long as you don't overdo that. High order polynomial models are a bad thing in general.

[John D'Errico]

So if we use a wee bit higher order model with smaller lack of fit, Here I'll use polyfitn, because it has an easy conversion tool to move the function into the symbolic toolbox. From there, I'll use solve to generate the possible solutions.

P = polyfitn([x,y],z,4);
Ps = polyn2sym(P);
[x1,x2] = solve(gradient(Ps) == 0);

double([x1,x2])
ans =
    -1.9423 +          0i    -0.083392 +          0i
     1.1881 +          0i     -0.02961 +          0i
   -0.27634 +          0i      0.02871 +          0i
    -1.7295 +          0i     0.089204 +          0i
     1.4159 +          0i      0.13873 +          0i
   -0.10511 +     1.8035i     -0.13732 +   0.058752i
   -0.10511 -     1.8035i     -0.13732 -   0.058752i
   -0.53011 +      1.795i      0.19272 +    0.06164i
   -0.53011 -      1.795i      0.19272 -    0.06164i

Only one of those roots is both real and lies in the region of interest.

(x1,x2) = (-0.27634, 0.02871)

We can use those values in the original model to estimate the minimum.

polyvaln(P,double([x1(3),x2(3)]))
ans =
   1.1081e-07

Compare that min value to the lowest data point:

[zdatamin,loc] = min(z)
zdatamin =
   1.1017e-07
loc =
   233

[x(loc),y(loc)]
ans =
        -0.25         0.03

So, if the lack of fit is now sufficiently low, this MAY be a better estimate of the location.

Even better yet would be to use a model of the surface for just a very local region. But this may be kicking a dead horse.