Re: Efficient repeated use of FindRoot
- To: mathgroup at smc.vnet.net
- Subject: [mg74068] Re: [mg74049] Efficient repeated use of FindRoot
- From: "Chris Chiasson" <chris at chiasson.name>
- Date: Thu, 8 Mar 2007 04:39:31 -0500 (EST)
- References: <200703070816.DAA26723@smc.vnet.net>
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/
- References:
- Efficient repeated use of FindRoot
- From: "Michael A. Gilchrist" <mikeg@utk.edu>
- Efficient repeated use of FindRoot