Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>