Group Abstract Group Abstract

Message Boards Message Boards

0
|
5.1K Views
|
4 Replies
|
3 Total Likes
View groups...
Share
Share this post:

Why is FindMinimum running out of memory?

David Keith
Posted 10 years ago

Hello all,

The attached notebook and data file demonstrate a problem with FindMinimum. The data is a set of points which to a great extent lie on a circle. The calculation attempts to find the center of the circle by locating the point which is most nearly equidistant from the data points. The method used is to construct a function which accepts a candidate point as an argument, and returns the standard deviation of the computed list of distances from the candidate to each of the data points. The rationale is that the point with the smallest standard deviation of distances is central.

There are a lot of data points, so the calculation of each function value is lengthy, and requires a reasonable amount of memory. But FindMinimum sees a simple function which accepts two numbers and returns a third. That's all. However, as FindMinimum executes memory as reported by Task Manager grows steadily until it consumes all 8GB available and Windows asks to shut down the kernel.

Can any of you tell me what is consuming all this memory? (To execute, put the CSV file in the same directory as the notebook.)

Thanks and kind regards, David

Attachments:
POSTED BY: David Keith
4 Replies
Sort By:

If you rewrite the equation of the a circle at {x0,y0} with radius R0 in the following form: 

x^2 + y^2 = (x0^2 + y0^2 -R0^2)  + (2* x0) * x  +(2*y0) * y  (* z = c + a * x + b * y *)

where {x,y} are points on the circumference. You can use the linear model fit to find the circle

In[23]:= (reg={2 #1,2 #2,#2^2+#1^2}&@@@points)//Short
Out[23]//Short= {{124,1042,275285},{132,1030,269581},{132,1044,276840},<<50295>>,{1756,1016,1028948},{1760,968,1008656}}

In[28]:= lm=LinearModelFit[reg,{1,x,y},{x,y}]
Out[28]= FittedModel[-323255.+471.705 x+501.105 y]

Best model fit by least square: 

In[25]:= bf=lm["BestFitParameters"]
Out[25]= {-323255.,471.705,501.105}
In[26]:= exp=(x-#2)^2+(y-#3)^2-#1-#2^2-#3^2&@@bf
Out[26]= -150357.+(-471.705+x)^2+(-501.105+y)^2

The code is modified from this stack exchange page
POSTED BY: Shenghui Yang

For the out of memory issue, you want to pre-compute the massive expressions first. Use Set/= instead of SetDelayed/:=

distances[{x0_, y0_}] = EuclideanDistance[{x0, y0}, #] & /@ test
stdDevOfDistances[{x0_, y0_}] =Refine[StandardDeviation@distances[{x0, y0}], Assumptions -> x0 \[Element] Reals && y0 \[Element] Reals]

sol=FindMinimum[stdDevOfDistances[{h,k}],{h,400,600},{k,400,600}] (*use 500 random sample points*)
{9.30827,{h->472.507,k->501.032}}

If you use SetDelay, Mathematica tries to make up the huge expressions for the standard deviation and distance function every time you call it.

See the neat example for : https://reference.wolfram.com/language/ref/SetDelayed.html

POSTED BY: Shenghui Yang

I guess the issue with memory leak is from continuously created large expression during the optimization process. You may try the StepMonitor to show the internal step. My best estimate is that when the function takes the derivative and hessian matrix of the huge expression, things just grow exponentially. 

 FindMinimum[Exp[x] + 1/x, {x, 1},  StepMonitor :> Print["Step to x = ", x]]
POSTED BY: Shenghui Yang
David Keith
David Keith
Posted 10 years ago

Thanks very much, Shenghui. Very helpful. I am not sure I understand the issue regarding Set vs SetDelayed with regard to memory usage. It is clear that using Set means the assembly of the very large symbolic expression is done only in the definition, and is then used as the template for substitution each time the function is called. I have no doubt that is better with respect to speed. But I thought that in either case the memory used in each call should be released after the call is complete, and not accumulate. However, the method using LinearModelFit you give in your first post is vastly superior to what I was doing -- I will use that!

Kind regards, David
POSTED BY: David Keith
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard