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>
- Gradient option for FindMinimum