Re: Efficient repeated use of FindRoot

*To*: mathgroup at smc.vnet.net*Subject*: [mg74069] Re: [mg74049] Efficient repeated use of FindRoot*From*: "Chris Chiasson" <chris at chiasson.name>*Date*: Thu, 8 Mar 2007 04:40:04 -0500 (EST)*References*: <200703070816.DAA26723@smc.vnet.net>

P.S. If you are feeling adventurous, you can try to trace functions in the contexts that are shown after executing that NMinimize RandomSearch command: Contexts[] >From looking at the context names, I think that Mathematica developers have largely tackled these problems before now, but that the necessary functions just aren't documented for our use. On 3/7/07, Chris Chiasson <chris at chiasson.name> wrote: > There is at least one way to make Mathematica handle the largrange > multipliers (or, alternatively, do the interior point method) for a > given starting point and constraints. > > Take a look at the documentation for NMinimize and go to Advanced > Documentation. Then go to Random Search. One of the options for the > method gives the ability to directly specify the set of points tried > for post processing. > > In[7]:= NMinimize[{100(y-x^2)^2+(1-x)^2,x^2+y^2<=1},{x,y},Method->{"RandomSearch","InitialPoints"->{{0,0}}}] > Out[7]= {0.0456748,{x->0.786415,y->0.617698}} > > This should be relatively fast because only one start point is > specified and Mathematica is using internal code to construct the > lagrange multipliers (or do the interior point method if that is > selected). > > That still leaves the problem of repeatedly constructing the > simultaneous equations from convergence criteria. As you were saying > in the first post, it would be nice to construct the simultaneous > equations once and then solve repeatedly. I am thinking about how > homotopic continuation (a method Carl Woll showed to me in an earlier > MathGroup post) could be applied in this situation. > > Do you actually have all the simultaneous equations listed out > somewhere (so that all variables are a function of only that one > parameter you want to vary)? > > On 3/7/07, Chris Chiasson <chris at chiasson.name> wrote: > > You have hit the nail exactly on the head. NMinimize uses optimization > > techniques that are less efficient than those of FindMinimum if the > > global optimum can be found by using local (derivative) information > > from a chosen starting point. Until FindMinimum sprouts a constraint > > handling feature, we are left to fill the gap. I will think about your > > problem a bit more. > > > > On 3/7/07, Michael A. Gilchrist <mikeg at utk.edu> wrote: > > > Hi Chris, > > > > > > The basic answer is I am interested in understanding the lagrangian and I > > > think working with it is the best way to begin to understand it. I've > > > also run into issues with NMinimize in the past. In my experience, > > > NMinimize is more compuationally intensive than FindRoot or FindMinimum > > > for systems where there's a single global optimum as I would expect in > > > this case. In addition, NMinimize is too 'blackbox' for me (i.e. I > > > understand the routines in FindRoot better). As a result I don't feel > > > like I have as much control over it as I do FindRoot. > > > > > > Also, from what I understand I'd be running into the same problem of the > > > large initialization time. > > > > > > Mike > > > > > > > > > On Wed, 7 Mar 2007, Chris Chiasson wrote: > > > > > > > Why are you not using NMinimize or NMaximize? > > > > > > > > On 3/7/07, Michael A. Gilchrist <mikeg at utk.edu> wrote: > > > >> Hi all, > > > >> > > > >> I've got an optimization problem that I am trying to evaluate numerically > > > >> and at a number of different points of a particular variable. I am using > > > >> a Lagrangian multiplier to impose a constraint on the optimization of the > > > >> 'free variables' and as a result trying to find the root for a set of n > > > >> coupled equations (in its full form n = 4000+ variables). > > > >> > > > >> > > > >> Using some approximations I can come up with some reasonable initial > > > >> conditions, but, as you might imagine, it takes quite some time to run > > > >> the code. Looking at the output it appears that the greatest amount of > > > >> time is initialization of the FindRoot routine (once the routine is > > > >> running it calculates each step quite quickly). > > > >> > > > >> > > > >> Here's some pseudo code to illustrate the basic idea: > > > >> > > > >> (*set up eqns and variables*) > > > >> Clear[m]; > > > >> vars = Table[m[i], {1, n}] > > > >> > > > >> eqns = Table[ > > > >> (llik[i, vars] + \[Lambda] m[i] ==0), {i, 2, n}] > > > >> (*llik previously defined) > > > >> ics = Table[ > > > >> m0[i] = T[i]/phi[i] (*T[i] and Phi[i] previously defined*), > > > >> {i, 2, n}]; > > > >> > > > >> frvars = Table[{m[i], m0[i] * 0.01, m0[i]*10}, {i, 2, n}]; > > > >> > > > >> > > > >> (*look for solution to problem for multiple values of m[1] *) > > > >> Table[ > > > >> FindRoot[eqns, frvars], {m[1], 0.01, 0.2, 0.01}] > > > >> > > > >> > > > >> I am aware of the NDSolve package StateData that allows one to > > > >> efficiently evaluate DE's with various different initial > > > >> conditions by processing the equations. > > > >> > > > >> I've looked through the documentation on FindRoot and haven't found a > > > >> similar routine/ability. I'm wondering if anyone has any ideas on how > > > >> one might increase the efficiency of my calculations. > > > >> > > > >> Thanks. > > > >> > > > >> Mike > > > >> > > > >> > > > >> ----------------------------------------------------- > > > >> Department of Ecology & Evolutionary Biology > > > >> 569 Dabney Hall > > > >> University of Tennessee > > > >> Knoxville, TN 37996-1610 > > > >> > > > >> phone:(865) 974-6453 > > > >> fax: (865) 974-6042 > > > >> > > > >> web: http://eeb.bio.utk.edu/gilchrist.asp > > > >> ----------------------------------------------------- > > > >> > > > >> > > > >> > > > > > > > > > > > > -- > > > > http://chris.chiasson.name/ > > > > > > > > > > ----------------------------------------------------- > > > Department of Ecology & Evolutionary Biology > > > 569 Dabney Hall > > > University of Tennessee > > > Knoxville, TN 37996-1610 > > > > > > phone:(865) 974-6453 > > > fax: (865) 974-6042 > > > > > > web: http://eeb.bio.utk.edu/gilchrist.asp > > > ----------------------------------------------------- > > > > > > > > > > > > -- > > http://chris.chiasson.name/ > > > > > -- > http://chris.chiasson.name/ > -- http://chris.chiasson.name/

**References**:**Efficient repeated use of FindRoot***From:*"Michael A. Gilchrist" <mikeg@utk.edu>