Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Gradient option for FindMinimum

• To: mathgroup at smc.vnet.net
• Subject: [mg77086] Re: [mg77067] Gradient option for FindMinimum
• From: Carl Woll <carlw at wolfram.com>
• Date: Sun, 3 Jun 2007 06:08:33 -0400 (EDT)
• References: <200706020820.EAA00301@smc.vnet.net>

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>