Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2008

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

Search the Archive

Re: Speeding up FindMinimum setup

  • To: mathgroup at smc.vnet.net
  • Subject: [mg86672] Re: [mg86652] Speeding up FindMinimum setup
  • From: Carl Woll <carlw at wolfram.com>
  • Date: Mon, 17 Mar 2008 00:23:16 -0500 (EST)
  • References: <200803160939.EAA27599@smc.vnet.net>

Art wrote:

>I am having trouble with the time FindMinimum takes to make it's first
>step in an optimization. I am doing something wrong but I am not sure
>what. This is a repost of a previous question that I phrased poorly.
>
>I am minimizing a convex f: R^n->R with derivative df: R^n->R^n using
>FindMinimum. A toy example,
>
>n = 1000;
>f[k_] := k.k
>df[k_] := 2k
>
>I find the minimal k starting at random k0:
>
>k0 = RandomReal[1, n];
>ker = Array[k, n];
>
>min = Reap[
>  t0 = AbsoluteTime[];
>  FindMinimum[f[ker], Transpose[{ker, k0}], Gradient -> df[ker],
>    StepMonitor :> Sow[AbsoluteTime[] - t0]]
>];
>
>min[[2,1]] gives the times of the steps
>
>(Above is a bad example as it converges in one step.)
>
>For my particular convex f, FindMinimum takes a very long time before
>it makes it's first step but then proceeds very quickly. And time
>scales superlinearly with n. It takes so long that I have resorted to
>a C Mathlink function that does BFGS or ConjugateGradient (from Press
>et al., Numerical Recipes, v3) and calls f and df through Mathlink.
>
>What is FindMinimum doing during this time before the first step?
>Compiling f and df? It does this even when I precompile f and df and
>specify Method. How do I specify my problem so it works faster? I
>would like it to just start making optimization steps because it's
>surprisingly efficient even with n large when it gets going.
>
>Also, thanks to whoever wrote all the excellent tutorial documentation
>for the optimization functions in Mathematica and the examples in
>UnconstrainedProblems.m.
>
>Art.
>  
>
Perhaps you could try using a vector variable approach:

Clear[f, df]

f[k_List] := k.k
df[k_List] := 2 k

k0 = RandomReal[1, 1000];
min = FindMinimum[f[v], {v, k0}, Gradient -> df[v]];

Or, a slightly less trivial example:

Clear[f, df]

f[k_List] := (k.k - 2)^2
df[k_List] := 4 k (k.k - 2)

k0 = RandomReal[1, 1000];
min = FindMinimum[f[v], {v, k0}, Gradient -> df[v]];

Carl Woll
Wolfram Research


  • Prev by Date: Re: Operate on Heads
  • Next by Date: Re: V.6.0.2 gripes...
  • Previous by thread: Speeding up FindMinimum setup
  • Next by thread: Does Mathematica think Sqrt[2] is rational?