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>
- Efficient repeated use of FindRoot