Re: Re: Gradient option for FindMinimum

*To*: mathgroup at smc.vnet.net*Subject*: [mg77121] Re: [mg77086] Re: [mg77067] Gradient option for FindMinimum*From*: Carl Woll <carlw at wolfram.com>*Date*: Mon, 4 Jun 2007 03:50:43 -0400 (EDT)*References*: <200706020820.EAA00301@smc.vnet.net> <21521158.1180880832611.JavaMail.root@m35> <op.ttdcxsyyqu6oor@monster.ma.dl.cox.net>

DrMajorBob wrote: > In version 6, at least, that can be simplified: > > Clear[f, grad] > f[x_List] := (x.x - 10)^2 > grad[x_?(VectorQ[#, NumberQ] &)] := 4 (x.x - 10) x > Remove["x*"] > vars = Unique[ConstantArray["x", 1000]]; > n = Length@vars; > Timing[First@ > FindMinimum[f[vars], Transpose@{vars, RandomReal[1, n]}, > Gradient -> grad[vars]]] > Timing[First@FindMinimum[f[vars], Transpose@{vars, RandomReal[1, n]}]] > > {0.078,1.5014*10^-17} > {0.266,1.07907*10^-17} > > Gradient speeds up the search quite a bit! > > Bobby I should have looked at the FindMinimum documentation before replying! At any rate, looking at the documentation, we find the following: If the starting point for a variable is given as a list, the values of the variable are taken to be lists with the same dimensions. So, an even simpler approach is: f[x_List] := (x.x - 10)^2 grad[x : {__?NumericQ}] := 4 (x.x - 10) x In[45]:= FindMinimum[f[x], {x, RandomReal[1, {1000}]}, Gradient -> grad[x]][[1]] // Timing Out[45]= {0.031,1.55719*10^-16} Carl Woll Wolfram Research > > On Sun, 03 Jun 2007 05:08:33 -0500, Carl Woll <carlw at wolfram.com> wrote: > >> Veit Elser wrote: >> >>> How does one specify the Gradient option for FindMinimum when the >>> function >>> being minimized takes as argument a list of real numbers of >>> unspecified length? >>> >>> Suppose I have defined a numerical function >>> >>> func[x_] := ... >>> >>> that returns a real number when given a list of real numbers x. I >>> have also defined >>> a numerical function >>> >>> grad[x_] := ... >>> >>> that returns the gradient of func at x (a list of real numbers of the >>> same length as x). >>> How do I use func and grad within FindMinimum to find the local >>> minimum of func >>> given some starting point x0 (a list of real numbers of the >>> appropriate length)? >>> >>> I use Mathematica version 6. The documentation for the Gradient >>> option says to specify >>> a list of functions. This would be very inefficient in my case. >>> Without going into too many >>> details, this comes about because func is a sum of terms over pairs >>> of variables, as is grad. >>> One computation of grad therefore takes just about the same time as >>> one computation of >>> func. This efficiency would be lost if Mathematica had to evaluate >>> multiple versions of grad, >>> one corresponding to each of its components. In my application the >>> variable x has typically >>> thousands of components. >>> >>> >>> >>> >> Here is a toy example that you might use as a template: >> >> Clear[f, grad] >> f[x_List}] := (x.x - 10)^2 >> grad[x : {__?NumberQ}] := (Print[x]; 4 (x.x - 10) x) >> >> I use argument restrictions on the function grad to make sure that my >> definition of grad is being used. The Print statement is just there to >> give you confidence that grad is being used. Then, as an example of >> using FindMinimum with f and grad: >> >> vars = {x0,x1,x2,x3}; >> >> In[309]:= FindMinimum[ >> f[vars], >> Evaluate[Sequence @@ Transpose[{vars, RandomReal[1, >> Length[vars]]}]], >> Gradient -> grad[vars] >> ] >> >> During evaluation of In[309]:= {0.325662,0.918296,0.399839,0.554055} >> >> During evaluation of In[309]:= {0.488493,1.37744,0.599758,0.831083} >> >> During evaluation of In[309]:= {1.13982,3.21404,1.39944,1.93919} >> >> During evaluation of In[309]:= {0.828109,2.33509,1.01673,1.40888} >> >> During evaluation of In[309]:= {0.995324,2.8066,1.22203,1.69337} >> >> During evaluation of In[309]:= {0.86316,2.43393,1.05977,1.46851} >> >> During evaluation of In[309]:= {0.865535,2.44062,1.06268,1.47255} >> >> During evaluation of In[309]:= {0.865383,2.44019,1.06249,1.47229} >> >> During evaluation of In[309]:= {0.865384,2.4402,1.0625,1.4723} >> >> During evaluation of In[309]:= {0.865384,2.4402,1.0625,1.4723} >> >> Out[309]= >> {1.26218*10^-29,{x0->0.865384,x1->2.4402,x2->1.0625,x3->1.4723}} >> >> We see from the Print statements that grad is being used. Now, let's >> remove the Print statement, and do the same problem with a 1000 >> variables: >> >> Clear[f, grad] >> f[x : {__?NumberQ}] := (x.x - 10)^2 >> grad[x : {__?NumberQ}] := 4 (x.x - 10) x >> >> Now create variables x1, x2, etc.: >> >> Remove["x*"] >> vars = Unique[ConstantArray["x", 1000]]; >> >> Let's check that vars does contain distinct variables >> >> In[326]:= vars[[;; 10]] >> Out[326]= {x1,x2,x3,x4,x5,x6,x7,x8,x9,x10} >> >> Now, try FindMinimum again: >> >> In[327]:= >> FindMinimum[ >> f[vars], >> Evaluate[Sequence @@ Transpose[{vars, RandomReal[1, >> Length[vars]]}]], >> Gradient -> grad[vars] >> ][[1]] // Timing >> >> Out[327]= {0.094,1.58047*10^-16} >> >> So, the toy problem took .094 seconds, and arrived at a minimum value of >> essentially 0. >> >> Hope that helps, >> Carl Woll >> Wolfram Research >> >> > > >

**References**:**Gradient option for FindMinimum***From:*Veit Elser <ve10@cornell.edu>