Re: Re: Gradient option for FindMinimum

*To*: mathgroup at smc.vnet.net*Subject*: [mg77119] Re: [mg77086] Re: [mg77067] Gradient option for FindMinimum*From*: DrMajorBob <drmajorbob at bigfoot.com>*Date*: Mon, 4 Jun 2007 03:49:41 -0400 (EDT)*References*: <200706020820.EAA00301@smc.vnet.net> <21521158.1180880832611.JavaMail.root@m35>*Reply-to*: drmajorbob at bigfoot.com

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 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 > > -- = DrMajorBob at bigfoot.com

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